連結グラフのソースを表示

'''連結グラフ'''（れんけつグラフ、[[英語|英]]: ''connected graph''）は、グラフ上の任意の2頂点間に[[道 (グラフ理論)|道]]が存在する[[グラフ理論|グラフ]]のことである。連結でないグラフを'''非連結グラフ''' (''disconnected graph'') と呼ぶ。極大で連結な部分グラフは、'''連結成分''' (''connected component'') という。

== 連結度 ==
グラフがどの程度かたく結びついているかを示す不変量として連結度があり、主に'''点連結度''' (''vertex-connectivity'') と'''辺連結度''' (''edge-connectivity'') に分類される。また、グラフ全体の連結度 (それぞれ、辺連結度) について、指定した2点間に対する連結性を示す不変量として、'''局所点連結度''' (''local vertex-connectivity'') (それぞれ、'''局所辺連結度''' (''local edge-connectivity'') ) がある。点連結度 (それぞれ、局所点連結度) は単に'''連結度''' (それぞれ、'''局所連結度''') と呼ぶ場合があることを付記しておく。

=== 点連結度 ===
グラフ {{mvar|G}} から取り除くと非連結になるような {{mvar|k}} 個の頂点集合を'''{{mvar|k}}-点切断'''とよぶ。{{mvar|G}} において{{mvar|k}}-点切断が存在するような最小の {{mvar|k}} を'''点連結度'''または連結度とよび、<math>\kappa(G), \chi(G)</math>で表す。特に、1-点切断を'''切断点'''  (''cut vertex'')  または'''関節点''' (''articulation point'')  とよぶ。[[k-頂点連結グラフ|{{mvar|k}}-連結グラフ]] (''{{mvar|k}}-connected graph'') は点連結度が {{mvar|k}} 以上のグラフである。

{{mvar|G}} から {{mvar|S}} を取り除いたグラフにおいて {{mvar|x}} と {{mvar|y}} の間に道が存在しないことを頂点の集合 {{mvar|S}} が {{mvar|x, y}} を'''分離'''するという。グラフ {{mvar|G}} から（もし存在すれば）辺 {{mvar|xy}} を除いたグラフにおいて、二つの頂点 {{mvar|x, y}} を分離するために必要な頂点の個数を {{mvar|s}} とするこのとき、{{mvar|x, y}}が隣接していないなら {{mvar|s}} を、{{mvar|x, y}} が隣接しているなら {{math|''s'' + 1}} を {{mvar|x, y}} の'''局所連結度'''といい、{{math|''&kappa;''(''x'', ''y'')}} 等で表すことが多い。点連結度は局所連結度の最小値と一致する。

グラフ {{mvar|G}} のある因子が {{mvar|k}}連結なら、{{mvar|G}} 自身も {{mvar|k}} 連結となる。{{mvar|G}} が {{mvar|k}} 連結で、{{mvar|G}} の自分自身を除いた因子が {{mvar|k}} 連結でないとき（つまり、{{mvar|G}} から一つでも辺を取り除くと {{mvar|k}} 連結でないとき）、{{mvar|G}} を '''極小 {{mvar|k}} 連結''' (''minimally {{mvar|k}}-connected'') という。

