連結グラフ

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

連結度

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

点連結度

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

テンプレート:Mvar から テンプレート:Mvar を取り除いたグラフにおいて テンプレート:Mvar と テンプレート:Mvar の間に道が存在しないことを頂点の集合 テンプレート:Mvar が テンプレート:Mvar を分離するという。グラフ テンプレート:Mvar から（もし存在すれば）辺 テンプレート:Mvar を除いたグラフにおいて、二つの頂点 テンプレート:Mvar を分離するために必要な頂点の個数を テンプレート:Mvar とするこのとき、テンプレート:Mvarが隣接していないなら テンプレート:Mvar を、テンプレート:Mvar が隣接しているなら テンプレート:Math を テンプレート:Mvar の局所連結度といい、テンプレート:Math 等で表すことが多い。点連結度は局所連結度の最小値と一致する。

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

辺連結度

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

点連結度と同様に、2点 テンプレート:Mvar を分離する辺集合の大きさの最小値として、局所辺連結度が定義され テンプレート:Math で表記される。

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

有向グラフと連結度

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

強連結

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

点連結度の対応物

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

辺連結度の対応物

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

連結度の一般化

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

アルゴリズム

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

性質

• グラフ テンプレート:Mvar の最小次数を テンプレート:Math で表すと、テンプレート:Math。
• 任意の テンプレート:Math に対し、テンプレート:Math を満たすグラフ テンプレート:Mvar が存在する。
• 2連結グラフの任意の頂点は、閉路上にある。
• 2 点 テンプレート:Mvar 間の互いに独立な道 (点素パス) の最大個数は局所連結度 テンプレート:Math に一致する（メンガーの定理）。
• 2 点 テンプレート:Mvar 間の辺素パスの最大個数は局所辺連結度 テンプレート:Math に一致する（メンガーの定理）。
• 任意の テンプレート:Mvar 次元多面体のグラフの点連結度は テンプレート:Mvar である。 (バリンスキーの定理)。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book

関連項目

数学的対象と性質

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

定理

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

その他

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