k-頂点連結グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動: 案内、 検索


数学のグラフ理論において、頂点集合 V(G) を備えるグラフ G がk-頂点連結（k-ちょうてんれんけつ、英: k-vertex-connected）あるいはk-連結であるとは、k より少ない数の頂点を取り除いても依然としてそのグラフが連結（英語版）であることを言う。代替的に、グラフがk-連結であるとは、それらを除いたときにグラフが非連結となるような頂点の最小部分集合の大きさが k であることを言う[1]。

グラフが完全でないことと同値な定義は、任意の二つの頂点が k 独立な道によって結ばれるときにグラフがk-連結であることである; メンガーの定理を参照されたい(Diestel 2005, p. 55)。しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: n-頂点の完全グラフは、頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、独立な道に基づいた定義に従うと、その連結度は n − 1 になる。そして、何人かの研究者は、連結度が n となるような代替的な定義を用いている[1]。

1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。

グラフの頂点連結度あるいは単純に連結度とは、そのグラフ k-頂点連結であるような k の最大数のことを言う。

任意のk-次元凸ポリトープのスケルトン（英語版）は、k-頂点連結グラフを形成する（バリンスキーの定理、Balinski 1961）。その部分的な逆として、シュタイニッツの定理（英語版）では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。

関連項目 [編集]

注釈 [編集]

  1. ^ a b Schrijver, Combinatorial Optimization, Springer 

参考文献 [編集]

執筆の途中です この項目は、数学に関連した書きかけの項目です。この記事を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。
「http://ja.wikipedia.org/w/index.php?title=K-頂点連結グラフ&oldid=47448961」から取得