連結グラフ

連結グラフ（れんけつグラフ、英: connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。

連結度

グラフがどの程度かたく結びついているかを示す不変量として連結度があり、主に点連結度 (vertex-connectivity) と辺連結度 (edge-connectivity) に分類される。また、グラフ全体の連結度 (それぞれ、辺連結度) について、指定した2点間に対する連結性を示す不変量として、局所点連結度 (local vertex-connectivity) (それぞれ、局所辺連結度 (local edge-connectivity) ) がある。点連結度 (それぞれ、局所点連結度) は単に連結度 (それぞれ、局所連結度) と呼ぶ場合があることを付記しておく。

点連結度

グラフ G から取り除くと非連結になるような k 個の頂点集合をk-点切断とよぶ。G においてk-点切断が存在するような最小の k を点連結度または連結度とよび、${\displaystyle \kappa (G),\chi (G)}$で表す。特に、1-点切断を切断点 (cut vertex) または関節点 (articulation point) とよぶ。k-連結グラフ (k-connected graph) は点連結度が k 以上のグラフである。

G から S を取り除いたグラフにおいて x と y の間に道が存在しないことを頂点の集合 S が x, y を分離するという。グラフ G から（もし存在すれば）辺 xy を除いたグラフにおいて、二つの頂点 x, y を分離するために必要な頂点の個数を s とするこのとき、x, yが隣接していないなら s を、x, y が隣接しているなら s + 1 を x, y の局所連結度といい、κ(x, y) 等で表すことが多い。点連結度は局所連結度の最小値と一致する。

グラフ G のある因子が k連結なら、G 自身も k 連結となる。G が k 連結で、G の自分自身を除いた因子が k 連結でないとき（つまり、G から一つでも辺を取り除くと k 連結でないとき）、G を 極小 k 連結 (minimally k-connected) という。

辺連結度

グラフ G から取り除くと非連結になるような k 本の辺集合をk-辺切断 (またはk-カット) とよぶ。G において k-辺切断が存在するような最小の k を辺連結度とよび、${\displaystyle \lambda (G),\chi '(G)}$で表す。特に、1-辺切断を切断辺または橋 (bridge) とよぶ。k-辺連結グラフ (k-edge-connected graph) は、辺連結度が k 以上のグラフのことを指す。

点連結度と同様に、2点 x, y を分離する辺集合の大きさの最小値として、局所辺連結度が定義され λ(x, y) で表記される。

また、 ${\displaystyle \lambda (G)=\min _{x,y\in V(G)}\lambda (x,y)}$ となることを付記しておく。

有向グラフと連結度

有向グラフにおいて、無向グラフと同様に連結度の対応物が定義されている^[1]。

強連結

有向グラフが強連結であるとは、グラフ上の任意の2点間に有向路が存在することである。極大で強連結な部分グラフは、強連結成分という。

点連結度の対応物

ある2点 x, y を指定したとき、除去することで x, y のどちらを始点にしても有向路が存在しなくなるような点集合の大きさの最小値として、x, y の局所点強連結度 (local vertex-strong connectivity) が定義される。 また、局所点強連結度の最小値を点強連結度 (vertex-strong connectivity) と呼ぶ。点強連結度が k 以上のグラフを k 点強連結グラフ (k-strongly connected graph) 、または、 k 強グラフ (k-strong graph) と呼ぶ。

辺連結度の対応物

ある2点 x, y を指定したとき、除去することで x, y のどちらを始点にしても有向路が存在しなくなるような辺集合の大きさの最小値として、 x, y の局所有向辺強連結度 (local arc-strong connectivity) が定義される。また、局所有向辺強連結度の最小値を有向辺強連結度 (arc-strong connectivity) と呼ぶ。有向辺強連結度が k 以上のグラフを k 有向辺強連結グラフ (k-arc-strongly connected graph) 、または、k 有向辺強グラフ (k-arc-strong graph) と呼ぶ。

連結度の一般化

• 要素連結度
• 節点領域連結度
• 集合間連結度

アルゴリズム

• k点連結成分分解
• k辺連結成分分解
• 強連結成分分解

性質

• グラフ G の最小次数を δ(G) で表すと、κ(G) ≦ λ(G) ≦ δ(G)。
• 任意の l < m < n に対し、κ(G) = l, λ(G) = m, δ(G) = n を満たすグラフ G が存在する。
• 2連結グラフの任意の頂点は、閉路上にある。
• 2 点 x, y 間の互いに独立な道 (点素パス) の最大個数は局所連結度 κ(x, y) に一致する（メンガーの定理）。
• 2 点 x, y 間の辺素パスの最大個数は局所辺連結度 λ(x, y) に一致する（メンガーの定理）。
• 任意の k 次元多面体のグラフの点連結度は k である。 (バリンスキーの定理)。

注釈・出典

1. 点連結度の対応物と辺連結度の対応物についての用語の和訳は定訳が不明であるため直訳した。

参考文献

• Bang-Jensen, J.; Gutin, G. Z. (2008). “Chapter 7. Global Connectivity”. Digraphs: Theory, Algorithms and Applications. Springer-Verlag. ISBN 978-1-85233-611-0. https://books.google.co.jp/books?id=CR_oBwAAQBAJ&pg=PA345
• Bollobás, B. (2004) [1978]. “Chapter 1. Connectivity”. Extreamal Graph Theory (Dover ed.). Academic Press. ISBN 0-486-43596-2. https://books.google.co.jp/books?id=fkLDAgAAQBAJ&pg=PA1
• Diestel, R. (2005). “Chapter 3. Connectivity”. Graph Theory. Graduate Textbooks in Mathematics. 173 (Third ed.). Springer-Verlag. ISBN 3-540-26183-4. https://books.google.co.jp/books?id=aR2TMYQr2CMC&pg=PA55

関連項目

数学的対象と性質

• カット (グラフ理論)
• k-頂点連結グラフ
• k-辺連結グラフ

定理

• メンガーの定理
• 最大フロー最小カット定理
• バリンスキーの定理

その他

• 連結空間
• 素集合データ構造