頂点（グラフ理論）

離散数学、より具体的にはグラフ理論において、頂点（複数形はvertices）またはノードはグラフが形成される基本単位です。無向グラフは頂点の集合と辺の集合（頂点の順序のないペア）で構成され、有向グラフは頂点の集合と弧の集合（頂点の順序のあるペア）で構成されます。グラフの図では、頂点は通常、ラベルの付いた円で表され、辺は頂点から頂点へ伸びる線または矢印で表されます。

グラフ理論の観点からは、頂点は特徴のない分割不可能なオブジェクトとして扱われますが、グラフが発生するアプリケーションに応じて追加の構造を持つ場合があります。たとえば、セマンティック ネットワークは、頂点がオブジェクトの概念またはクラスを表すグラフです。

辺を形成する 2 つの頂点は、この辺の端点であるとされ、辺は頂点に接続されているとされます。グラフに辺 ( v , w )が含まれている場合、頂点w は別の頂点vに隣接していると言われます。頂点vの近傍は、 vに隣接するすべての頂点によって形成されるグラフの 誘導サブグラフです。

グラフ内の頂点の次数（ 𝛿(v) と表記）は、その頂点に接続する辺の数です。孤立頂点は次数 0 の頂点、つまりどの辺の終点でもない頂点です（例の画像は孤立頂点を 1 つ示しています）。^[1]葉頂点（ペンダント頂点とも呼ばれる）は次数 1 の頂点です。有向グラフでは、出次数（出ていく辺の数）𝛿 ⁺ (v) と表記され、入次数（入ってくる辺の数）𝛿 ⁻ (v) と表記される頂点を区別できます。ソース頂点は入次数 0 の頂点で、シンク頂点は出次数 0 の頂点です。単体頂点は、隣接する頂点がクリークを形成する頂点です。つまり、2 つの隣接する頂点はすべて隣接しています。ユニバーサル頂点は、グラフ内の他のすべての頂点に隣接する頂点です。

カット頂点とは、削除すると残りのグラフが切断される頂点です。頂点セパレータとは、削除すると残りのグラフが小さな断片に切断される頂点の集合です。k頂点連結グラフとは、 k個未満の頂点を削除しても、残りのグラフが常に連結されたままになるグラフです。独立集合とは、2 つの頂点が隣接しない頂点の集合であり、頂点カバーとは、グラフの各辺の少なくとも 1 つの端点を含む頂点の集合です。グラフの頂点空間は、グラフの頂点に対応する基底ベクトルの集合を持つベクトル空間です。

グラフは、任意の頂点を他の任意の頂点にマッピングする対称性がある場合、頂点推移的です。グラフの列挙とグラフ同型性のコンテキストでは、ラベル付き頂点とラベルなし頂点を区別することが重要です。ラベル付き頂点は、他のラベル付き頂点と区別できるようにする追加情報に関連付けられている頂点です。2 つのグラフは、頂点間の対応が同じラベルを持つ頂点のペアになる場合にのみ同型と見なすことができます。ラベルなし頂点は、グラフ内の 隣接関係のみに基づいて、追加情報に基づかずに他の任意の頂点と置き換えることができる頂点です。

グラフの頂点は多面体の頂点に類似していますが、同じではありません。多面体の骨格はグラフを形成し、その頂点は多面体の頂点ですが、多面体の頂点には、グラフ理論では存在しないと想定されている追加の構造 (幾何学的位置) があります。多面体の頂点の頂点図は、グラフの頂点の近傍に類似しています。

• ノード（コンピュータサイエンス）
• グラフ理論
• グラフ理論用語集

• Gallo, Giorgio; Pallotino, Stefano (1988). 「最短経路アルゴリズム」. Annals of Operations Research . 13 (1): 1–79. doi :10.1007/BF02288320. S2CID  62752810.
• Berge、Claude、Théorie desgraphes et ses application。 Collection Universitaire de Mathématiques、II Dunod、パリ 1958、viii+277 ページ (英語版、Wiley 1961; Methuen & Co、ニューヨーク 1962; ロシア語、モスクワ 1961; スペイン語、メキシコ 1962; ルーマニア語、ブカレスト 1969; 中国語、上海 1963 ; 1962 年の初版英語版の第 2 刷。ニューヨーク 2001)
• チャートランド、ゲイリー（1985年）。『グラフ理論入門』ニューヨーク：ドーバー。ISBN 0-486-24775-9。
• ビッグス、ノーマン、ロイド、EH、ウィルソン、ロビン J. (1986)。グラフ理論、1736-1936。オックスフォード[オックスフォードシャー]：クラレンドンプレス。ISBN 0-19-853916-9。
• ハラリー、フランク(1969)。グラフ理論。マサチューセッツ州レディング：アディソン・ウェスレー出版。ISBN 0-201-41033-8。
• ハラリー、フランク; パーマー、エドガー M. (1973)。グラフィカル列挙。ニューヨーク、アカデミック プレス。ISBN 0-12-324245-2。

• Weisstein、Eric W.「グラフ頂点」。MathWorld。