連結グラフ

連結グラフ（れんけつグラフ）は、グラフ上の任意の2頂点間に路が存在するグラフのことである。極大で連結な部分グラフは、連結成分という。

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

連結なグラフGから、ある頂点を取り除くと、Gが非連結になるとき、その頂点を切断点または関節点という。また、Gから、ある辺を取り除くと、Gが非連結になるとき、その辺を切断辺または橋という。

グラフがどの程度、かたく結びついているかを示す尺度として、点連結度（あるいは単に連結度）と辺連結度がある。k連結グラフは、点連結度がk以上のグラフのことを指す。

点連結度

グラフGから、k個の頂点を取り除いてGを非連結にする操作を、k-点切断という。Gをk-点切断するkのうち、最小のkを点連結度という。点連結度は、κ(G), χ(G)等で表すことが多い。

辺連結度

グラフGから、k個の辺を取り除いてGを非連結にする操作を、k-辺切断という。Gをk-辺切断するkのうち、最小のkを辺連結度という。辺連結度は、λ(G), χ'(G)等で表すことが多い。

性質

• グラフGの最小次数をδ(G)で表すと、κ(G)≦λ(G)≦δ(G)
• 任意のl<m<nに対し、κ(G)=l, λ(G)=m, δ(G)=n を満たすグラフGが存在する
• 2連結グラフの任意の頂点は、閉路上にある