|
数学のグラフ理論において、頂点集合 を備えるグラフ が ''k''-頂点連結（''k''-ちょうてんれんけつ、）あるいは''k''-連結であるとは、 ''k'' より少ない数の頂点を取り除いても依然として連結グラフであることを言う。 つまり、点連結度がk以上のグラフのことである。 代替的に、グラフが''k''-連結であるとは、それらを除いたときに グラフが非連結となるような頂点の最小部分集合の大きさが ''k'' であることを言う。 グラフが完全でないことと同値な定義は、任意の二つの頂点が ''k'' 独立な道 (点素パス) によって 結ばれるときにグラフが''k''-連結であることである; メンガーの定理を参照されたい。 しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: ''n''-頂点の完全グラフは、 頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、 独立な道に基づいた定義に従うと、その連結度は ''n'' − 1 になる。 そして、何人かの研究者は、連結度が ''n'' となるような代替的な定義を用いている〔。 1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。 グラフの頂点連結度あるいは単純に連結度とは、 そのグラフ ''k''-頂点連結であるような ''k'' の最大数のことを言う。 任意の''k''-次元凸ポリトープのは、 ''k''-頂点連結グラフを形成する（バリンスキーの定理、）。 その部分的な逆として、では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。 ''k'' より少ない数の頂点を取り除いても依然として連結グラフであることを言う。 つまり、点連結度がk以上のグラフのことである。 代替的に、グラフが''k''-連結であるとは、それらを除いたときに グラフが非連結となるような頂点の最小部分集合の大きさが ''k'' であることを言う。 グラフが完全でないことと同値な定義は、任意の二つの頂点が ''k'' 独立な道 (点素パス) によって 結ばれるときにグラフが''k''-連結であることである; メンガーの定理を参照されたい。 しかしながら、完全グラフに対して、上述の二つの定義は異なるものとなる: ''n''-頂点の完全グラフは、 頂点を除去することに基づいた定義に従うとその連結度は非有界となるが、 独立な道に基づいた定義に従うと、その連結度は ''n'' − 1 になる。 そして、何人かの研究者は、連結度が ''n'' となるような代替的な定義を用いている〔。 1-頂点連結グラフは、連結であると言われ、2-頂点連結グラフは2重連結であると言われる。 グラフの頂点連結度あるいは単純に連結度とは、 そのグラフ ''k''-頂点連結であるような ''k'' の最大数のことを言う。 任意の''k''-次元凸ポリトープのは、 ''k''-頂点連結グラフを形成する（バリンスキーの定理、）。 その部分的な逆として、では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。 連結度とは、 そのグラフ ''k''-頂点連結であるような ''k'' の最大数のことを言う。 任意の''k''-次元凸ポリトープのは、 ''k''-頂点連結グラフを形成する（バリンスキーの定理、）。 その部分的な逆として、では、任意の3-頂点連結平面グラフは凸多面体のスケルトンを形成する、ということが述べられている。 == 関連項目 == === 数学的対象と性質 === * k-辺連結グラフ * 連結グラフ * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-頂点連結グラフ」の詳細全文を読む スポンサード リンク
|