K-頂点連結グラフ (original) (raw)

数学のグラフ理論において、頂点集合 を備えるグラフ がk-頂点連結（k-ちょうてんれんけつ、英: k-vertex-connected）あるいはk-連結であるとは、k より少ない数の頂点を取り除いても依然として連結グラフであることを言う。つまり、点連結度がk以上のグラフのことである。代替的に、グラフがk-連結であるとは、それらを除いたときにグラフが非連結となるような頂点の最小部分集合の大きさが k であることを言う。 グラフが完全でないことと同値な定義は、任意の二つの頂点が k 独立な道 (点素パス) によって結ばれるときにグラフがk-連結であることである; メンガーの定理を参照されたい。しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: n-頂点の完全グラフは、頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、独立な道に基づいた定義に従うと、その連結度は n − 1 になる。そして、何人かの研究者は、連結度が n となるような代替的な定義を用いている。 1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。 グラフの頂点連結度あるいは単純に連結度とは、そのグラフ k-頂点連結であるような k の最大数のことを言う。