📂グラフ理論

グラフのk-連結性とメンガーの定理

定義

与えられたグラフを $G$ とし、コンポーネントの数を $\text{comp} (G)$ と表す。

エッジ-連結性

1. 次の条件を満たすエッジの集合$D \subset E(G)$を $G$ の断絶集合^{disconnecting set}と呼ぶ。 $$ \text{comp} \left( G \setminus D \right) > \text{comp}(G) $$
2. $G$ の断絶集合の中で真部分集合として断絶集合でないものを持たない断絶集合を、 $G$ のカットセット^cutsetと呼ぶ。
3. $G$ が連結グラフである時、（エッジ）カットセットの基数の最小値をエッジ-連結性$\lambda (G)$ と表す。
4. 単一要素集合のカットセット$\left\{ e \right\}$ について、$e$ をブリッジ^bridgeと呼ぶ。

バーテックス-連結性

1. 次の条件を満たすバーテックスの集合$S \subset E(G)$を $G$ の分離集合^{separating set}と呼ぶ。 $$ \text{comp} \left( G \setminus S \right) > \text{comp}(G) $$
2. $G$ が連結グラフである時、分離集合の基数の最小値をバーテックス-連結性$\kappa (G)$ と表す。
3. $\left| S \right| < k$ のすべての$S \subset V(G)$ について、$G \setminus S$が完全グラフでない連結グラフなら、$G \ne K_{k}$ を**$k$-連結グラフ**と呼ぶ。

説明

例として、完全グラフ $K_{n}$ のバーテックス-連結性は自明に $\kappa \left( K_{n} \right) = n-1$ である。

次の図では$e_{5}$ がブリッジである¹。

断絶集合

断絶集合とは、コンポーネントの数が増えるだけで、つまりグラフを切断するだけでよい。$E(G)$ は当然断絶集合だが、あまりに自明なため意味がない。次にいくつかの断絶集合を列挙する。 $$ \left\{ e_{5} \right\} \\ \left\{ e_{1}, e_{4} \right\} \\ \left\{ e_{1}, e_{2} , e_{3}, e_{4}, e_{5} \right\} $$

カットセット

簡単に言えば、一番小さい^minimal断絶集合がカットセットである。『断絶集合のうち、断絶集合でない部分集合を持たない断絶集合』のように難しく言う理由は、単に一番小さい断絶集合ではなく、多くの断絶集合を取ることによって生じる部分順序集合のセンスで一番小さいということだ。したがって、カットセットは一意である保証はなく、上の例では以下の5つがカットセットである。 $$ \left\{ e_{5} \right\} \\ \left\{ e_{1}, e_{4} \right\} \\ \left\{ e_{1}, e_{2} \right\} \\ \left\{ e_{2} , e_{3} \right\} \\ \left\{ e_{3}, e_{4} \right\} $$

エッジ-連結性

上の図のグラフが $G$ であるとすると、エッジ-連結性 $\lambda (G)$ は $\left| \left\{ e_{5} \right\} \right| =1$ のように計算される。

定義から、連結グラフは $1$-連結グラフ、すなわち何もバーテックスを除去しなかった時に連結グラフとして$k$-連結グラフが連結グラフの一般化であることがわかる。連結性 $\kappa (G)$ は $G$ が $k$-連結グラフである時、$k$ の中で最大の数としても定義される。通常、$k$-連結グラフというとこのバーテックスに対する$k$-連結グラフのことを指す。エッジに対しても $k$-(エッジ) 連結グラフを定義できるが、詳しく言及されることは少ない。しかしながらこのポストでは、説明の便宜のためにエッジを中心に説明した。

定理

最後に$k$-連結グラフに関して最も有名な次の定理を紹介する。

メンガーの定理

バーテックスの数が少なくとも$k+1$ 個のグラフ $G$ が与えられたとする。 (1)と(2)は互いに同値である。

• (1): $G$ は $k$-連結グラフである。
• (2): 任意の2つのバーテックス$u,v$ に対して、始点と終点を持ちながら素なパスが少なくとも$k$ 個存在する。

---

• ここでパスが素というのは、$u,v$ を除いてどの要素も共有しないことを意味する。