📂グラフ理論

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

定義

与えられたグラフ $G$ における コンポーネントの数を $\text{comp} (G)$ と表記しよう。

• 1-1. 次を満たすエッジの集合 $D \subset E(G)$ を $G$ の切断集合^{disconnecting set}と呼ぶ。 $$ \text{comp} \left( G \setminus D \right) > \text{comp}(G) $$

• 1-2. $G$ の切断集合の中で、切断集合でない真部分集合を持たない切断集合を$G$ のカットセット^cutsetと呼ぶ。

• 1-3. $G$ が連結グラフだとすると、（エッジ）カットセットの基数の中で最も小さい数をエッジ-連結性 $\lambda (G)$ として表される。

• 2-1. 次を満たす頂点の集合 $S \subset E(G)$ を $G$ の分離集合^{separating set}と呼ぶ。 $$ \text{comp} \left( G \setminus S \right) > \text{comp}(G) $$

• 2-3. $G$ が連結グラフだとすると、分離集合の基数の中で最も小さい数を頂点-連結性 $\kappa (G)$ として表す。

• 3. $\left| S \right| < k $ である全ての $S \subset V(G)$ について、$G \setminus S$ が連結グラフであれば、$G \ne K_{k}$ を $k$-連結グラフと呼ぶ。

説明

1-2: 単元素集合であるカットセット $\left\{ e \right\}$ について、$e$ をブリッジと定義できる。以下の図では、$e_{5}$ がブリッジである。

¹

2-3: 完全グラフ $K_{n}$ の連結性は、言うまでもなく$\kappa \left( K_{n} \right) = n-1$ である。

上記の図にあるグラフを例に**1-n.**を見てみよう：

1-1: 切断集合は、単にグラフを切断する、つまりコンポーネントの数を増やすだけでよい。$E(G)$ は明らかに切断集合になるが、あまりにも自明で意味がない。以下はいくつかの切断集合の例である。 $$ \left\{ e_{5} \right\} \\ \left\{ e_{1}, e_{4} \right\} \\ \left\{ e_{1}, e_{2} , e_{3}, e_{4}, e_{5} \right\} $$

1-2: 簡単に言えば、最も小さい切断集合がまさにカットセットである。「切断集合の中で切断集合でない真部分集合を持たない切断集合」と難しく言う理由は、単に最小の切断集合というわけではなく、多数の切断集合によって生じる部分順序集合の意味で最小であるからだ。従って、カットセットが一意であるという保証はなく、上述の例では以下の五種類のカットセットがある。 $$ \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\} $$

1-3: 図のグラフを $G$ とすると、そのエッジ-連結性 $\lambda (G)$ は $\left| \left\{ e_{5} \right\} \right| =1$ として計算される。

定義から、連結グラフは $1$-連結グラフであり、つまり何の頂点も除去しなかった場合の連結グラフとして、$k$-連結グラフは連結グラフの一般化であると理解できる。$k$ の中で最も大きい数としても、連結性 $\kappa (G)$ が定義される。通常$k$-連結グラフと言えば、この頂点に関する$k$-連結グラフを指す。しかしながら、エッジについても$k$-(エッジ) 連結グラフを定義できるが、詳細に触れられることは少ない。ただし、この投稿では説明の利便性のためにエッジを中心に説明する。

$k$-連結グラフに関する以下のよく知られた定理を紹介する。

メンガーの定理

頂点の数が少なくとも $k+1$ 個あるグラフ $G$ が与えられたとする。(1)と(2)は等価である。

• (1): $G$ は$k$-連結グラフである。
• (2): 任意の2頂点 $u,v$ を始点と終点として持ち、$u,v$ を除いて他のどの要素も共有しないパスが少なくとも$k$ 個存在する。