k 頂点連結グラフ

グラフ理論では、連結グラフ Gがk個を超える頂点を持ち、 k 個未満の頂点を削除しても連結されたままである場合、その連結グラフGはk頂点連結(またはk連結) であると言われます。

グラフの頂点連結性、または単に連結性は、グラフがk頂点連結される 最大のkです。

グラフ（完全グラフ以外）の接続性がkであるとは、頂点の最小部分集合のサイズがkであり、その頂点を削除するとグラフが切断されることを意味する。 ^[1]完全グラフでは、部分集合を削除してもグラフが切断されることはない。一部の情報源では、接続性の定義を、削除するとグラフが切断されるか頂点が 1 つだけになるような最小部分集合のサイズとして定義し、このケースに対応できるように変更している。このバリエーションでは、完全グラフの接続性はである。^[2]${\displaystyle K_{n}}$${\displaystyle n-1}$

同等の定義は、少なくとも2つの頂点を持つグラフがk連結であるとは、そのグラフの頂点のすべてのペアに対して、これらの頂点を接続するk本の頂点独立パスを見つけることが可能である場合である。メンガーの定理（Diestel 2005、p. 55）を参照。この定義は、完全グラフK _n の連結性について同じ答えn −1を生成する。^[1]

1 連結グラフは連結グラフと呼ばれ、2 連結グラフは二連結グラフと呼ばれます。3 連結グラフは三連結グラフと呼ばれます。

すべてのグラフは、1 連結コンポーネントの分離した和集合に分解されます。1 連結グラフは、2 連結コンポーネントのツリーに分解されます。2 連結グラフは、3連結コンポーネントのツリーに分解されます。

任意のk次元凸多面体の1次元スケルトンはk頂点連結グラフを形成する（バリンスキーの定理）。^[3]部分的な逆として、シュタイニッツの定理は任意の3頂点連結平面グラフが凸多面体のスケルトンを形成することを述べている。

入力グラフGの頂点の接続性は、次の方法^[4]で多項式時間で計算できます。隣接していないノードのすべての可能なペアを切断することを検討し、メンガーの定理を使用して、 の最小サイズのセパレータがそれらの間のペアごとの頂点独立パスの数であることを正当化し、各頂点をエッジとして 2 倍にして入力をエンコードして、ペアごとのエッジ独立パスの数の計算に減らし、各エッジへの容量 1 でと間のグラフの最大フローを計算することで、そのようなパスの最大数を計算します。このグラフの のフローは、積分フロー定理により、 からへのペアごとのエッジ独立パスに対応することに注意してください。 ${\displaystyle (s,t)}$${\displaystyle (s,t)}$${\displaystyle s}$${\displaystyle t}$${\displaystyle k}$${\displaystyle k}$${\displaystyle s}$${\displaystyle t}$

k≥2とします。

• 少なくとも位数の連結グラフには、少なくとも長さの閉路が含まれる。${\displaystyle k}$${\displaystyle 2k}$${\displaystyle 2k}$
• 連結グラフでは、 内の任意の頂点は共通閉路上に存在する。^[5]${\displaystyle k}$${\displaystyle k}$${\displaystyle G}$

連結グラフのサイクル空間は、分離しない誘導サイクルによって生成される。 ^[6]${\displaystyle 3}$

少なくとも頂点を持つグラフは、任意のシーケンスに対して互いに素なパス があり、異なる頂点を持つ場合、 -リンクグラフと呼ばれます。すべての-リンクグラフは-接続グラフですが、必ずしも -接続されているわけではありません。^[7]${\displaystyle 2k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle a_{1},\dots ,a_{k}}$${\displaystyle b_{1},\dots ,b_{k}}$${\displaystyle 2k}$${\displaystyle k}$${\displaystyle (2k-1)}$${\displaystyle 2k}$

グラフが-連結で平均次数が少なくともの場合、そのグラフは-連結である。 ^[8]${\displaystyle 2k}$${\displaystyle 16k}$${\displaystyle k}$

• k辺連結グラフ
• 連結性（グラフ理論）
• メンガーの定理
• 構造的凝集性
• トゥッテ埋め込み
• 頂点セパレータ

• Diestel、Reinhard (2005)、グラフ理論 (第 3 版)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-3-540-26183-4
• Diestel, Reinhard (2012)、「グラフ理論」（訂正第 4 版電子版）
• Diestel、Reinhard (2016)、グラフ理論 (第 5 版)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-3-662-53621-6