=== 辺連結度 ===
グラフ {{mvar|G}} から取り除くと非連結になるような {{mvar|k}} 本の辺集合を'''{{mvar|k}}-辺切断''' (または[[カット_(グラフ理論)|k-カット]]) とよぶ。{{mvar|G}} において {{mvar|k}}-辺切断が存在するような最小の {{mvar|k}} を'''辺連結度'''とよび、<math>\lambda(G), \chi'(G)</math>で表す。特に、1-辺切断を'''切断辺'''または'''橋''' (''bridge'') とよぶ。[[k-辺連結グラフ|{{mvar|k}}-辺連結グラフ]]  (''{{mvar|k}}-edge-connected graph'') は、辺連結度が {{mvar|k}} 以上のグラフのことを指す。

点連結度と同様に、2点 {{mvar|x, y}} を分離する辺集合の大きさの最小値として、'''局所辺連結度'''が定義され {{math|''&lambda;''(''x'', ''y'')}} で表記される。

また、 <math>\lambda(G) = \min_{x, y \in V(G)} \lambda(x, y) </math> となることを付記しておく。

== 有向グラフと連結度 ==
[[有向グラフ]]において、無向グラフと同様に連結度の対応物が定義されている<ref>点連結度の対応物と辺連結度の対応物についての用語の和訳は定訳が不明であるため直訳した。</ref>。

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

=== 点連結度の対応物 ===
ある2点 {{mvar|x, y}} を指定したとき、除去することで {{mvar|x, y}} のどちらを始点にしても有向路が存在しなくなるような点集合の大きさの最小値として、{{mvar|x, y}} の局所点強連結度 (''local vertex-strong connectivity'') が定義される。 また、局所点強連結度の最小値を点強連結度 (''vertex-strong connectivity'') と呼ぶ。点強連結度が {{mvar|k}} 以上のグラフを {{mvar|k}} 点強連結グラフ ({{mvar|k}}-''strongly connected graph'') 、または、
{{mvar|k}} 強グラフ ({{mvar|k}}-''strong graph'') と呼ぶ。

=== 辺連結度の対応物 ===
ある2点 {{mvar|x, y}} を指定したとき、除去することで {{mvar|x, y}} のどちらを始点にしても有向路が存在しなくなるような辺集合の大きさの最小値として、
{{mvar|x, y}} の局所有向辺強連結度 (''local arc-strong connectivity'') が定義される。また、局所有向辺強連結度の最小値を有向辺強連結度 (''arc-strong connectivity'') と呼ぶ。有向辺強連結度が {{mvar|k}} 以上のグラフを {{mvar|k}} 有向辺強連結グラフ ({{mvar|k}}-''arc''-''strongly connected graph'') 、または、{{mvar|k}} 有向辺強グラフ ({{mvar|k}}-''arc''-''strong graph'') と呼ぶ。

== 連結度の一般化 ==
* [[要素連結度]]
* [[節点領域連結度]]
* [[集合間連結度]]

== アルゴリズム ==
* [[k点連結成分分解]]
* [[k辺連結成分分解]]
* [[強連結成分分解]]

== 性質 ==
* グラフ {{mvar|G}} の最小[[次数 (グラフ理論)|次数]]を {{math|''&delta;''(''G'')}} で表すと、{{math|''&kappa;''(''G'') ≦ ''&lambda;''(''G'') ≦ ''&delta;''(''G'')}}。
* 任意の {{math|''l'' < ''m'' < ''n''}} に対し、{{math|''&kappa;''(''G'') {{=}} ''l'', ''&lambda;''(''G'') {{=}} ''m'', ''&delta;''(''G'') {{=}} ''n''}} を満たすグラフ {{mvar|G}} が存在する。
* 2連結グラフの任意の頂点は、[[閉路]]上にある。
* 2 点 {{mvar|x, y}} 間の互いに独立な道 (点素パス) の最大個数は局所連結度 {{math|''&kappa;''(''x'', ''y'')}} に一致する（[[メンガーの定理]]）。
* 2 点 {{mvar|x, y}} 間の辺素パスの最大個数は局所辺連結度 {{math|''&lambda;''(''x'', ''y'')}} に一致する（[[メンガーの定理]]）。
* 任意の {{mvar|k}} 次元多面体のグラフの点連結度は {{mvar|k}} である。 ([[バリンスキーの定理]])。

== 注釈・出典 ==
{{Reflist}}

== 参考文献 ==
* {{cite book
    |last1              = Bang-Jensen
    |first1             = J.
    |last2              = Gutin
    |first2             = G. Z.
    |year               = 2008
    |title              = Digraphs: Theory, Algorithms and Applications
    |chapter            = Chapter 7. Global Connectivity
    |url                = {{google books|CR_oBwAAQBAJ|page=345|plainurl=yes}}
    |publisher          = Springer-Verlag
    |isbn               = 978-1-85233-611-0
    |mr                 = 
    |zbl                = 
    |ref                = harv
}}
* {{cite book
    |last1              = Bollobás
    |first1             = B.
    |year               = 2004
    |origyear           = 1978
    |title              = Extreamal Graph Theory
    |chapter            = Chapter 1. Connectivity
    |edition            = Dover
    |url                = {{google books|fkLDAgAAQBAJ|page=1|plainurl=yes}}
    |publisher          = Academic Press
    |isbn               = 0-486-43596-2
    |mr                 = 
    |zbl                = 
    |ref                = harv
}}
* {{cite book
    |last1              = Diestel
    |first1             = R.
    |year               = 2005
    |title              = Graph Theory
    |chapter            = Chapter 3. Connectivity
    |edition            = Third
    |series             = Graduate Textbooks in Mathematics
    |volume             = 173
    |url                = {{google books|aR2TMYQr2CMC|page=55|plainurl=yes}}
    |publisher          = Springer-Verlag
    |isbn               = 3-540-26183-4
    |mr                 = 
    |zbl                = 
    |ref                = harv
}}

== 関連項目 ==
=== 数学的対象と性質 ===
* [[カット (グラフ理論)]]
* [[k-頂点連結グラフ]]
* [[k-辺連結グラフ]]

=== 定理 ===
* [[メンガーの定理]]
* [[最大フロー最小カット定理]]
* [[バリンスキーの定理]]

=== その他 ===
* [[連結空間]]
* [[素集合データ構造]]

{{Graph Theory-footer}}

{{DEFAULTSORT:れんけつくらふ}}
[[category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]