連結グラフ

連結グラフとは

連結グラフとは、任意の2つの頂点間に道が存在するグラフを指します。もし道が存在しない場合、そのグラフは非連結グラフと呼ばれます。連結性はグラフ理論において重要な概念であり、特に「連結成分」と呼ばれる極大かつ連結な部分グラフが重要な役割を果たします。

連結度

連結度は、グラフがどの程度結びついているかを示す不変量で、主に以下の2つに分類されます。

• - 点連結度（vertex-connectivity）
• - 辺連結度（edge-connectivity）

また、特定の2点間の連結性を示すために、局所的な連結度が定義されることもあります。これらによって、グラフの連結構造の強さや弱さを評価できます。

点連結度

グラフGにおいて、k個の頂点を取り除くことで非連結になるような最小のkを指し、これを点連結度と呼びます。具体的には、k-点切断が存在する最小のkはコンパクトに表現され、次のように示されます。

• - 点連結度:

- \\kappa(G)\、\\chi(G)

ここで、特に1-点切断によって非連結になる点を切断点（または関節点）と称します。k-連結グラフは、点連結度がk以上のグラフです。

また、グラフGから頂点の集合Sを取り除いた場合、そのグラフ内に特定の2点xとyの間の道が存在しない場合、集合Sがxとyを分離していると呼びます。局所的な点連結度は、特定の2点の間に道を存在させるために必要な頂点数として定義されます。

辺連結度

辺連結度は、k本の辺を取り除くことで非連結になってしまうような最小のkを指します。このk-辺切断は以下のように表されます。

• - 辺連結度:

- \\lambda(G)\、\\chi'(G)

特に1-辺切断される辺を「切断辺」または「橋」と呼びます。k-辺連結グラフは、辺連結度がk以上のグラフです。局所的な辺連結度も同様に定義され、安全性や堅牢性を示す指標となります。

有向グラフと連結度

有向グラフの場合は特有の連結性があり、強連結と呼ばれる概念が存在します。強連結とは、任意の2点間に有向の道が存在する状態を示し、極大な強連結部分グラフは強連結成分とみなされます。さらに、局所点強連結度や点強連結度が定義され、特定の2点間の連結性を測ります。

連結度の一般化

連結度にはより幅広い定義があり、要素連結度や節点領域連結度、集合間連結度といった異なる観点が存在します。これにより、グラフの特性をさらに詳細に解析することが可能となります。

性質と性質

グラフGにおいて、最小次数が\\δ(G)\\のことを表すと、以下のような関係が成立します：
\\kappa(G) \leq \lambda(G) \leq \delta(G)\\。
また、任意のl < m < nに対し、\\kappa(G) = l, \lambda(G) = m, \delta(G) = n\\を満たすようなグラフGが存在します。2連結グラフにおいては、任意の頂点が閉路上に位置するという特徴も持っています。

このように、連結グラフには多くの興味深い特性があり、それぞれの定義や性質はグラフ理論の研究や実用的な応用において重要な意義を持ちます。

もう一度検索