連結グラフ
連結グラフ（れんけつグラフ, connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。極大で連結な部分グラフは、連結成分という。
有向グラフが強連結であるとは、グラフ上の任意の2点間に有向路が存在することである。極大で強連結な部分グラフは、強連結成分という。
連結なグラフGから、ある頂点を取り除くと、Gが非連結になるとき、その頂点を切断点または関節点という。また、Gから、ある辺を取り除くと、Gが非連結になるとき、その辺を切断辺または橋という。
グラフがどの程度、かたく結びついているかを示す尺度として、点連結度（あるいは単に連結度）と辺連結度がある。また、グラフ全体の連結度に対して、二つの点の間の連結性を示す尺度として、局所連結度がある。
目次 |
[編集] 点連結度
グラフGから、k個の頂点を取り除いてGを非連結にする操作を、k-点切断という。Gをk-点切断するkのうち、最小のkを点連結度または単に連結度という。k連結グラフ(k-connected graph)は、点連結度がk以上のグラフのことを指す。点連結度は、κ(G), χ(G)等で表すことが多い。
グラフGから（もし存在すれば）辺xyを除いたグラフにおいて二つの頂点x, yを分離するために必要な頂点の個数を s とする（頂点の集合Sがx, yを分離するとは、GからSを取り除いたグラフにおいてxとyの間に道が存在しないことをいう）。このとき、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個の辺を取り除いてGを非連結にする操作を、k-辺切断という。Gをk-辺切断するkのうち、最小のkを辺連結度という。k辺連結グラフ(k-edge-connected graph)は、辺連結度がk以上のグラフのことを指す。辺連結度は、λ(G), χ'(G)等で表すことが多い。
[編集] 性質
- グラフGの最小次数をδ(G)で表すと、κ(G)≦λ(G)≦δ(G)。
- 任意のl<m<nに対し、κ(G)=l, λ(G)=m, δ(G)=n を満たすグラフGが存在する。
- 2連結グラフの任意の頂点は、閉路上にある。
- グラフの二点x, yを結ぶ互いに独立な道の最大個数は局所連結度κ(x, y)に一致する（メンガーの定理）。
[編集] 関連項目
[編集] 参考文献
- 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.
