頂点 (グラフ理論)

数学のグラフ理論の分野における頂点（ちょうてん、英: 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 より少ない数の頂点を除くだけでは依然として連結であるようなグラフのことである。独立集合とは、どの二つの頂点も隣接していないような頂点の集合のことであり、頂点被覆とは、グラフの各辺の端点を含むような頂点の集合のことである。グラフの頂点空間（英語版）とは、グラフの頂点に対応する基底ベクトルの集合を備えるベクトル空間のことである。

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

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

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

${\displaystyle \{(u,v)\in E\}\ }$^[1]

と表される。

• 節点 (計算機科学)（英語版）

• 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 (英語).

表 話 編 歴 グラフ理論
要素・定義・表現	頂点 辺（英語版） グラフ 無向 有向 ラベル付き（英語版） 重み付き（英語版） ハイパーグラフ 接続行列 隣接行列 隣接リスト
指標	位数（英語版） サイズ（英語版） 次数 次数行列 距離（英語版） 半径 直径 内周 (頂点)彩色数 辺彩色数（英語版） 点連結度 辺連結度 交叉数（英語版）
部分構造	ループ（英語版） 多重辺（英語版） 部分グラフ（英語版） 誘導部分グラフ 道 閉道 連結成分（英語版） 強連結成分（英語版） 橋（英語版） カット クリーク 独立集合 支配集合（英語版） マッチング オイラー路 シュタイナー木 全域木 ハミルトン路
全体構造	連結グラフ 正則グラフ 立方体グラフ ケージ 強正則グラフ 木 平面グラフ 2部グラフ 有向非巡回グラフ 弦グラフ ムーアグラフ パーフェクトグラフ 対称グラフ 半対称グラフ 頂点推移グラフ 辺推移グラフ 距離推移グラフ 補グラフ 双対グラフ グラフ同型
固有名を持つグラフ	パスグラフ（英語版）Pn 閉路グラフCn 完全グラフKn 完全2部グラフKm,n スターSn = K1,n 車輪グラフWn 空グラフ ピーターセングラフ ヒーウッドグラフ マギーグラフ ホフマンシングルトングラフ フォークマングラフ
トピック・定理	一筆書き オイラーの多面体定理 クラトフスキの定理 四色定理 五色定理 ケイリーの公式 プリューファー列 最短経路問題 巡回セールスマン問題 中国人郵便配達問題 ダイクストラ法 ベルマン-フォード法 ワーシャル-フロイド法 ハミルトン閉路問題 最大クリーク問題 頂点被覆問題 最小頂点被覆問題 最大独立集合問題 最大流最小カット定理 支配集合問題 次数直径問題 安定結婚問題
カテゴリ / コモンズ