連結グラフ
連結グラフ（れんけつグラフ, connected graph）は、 グラフ上の任意の2頂点間に道が存在するグラフのことである。 連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。 極大で連結な部分グラフは、連結成分 (connected component) という。
目次
連結度
グラフがどの程度、かたく結びついているかを示す尺度として、点連結度 (vertex-connectivity) と 辺連結度 (edge-connectivity) がある。 また、グラフ全体の連結度 (それぞれ、辺連結度) に対して、 指定した2点間の連結性を示す尺度として、局所点連結度 (local vertex-connectivity) (それぞれ、局所辺連結度 (local edge-connectivity) ) がある。
点連結度 (それぞれ、局所点連結度) は単に連結度 (それぞれ、局所連結度) と呼ぶ場合があることを付記しておく。
点連結度
グラフGから、k個の頂点を取り除いてGを非連結にする操作を、k-点切断という。Gをk-点切断するkのうち、 最小のkを点連結度または単に連結度という。 また、除去することで非連結になるようなk個の頂点集合をk-点切断と呼ぶこともある。 特に、1-点切断を切断点 (cut vertex) または関節点 (articulation point) と呼ぶ。
k-連結グラフ (k-connected graph) は、点連結度がk以上のグラフのことを指す。 点連結度は、<math>\kappa(G), \chi(G)</math> 等で表すことが多い。
GからSを取り除いたグラフにおいてxとyの間に道が存在しないことを 頂点の集合Sがx, yを分離するという。 グラフGから（もし存在すれば）辺xyを除いたグラフにおいて、 二つの頂点x, yを分離するために必要な頂点の個数を s とする このとき、x, yが隣接していないならsを、 x, yが隣接しているならs+1をx, yの局所連結度といい、 <math>\kappa(x, y)</math> 等で表すことが多い。 点連結度は局所連結度の最小値と一致する。
グラフGのある因子がk連結なら、G自身もk連結となる。 Gがk連結で、Gの自分自身を除いた因子がk連結でないとき（つまり、Gから一つでも辺を取り除くとk連結でないとき）、 Gを 極小k連結 (minimally k-connected) という。
辺連結度
グラフGから、k個の辺を取り除いてGを非連結にする操作を、k-辺切断という。Gをk-辺切断するkのうち、最小のkを辺連結度という。 また、除去することで非連結になるようなk本の辺集合をk-辺切断 (k-カット) と呼ぶこともある。 特に、1-辺切断を切断辺または橋 (bridge) と呼ぶ。
k-辺連結グラフ (k-edge-connected graph) は、辺連結度がk以上のグラフのことを指す。 辺連結度は、<math>\lambda(G), \chi'(G)</math> 等で表すことが多い。
点連結度と同様に、2点 <math>x, y</math> を分離する辺集合の大きさの最小値として、 局所辺連結度が定義され <math>\lambda(x, y)</math> で表記される。
また、 <math>\lambda(G) = \min_{x, y \in V(G)} \lambda(x, y) </math> となることを付記しておく。
有向グラフと連結度
有向グラフにおいて、無向グラフと同様に連結度の対応物が定義されている。 [1]
強連結
有向グラフが強連結であるとは、グラフ上の任意の2点間に有向路が存在することである。 極大で強連結な部分グラフは、強連結成分という。
点連結度の対応物
ある2点 <math>x, y</math> を指定したとき、 除去することで <math>x, y</math> のどちらを始点にしても有向路が存在しなくなるような点集合の大きさの最小値として、 <math>x, y</math> の局所点強連結度 (local vertex-strong connectivity) が定義される。 また、局所点強連結度の最小値を点強連結度 (vertex-strong connectivity) と呼ぶ。 点強連結度が <math>k</math> 以上のグラフを <math>k</math> 点強連結グラフ (<math>k</math>-strongly connected graph) 、または、 <math>k</math> 強グラフ (<math>k</math>-strong graph) と呼ぶ。
辺連結度の対応物
ある2点 <math>x, y</math> を指定したとき、 除去することで <math>x, y</math> のどちらを始点にしても有向路が存在しなくなるような辺集合の大きさの最小値として、 <math>x, y</math> の局所有向辺強連結度 (local arc-strong connectivity) が定義される。 また、局所有向辺強連結度の最小値を有向辺強連結度 (arc-strong connectivity) と呼ぶ。 有向辺強連結度が <math>k</math> 以上のグラフを <math>k</math> 有向辺強連結グラフ (<math>k</math>-arc-strongly connected graph) 、または、 <math>k</math> 有向辺強グラフ (<math>k</math>-arc-strong graph) と呼ぶ。
連結度の一般化
性質
- グラフGの最小次数をδ(G)で表すと、κ(G)≦λ(G)≦δ(G)。
- 任意のl<m<nに対し、κ(G)=l, λ(G)=m, δ(G)=n を満たすグラフGが存在する。
- 2連結グラフの任意の頂点は、閉路上にある。
- 2 点x, y間の互いに独立な道 (点素パス) の最大個数は局所連結度 <math>\kappa(x, y)</math> に一致する（メンガーの定理）。
- 2 点x, y間の辺素パスの最大個数は局所辺連結度 <math>\lambda(x, y)</math> に一致する（メンガーの定理）。
- 任意の k 次元多面体のグラフの点連結度は k である。 (バリンスキーの定理)。
関連項目
脚注
参考文献
- B. Bollobas, Extremal Graph Theory, Academic Press, London, 1978. Dover edition, 2004, Chapter 1.
- R. Diestel, Graph Theory, GTM 173, Springer-Verlag, 3rd edition, 2005, Chapter 3.
- J. Bang-Jensen and G. Z. Gutin, Digraphs: Theory, Algorithms and Applications, 2008, Chapter 7.
