連結度(グラフ)
概要
連結度(グラフ)（vertex connectivity）とは、有限グラフを非連結にするか一頂点以下にするために除く必要がある頂点数の最小値であり、$\kappa(G)$ と書く。値が大きいほど頂点故障に対して連結性が保たれ、完全グラフでは $\kappa(K_n)=n-1$ となる。辺を除く辺連結度や位相空間の連結性とは異なり、$\kappa(G)\le\delta(G)$ を満たす。
前提知識: グラフ, 連結グラフ, 道(グラフ), 完全グラフ, 頂点の次数
定義
以下、グラフは有限単純グラフとする。$G=(V,E)$ と $X\subset V$ に対し、$G-X$ は頂点集合 $V\setminus X$ が誘導する部分グラフを表す。一頂点だけのグラフは連結、空グラフは非連結とする。
$k$ を非負整数とする。グラフ $G=(V,E)$ が $k$-連結（$k$-connected）であるとは、
- $|V|>k$ であり、
- $|X|< k$ を満たすすべての $X\subset V$ に対して $G-X$ が連結である
ことをいう。
条件 $|V|>k$ は小さいグラフ、とくに完全グラフの値を正しく定めるために必要である。これを落とすと、$K_n$ は $n$ 個未満の頂点を除いても空にならず連結なので、誤って $n$-連結と判定される。
空でないグラフ $G$ の 頂点連結度（vertex connectivity）$\kappa(G)$ とは、$G$ が $k$-連結となる最大の非負整数 $k$ である。空グラフについては $\kappa(G):=0$ と約束する。
この定義から、非連結なグラフと一頂点グラフ $K_1$ の連結度は $0$ である。二頂点完全グラフ $K_2$ の連結度は $1$ である。
同値な見方として、$\kappa(G)$ は「頂点を除いて $G$ を非連結にするか、残りを一頂点以下にするために必要な頂点数の最小値」である。完全グラフでは、非連結にする前に一頂点以下になるため、この後半の条件が必要になる。
直感――頂点故障への耐性
頂点を通信施設、辺を施設間の直接の接続とみなすと、$\kappa(G)$ はネットワークを分断するのに必要な施設故障数を測る。$\kappa(G)\ge2$ なら一頂点を失っても連結性は保たれ、$\kappa(G)\ge3$ なら任意の二頂点を失っても保たれる。単に連結であることは $\kappa(G)\ge1$ にすぎず、どの頂点が分断の弱点になるかまでは表さない。
例と反例
正整数 $n$ に対して
$$
\kappa(K_n)=n-1
$$
である。
$n=1$ では $K_1$ は0-連結であり、頂点数条件により1-連結ではないので $\kappa(K_1)=0=n-1$ である。以下 $n\ge2$ とする。
$k=n-1$ とする。$|V(K_n)|=n>n-1$ である。また、$|X|< n-1$ なら $K_n-X$ には少なくとも二頂点が残り、残った任意の二頂点は辺で結ばれているので連結である。したがって $K_n$ は $(n-1)$-連結である。
一方、$K_n$ が $n$-連結であるためには定義の第1条件 $|V(K_n)|>n$ が必要だが、実際には $|V(K_n)|=n$ である。よって $K_n$ は $n$-連結でなく、最大値は $n-1$ である。
一頂点の道 $P_1$ では $\kappa(P_1)=0$ である。$n\ge2$ では $\kappa(P_n)=1$ である。実際、$P_n$ は連結なので1-連結である。$n=2$ なら $P_2=K_2$ だから上の命題による。$n\ge3$ なら内部頂点を一つ除くと道が左右に分断されるので、2-連結ではない。
$n\ge3$ に対して $\kappa(C_n)=2$ である。一頂点を除いた $C_n$ は道グラフになって連結なので、$C_n$ は2-連結である。一方、各頂点の次数は2であり、後述の不等式 $\kappa(G)\le\delta(G)$ から $\kappa(C_n)\le2$ である。したがって等号が成り立つ。
$d\ge2$、$m\ge2$ とし、$m$ 個の $K_{d+1}$ を一つの頂点 $v$ だけで共有するように貼り合わせる。$v$ 以外の各頂点の次数は $d$、$v$ の次数は $md$ なので、最小次数は $\delta(G)=d$ である。しかし $v$ を除くと $m$ 個の成分に分かれるので $\kappa(G)=1$ である。
したがって「最小次数が大きければ頂点連結度も大きい」という逆向きの含意は成り立たない。これは $\delta(G)\ge d\Rightarrow\kappa(G)\ge d$ を破る反例である。
基本的な性質
空でない有限単純グラフ $G$ について
$$
\kappa(G)\le\delta(G)
$$
が成り立つ。ここで $\delta(G)$ は $G$ の最小次数である。
$G$ が完全グラフ $K_n$ なら、前の命題から $\kappa(G)=n-1=\delta(G)$ である。
$G$ が完全グラフでない場合を考える。最小次数をもつ頂点を $v$ とし、その隣接頂点全体を $N(v)$ とする。$G$ は完全でないので、ある頂点を適切に選べば、最小次数の頂点 $v$ に非隣接な頂点が存在するとは限らないように見えるが、実際には $\deg(v)=|V|-1$ なら最小次数が $|V|-1$ となり全頂点の次数が $|V|-1$、したがって $G$ は完全になる。よって非完全の場合は $\deg(v)<|V|-1$ であり、$v$ と異なり $v$ に隣接しない頂点 $u$ が存在する。
$N(v)$ を除いたグラフには $v$ と $u$ が残り、$v$ は孤立している。したがって $G-N(v)$ は非連結である。もし $\kappa(G)>\delta(G)$ なら、$G$ は $(\delta(G)+1)$-連結なので、濃度 $\delta(G)<\delta(G)+1$ の集合 $N(v)$ を除いても連結でなければならず矛盾する。よって
$$
\kappa(G)\le |N(v)|=\delta(G)
$$
を得る。
辺連結度との違い
辺連結度 $\lambda(G)$ は、頂点ではなく辺を除いてグラフを非連結にするために必要な最小本数を測る。有限単純グラフでは Whitney の不等式
$$
\kappa(G)\le\lambda(G)\le\delta(G)
$$
が成り立つ（Die17 §3.3）。しかし三つの値は一般に一致しない。
たとえば二つの三角形が一頂点だけを共有する蝶ネクタイ型グラフでは、共有頂点を除けば分断されるので $\kappa(G)=1$ である。一方、どの一辺を除いても各三角形内には別の道が残るため連結性は失われず、二辺を適切に除けば分断できるので $\lambda(G)=2$ である。この例は「頂点連結度と辺連結度は常に等しい」という主張を破る。
また、位相空間が連結であることや、より高いホモトピー群の消滅で測る位相的な連結性は別の概念である。本記事の $\kappa(G)$ は有限グラフから頂点を削除する操作だけを扱う。
Mengerの定理
異なる頂点 $x,y$ に対し、$x,y$ 以外の頂点集合 $S$ を除くと $x$ と $y$ が異なる連結成分に入るとき、$S$ を $x$–$y$ 頂点分離集合という。二つの $x$–$y$ 道が 内部頂点素であるとは、端点 $x,y$ 以外の頂点を共有しないことをいう。
有限グラフ $G$ の異なる非隣接頂点 $x,y$ に対し、$x$–$y$ 頂点分離集合の最小濃度は、内部頂点素な $x$–$y$ 道の最大本数に等しい。
この定理の完全証明は Die17 §3.3, Menger's theorem に譲る。仮定を非隣接頂点に限定するのは、辺 $xy$ が存在すると端点以外の頂点を除いてもその一辺の道を壊せないためである。
Mengerの定理は、頂点連結度を「切断に必要な頂点数」だけでなく「互いに独立な迂回路の本数」として読めることを示す。とくに $k$-連結グラフでは、任意の異なる非隣接二頂点の間に内部頂点素な道を $k$ 本確保できる。これは上で述べた頂点版Mengerの定理から直接従い、頂点連結度をネットワークの冗長性の尺度として使える理由を与える。
小さいグラフと流儀
- $\kappa(K_1)=0$、$\kappa(K_2)=1$ とする。
- 非連結グラフと空グラフの連結度は $0$ とする。
- 文献によっては頂点切断を「除去後が非連結になる集合」だけで定義し、完全グラフを別途 $\kappa(K_n)=n-1$ と約束する。本記事は「非連結または一頂点以下にする」と述べることで、同じ値を一つの規約にまとめる。
- 無限グラフでは濃度を用いる拡張があるが、本記事の定義・最大値・Mengerの定理は有限グラフに限定する。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
