頂点の種類
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/21 16:49 UTC 版)
「頂点 (グラフ理論)」の記事における「頂点の種類」の解説
ある頂点の次数とは、その頂点に接続する辺の数のことである。孤立点（isolated vertex）とは、次数がゼロの頂点のことである。葉頂点（leaf vertex）あるいはペンダント頂点（pendant vertex）とは、次数が 1 の頂点のことである。有向グラフにおいては、入次数（indegree、入ってくる辺の数）と出次数（outdegree、出ていく辺の数）が区別される。源点（source vertex）とは入次数がゼロの頂点のことであり、沈点（sink vertex）とは出次数がゼロの頂点のことである。 切断点（英語版）（cut vertex）とは、それを除くと残されたグラフが非連結となるような頂点のことである。頂点分離（英語版）（vertex separator）とは、それらを除くと残されたグラフがそれぞれ小さな断片へとなることで非連結となるような頂点の集まりのことである。k-頂点連結グラフとは、k より少ない数の頂点を除くだけでは依然として連結であるようなグラフのことである。独立集合とは、どの二つの頂点も隣接していないような頂点の集合のことであり、頂点被覆とは、グラフの各辺の端点を含むような頂点の集合のことである。グラフの頂点空間（英語版）とは、グラフの頂点に対応する基底ベクトルの集合を備えるベクトル空間のことである。 任意の頂点を他の任意の頂点へと写すような対称性が存在するとき、そのグラフは頂点推移的であると言われる。グラフの列挙（英語版）やグラフ同型の文脈において、ラベル付けされた頂点とされていない頂点を区別することは重要である。ラベル付けされた頂点は、それを他のラベル付けされた頂点と区別することを可能にするような外的な情報を備えるものである。二つのグラフは、それらの頂点が等しいラベルを備えるもの同士でペアとされるような対応性が存在している状況に限り、同型であると見なされる。ラベル付けのされていない頂点は、そのグラフ内での隣接関係にのみ依存し、他の外的な情報には依存せず、他のラベル付けのされていない頂点と交換することが可能である。 グラフにおける頂点は、多角形の頂点と同様なものであるが、同一ではない。多角形のスケルトン（英語版）は、その頂点がグラフの頂点となるようなグラフを形成する。しかし、多角形の頂点は、グラフ理論では存在しないものとされるような付帯的な構造（幾何的な配置）も備えている。多角形の頂点の頂点図形（英語版）は、グラフにおける頂点の近傍と相似である。 有向グラフにおいて、ある頂点 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\}\ } と表される。
※この「頂点の種類」の解説は、「頂点 (グラフ理論)」の解説の一部です。
「頂点の種類」を含む「頂点 (グラフ理論)」の記事については、「頂点 (グラフ理論)」の概要を参照ください。
- 頂点の種類のページへのリンク
