「連結グラフ」の版間の差分

追加 定義および →‎参考文献
m編集の要約なし
(追加 定義および →‎参考文献)
'''連結グラフ'''(れんけつグラフ, ''connected graph'')は、グラフ上の任意の2頂点間に[[路]]が存在する[[グラフ理論|グラフ]]のことである。極大で連結な部分グラフは、'''連結成分'''という。
 
有向グラフが'''強連結'''であるとは、グラフ上の任意の2点間に有向路が存在することである。極大で強連結な部分グラフは、'''強連結成分'''という。
連結なグラフGから、ある頂点を取り除くと、Gが非連結になるとき、その頂点を'''切断点'''または'''関節点'''という。また、Gから、ある辺を取り除くと、Gが非連結になるとき、その辺を'''切断辺'''または'''橋'''という。
 
グラフがどの程度、かたく結びついているかを示す尺度として、'''点連結度'''(あるいは単に'''連結度''')と'''辺連結度'''がある。'''k連結グラフ'''は、点連結度がk以上のグラフのことを指す
 
==点連結度==
グラフGから、k個の頂点を取り除いてGを非連結にする操作を、'''k-点切断'''という。Gをk-点切断するkのうち、最小のkを'''点連結度'''または単に連結度という。'''k連結グラフ(k-connected graph)'''は、点連結度がk以上のグラフのことを指す。点連結度は、κ(G), χ(G)等で表すことが多い。
 
グラフ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)等で表すことが多い。
 
==性質==
*任意のl<m<nに対し、κ(G)=l, λ(G)=m, δ(G)=n を満たすグラフGが存在する
*2連結グラフの任意の頂点は、[[閉路]]上にある
 
 
==参考文献==
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.
 
[[category:グラフ理論|れんけつくらふ]]
248

回編集