Loading article…
離散数学、特にグラフ理論において、頂点（複数形は頂点群）またはノードは、グラフを構成する基本単位です。無向グラフは頂点の集合と辺（頂点の順序付けされていないペア）の集合からなり、有向グラフは頂点の集合と弧（頂点の順序付けされたペア）の集合からなります。グラフの図では、頂点は通常、ラベル付きの円で表され、辺は1つの頂点から別の頂点へと伸びる線または矢印で表されます。
グラフ理論の観点から見ると、頂点は特徴のない不可分なオブジェクトとして扱われますが、グラフが発生するアプリケーションによっては、追加の構造を持つ場合もあります。例えば、意味ネットワークは、頂点が概念やオブジェクトのクラスを表すグラフです。
辺を形成する 2 つの頂点は、その辺の端点と呼ばれ、その辺はそれらの頂点に接続されていると言われます。グラフに辺 ( v , w ) が存在する場合、頂点wは別の頂点vに隣接していると言われます。頂点vの近傍は、 vに隣接するすべての頂点によって形成される、グラフの誘導部分グラフです。
グラフにおける頂点の次数𝛿 (v) は、その頂点に接続する辺の数です。孤立頂点とは、次数がゼロの頂点、つまりどの辺の端点でもない頂点です (例の画像は 1 つの孤立頂点を示しています)。[ 1 ]葉頂点(または垂下頂点) は、次数が 1 の頂点です。有向グラフでは、出次数 (出ている辺の数) 𝛿 + (v) と入次数 (入っている辺の数) 𝛿 − (v)を区別できます。ソース頂点は入次数がゼロの頂点であり、シンク頂点は出次数がゼロの頂点です。単体頂点とは、閉じた近傍がクリークを形成する頂点です。つまり、任意の2つの隣接頂点が隣接しています。普遍頂点とは、グラフ内の他のすべての頂点に隣接している頂点です。
カット頂点とは、それを取り除くと残りのグラフが分断される頂点のことです。頂点分離点とは、それを取り除くと残りのグラフが小さな断片に分断される頂点の集合のことです。k頂点連結グラフとは、 k個未満の頂点を取り除いても残りのグラフが常に連結されたままとなるグラフのことです。独立集合とは、どの2つの頂点も隣接しない頂点の集合であり、頂点被覆とは、グラフ内の各辺の少なくとも1つの端点を含む頂点の集合のことです。グラフの頂点空間とは、グラフの頂点に対応する基底ベクトルの集合を持つベクトル空間のことです。
グラフは、任意の頂点を他の任意の頂点にマッピングする対称性を持つ場合、頂点推移的であると言います。グラフ列挙とグラフ同型性の文脈では、ラベル付き頂点とラベルなし頂点を区別することが重要です。ラベル付き頂点とは、他のラベル付き頂点と区別できる追加情報が関連付けられている頂点です。2つのグラフは、それらの頂点間の対応関係が同じラベルを持つ頂点をペアにする場合に限り、同型であるとみなすことができます。ラベルなし頂点とは、グラフ内の隣接関係のみに基づいて他の任意の頂点と置き換えることができ、追加情報に基づいて置き換えることができない頂点です。
グラフの頂点は、多面体の頂点と類似していますが、同一ではありません。多面体の骨格はグラフを形成し、その頂点は多面体の頂点ですが、多面体の頂点には、グラフ理論では想定されていない追加の構造（幾何学的位置）があります。多面体の頂点の頂点図は、グラフの頂点の近傍に類似しています。