頂点 (グラフ理論)

6 つの頂点と 7 つの辺を含むグラフ。左端の番号 6 の頂点は、葉頂点あるいはペンダント頂点と呼ばれる。

数学のグラフ理論の分野における頂点（ちょうてん、英: vertex）あるいは節点（せってん、英: node）とは、グラフを形成する基本的な構成単位である。頂点の数を位数（英: order）と呼ぶ。

無向グラフは頂点の集合と辺（英: edge、向き付けのされていない頂点のペア）の集合で構成され、有向グラフは頂点の集合と弧（arc、向き付けのされている頂点のペア）の集合で構成される。グラフを図示する際、頂点は通常ラベル付けのされた円で表され、辺は各頂点から別の頂点へと伸びる直線あるいは矢で表される。

グラフ理論において、頂点は決まった形の無いそれ以上分割の出来ない物体として扱われるが、それらが応用される場面においては他の構造が付け加えられることもある。例えば、意味ネットワークのグラフにおいては、頂点は概念やオブジェクトの類を表す。

辺を形成する二つの頂点は、その辺の端点（endpoint）と呼ばれ、その辺はそれらの頂点に接続（incident）していると言われる。ある頂点 w が別の頂点 v に隣接（adjacent）しているとは、グラフが辺 (v,w) を含むことを言う。ある頂点 v の近傍とは、v に隣接するすべての頂点によって形成される誘導部分グラフのことを言う。

頂点の種類

ある頂点の次数とは、その頂点に接続する辺の数のことである。孤立点（isolated vertex）とは、次数がゼロの頂点のことである。葉頂点（leaf vertex）あるいはペンダント頂点（pendant vertex）とは、次数が 1 の頂点のことである。有向グラフにおいては、入次数（indegree、入ってくる辺の数）と出次数（outdegree、出ていく辺の数）が区別される。源点（source vertex）とは入次数がゼロの頂点のことであり、沈点（sink vertex）とは出次数がゼロの頂点のことである。

切断点（cut vertex）とは、それを除くと残されたグラフが非連結となるような頂点のことである。頂点分離（vertex separator）とは、それらを除くと残されたグラフがそれぞれ小さな断片へとなることで非連結となるような頂点の集まりのことである。k-頂点連結グラフとは、k より少ない数の頂点を除くだけでは依然として連結であるようなグラフのことである。独立集合とは、どの二つの頂点も隣接していないような頂点の集合のことであり、頂点被覆とは、グラフの各辺の端点を含むような頂点の集合のことである。グラフの頂点空間とは、グラフの頂点に対応する基底ベクトルの集合を備えるベクトル空間のことである。

任意の頂点を他の任意の頂点へと写すような対称性が存在するとき、そのグラフは頂点推移的であると言われる。グラフの列挙やグラフ同型の文脈において、ラベル付けされた頂点とされていない頂点を区別することは重要である。ラベル付けされた頂点は、それを他のラベル付けされた頂点と区別することを可能にするような外的な情報を備えるものである。二つのグラフは、それらの頂点が等しいラベルを備えるもの同士でペアとされるような対応性が存在している状況に限り、同型であると見なされる。ラベル付けのされていない頂点は、そのグラフ内での隣接関係にのみ依存し、他の外的な情報には依存せず、他のラベル付けのされていない頂点と交換することが可能である。

グラフにおける頂点は、多角形の頂点と同様なものであるが、同一ではない。多角形のスケルトンは、その頂点がグラフの頂点となるようなグラフを形成する。しかし、多角形の頂点は、グラフ理論では存在しないものとされるような付帯的な構造（幾何的な配置）も備えている。多角形の頂点の頂点図形は、グラフにおける頂点の近傍と相似である。

有向グラフにおいて、ある頂点 $u$ の forward star は、その外向きの辺として定義される。頂点の集合 $V$ と辺の集合 $E$ を備えるグラフ $G$ において、$u$ の forward star は

$\{(u,v)\in E\}\$

と表される。

関連項目

• 節点 (計算機科学)

参考文献

• Gallo, Giorgio; Pallotino, Stefano (1988). “Shortest Path Algorithms”. Annals of Operations Research 13 (1): 1–79. doi:10.1007/BF02288320. 
• Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
• Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9 
• Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9 
• Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8 
• Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN 0-12-324245-2 

外部リンク

• Weisstein, Eric W. "Graph Vertex". mathworld.wolfram.com (英語).