K-頂点連結グラフのソースを表示

{{DISPLAYTITLE:''k''-頂点連結グラフ}}
[[数学]]の[[グラフ理論]]において、頂点集合 <math>V(G)</math> を備えるグラフ <math>G</math> が
'''''k''-頂点連結'''（''k''-ちょうてんれんけつ、{{Lang-en-short|k-vertex-connected}}）あるいは'''''k''-連結'''であるとは、
''k'' より少ない数の頂点を取り除いても依然として[[連結グラフ]]であることを言う。
つまり、[[連結グラフ|点連結度]]がk以上のグラフのことである。
代替的に、グラフが'''''k''-連結'''であるとは、それらを除いたときに
グラフが[[連結グラフ|非連結]]となるような頂点の最小部分集合の大きさが ''k'' であることを言う<ref name="Schrijver">{{Citation|author=Schrijver|title=Combinatorial Optimization|publisher=Springer}}</ref>。

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

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

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

任意の''k''-次元凸[[ポリトープ]]の{{仮リンク|スケルトン (位相幾何学)|label=スケルトン|en|Skeleton (topology)}}は、
''k''-頂点連結グラフを形成する（[[バリンスキーの定理]]、{{harvnb|Balinski|1961}}）。
その部分的な逆として、{{仮リンク|シュタイニッツの定理|en|Steinitz's theorem}}では、任意の3-頂点連結[[平面グラフ]]は凸[[多面体]]のスケルトンを形成する、ということが述べられている。

== 関連項目 ==
=== 数学的対象と性質 ===
* [[k-辺連結グラフ]]
* [[連結グラフ]]
* {{仮リンク|連結度|en|Connectivity (graph theory)}}
=== 定理 ===
* [[メンガーの定理]]
=== 問題 ===
* [[点連結度増大問題]]
=== その他 ===
* {{仮リンク|構造結束|en|Structural cohesion}}

== 注釈 ==
{{Reflist}}

== 参考文献 ==
*{{citation
 | last = Balinski | first = M. L.
 | issue = 2
 | journal = [[:en:Pacific Journal of Mathematics|Pacific Journal of Mathematics]]
 | pages = 431–434
 | title = On the graph structure of convex polyhedra in ''n''-space
 | url = http://www.projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103037323
 | volume = 11
 | year = 1961}}.
*{{citation
 | last = Diestel | first = Reinhard
 | edition = 3rd
 | isbn = 978-3-540-26183-4
 | location = Berlin, New York
 | publisher = Springer-Verlag
 | title = Graph Theory
 | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
 | year = 2005}}.

{{Combin-stub}}
{{DEFAULTSORT:kけいちようてんれんけつくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]