数学のグラフ理論の分野における頂点(ちょうてん、英: 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)とは出次数がゼロの頂点のことである。 切断点
頂点の種類
任意の頂点を他の任意の頂点へと写すような対称性が存在するとき、そのグラフは頂点推移的であると言われる。グラフの列挙(英語版)やグラフ同型の文脈において、ラベル付けされた頂点とされていない頂点を区別することは重要である。ラベル付けされた頂点は、それを他のラベル付けされた頂点と区別することを可能にするような外的な情報を備えるものである。二つのグラフは、それらの頂点が等しいラベルを備えるもの同士でペアとされるような対応性が存在している状況に限り、同型であると見なされる。ラベル付けのされていない頂点は、そのグラフ内での隣接関係にのみ依存し、他の外的な情報には依存せず、他のラベル付けのされていない頂点と交換することが可能である。
グラフにおける頂点は、多角形の頂点と同様なものであるが、同一ではない。多角形のスケルトン(英語版)は、その頂点がグラフの頂点となるようなグラフを形成する。しかし、多角形の頂点は、グラフ理論では存在しないものとされるような付帯的な構造(幾何的な配置)も備えている。多角形の頂点の頂点図形(英語版)は、グラフにおける頂点の近傍と相似である。
有向グラフにおいて、ある頂点 u {\displaystyle u} の forward star は、その外向きの辺として定義される。頂点の集合 V {\displaystyle V} と辺の集合 E {\displaystyle E} を備えるグラフ G {\displaystyle G} において、 u {\displaystyle u} の forward star は { ( u , v ) ∈ E } {\displaystyle \{(u,v)\in E\}\ } [1]
と表される。
脚注^ (Gallo & Pallotino 1988, p. 4)
関連項目
節点 (計算機科学)(英語版)
参考文献
Gallo, Giorgio; Pallotino, Stefano (1988). “Shortest Path Algorithms”. Annals of Operations Research 13 (1): 1?79. doi:10.1007/BF02288320.
Berge, Claude, Theorie des graphes et ses applications. Collection Universitaire de Mathematiques, 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. .mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}ISBN 0-486-24775-9