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

履歴の双方向閲覧

← 古い編集新しい編集 →

削除された内容追加された内容

ビジュアルウィキテキスト

インライン

2007年5月28日 (月) 12:03時点における版

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

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

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

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

点連結度

グラフ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)等で表すことが多い。

性質

グラフGの最小次数をδ(G)で表すと、κ(G)≦λ(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.

@@ 1行目: / 1行目: @@
-'''連結グラフ'''（れんけつグラフ）は、グラフ上の任意の2頂点間に[[路]]が存在する[[グラフ理論|グラフ]]のことである。極大で連結な部分グラフは、'''連結成分'''という。
+'''連結グラフ'''（れんけつグラフ, ''connected graph''）は、グラフ上の任意の2頂点間に[[路]]が存在する[[グラフ理論|グラフ]]のことである。極大で連結な部分グラフは、'''連結成分'''という。
 有向グラフが'''強連結'''であるとは、グラフ上の任意の2点間に有向路が存在することである。極大で強連結な部分グラフは、'''強連結成分'''という。
@@ 5行目: / 5行目: @@
 連結なグラフGから、ある頂点を取り除くと、Gが非連結になるとき、その頂点を'''切断点'''または'''関節点'''という。また、Gから、ある辺を取り除くと、Gが非連結になるとき、その辺を'''切断辺'''または'''橋'''という。
-グラフがどの程度、かたく結びついているかを示す尺度として、'''点連結度'''（あるいは単に'''連結度'''）と'''辺連結度'''がある。'''k連結グラフ'''は、点連結度がk以上のグラフのことを指す。
+グラフがどの程度、かたく結びついているかを示す尺度として、'''点連結度'''（あるいは単に'''連結度'''）と'''辺連結度'''がある。
 ==点連結度==
-グラフGから、k個の頂点を取り除いてGを非連結にする操作を、'''k-点切断'''という。Gをk-点切断するkのうち、最小のkを'''点連結度'''という。点連結度は、κ(G), χ(G)等で表すことが多い。
+グラフ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を'''辺連結度'''という。辺連結度は、λ(G), χ'(G)等で表すことが多い。
+グラフGから、k個の辺を取り除いてGを非連結にする操作を、'''k-辺切断'''という。Gをk-辺切断するkのうち、最小のkを'''辺連結度'''という。'''k辺連結グラフ(k-edge-connected graph)'''は、辺連結度がk以上のグラフのことを指す。辺連結度は、λ(G), χ'(G)等で表すことが多い。
 ==性質==
@@ 17行目: / 19行目: @@
 *任意の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:グラフ理論|れんけつくらふ]]