이번 글에서는 그래프 이론의 separating set, vertex cut, connectivity, k-connected등에 알아보겠습니다. 그리고 hypercube의 connectivity 까지 구해보도록 하겠습니다. 이번글은 가히! 그래프이론 맛집 글이라고 보셔도 됩니다. 차근차근 하나씩 시작해보겠습니다.
Separating set 또는 vertex cut
그래프 $G$가 있다고 합시다. 이 graph $G$의 vertex set을 $V(G)$라고 표시하겠습니다. $S \subset V(G)$라고 해보겠습니다. 만약에 $G-S$가 한 개보다 많은 component를 갖는다면 ( G-S가 disconnected 라면), $S$는 $G$의 separating set이라고 부릅니다. separating set은 vertex cut이라고도 부릅니다.
connectivity
그래프 $G$의 connectivity 는 $\kappa (G)$라고 표시합니다. $\kappa (G)$는 $G$의 separating set의 size 중 최소의 size를 의미합니다.
$$ \kappa(G) = \min \{ S \subset V(G) | \text{ S 는 G의 vertex cut} \} $$
이것이 의미하는 것은 뭘까요? $S \subset V(G) $의 원소의 갯수가 $\kappa(G)$보다 작다면 $G-S$는 connected 라는 의미이죠. vertex 들을 제거 해서 $G$를 disconnected 하게 만들고 싶다면 적어도 $\kappa(G)$개 만큼의 vertex를 제거해야 한다는 얘기입니다.
k-connected
그래프 $G$가 있다고 합시다. $\kappa(G) \geq k $일 때 $G$는 k-connected 라고 불리웁니다. G가 k-connected 라는 얘기는 G에서 k-1개의 vertex를 제거해도 여전히 G는 connected라는 것을 뜻합니다.
hypercube의 connectivity
이제 hypercube $Q_k = \{ x | x = (x_1,...,x_k), x_i \in \{0,1\}\}$의 connectivity 를 구해보겠습니다. $\bar{0} = (0,0,...,0) \in Q_k $라고 합시다. $N(\bar{0}) = \{ y | y=(y_1,...,y_k), \sum y_i =1 \}$ 이죠. $N(\bar{0})=k$이죠. $y \in Q_k - N(\bar{0})$이라고 합시다. 이때 $\bar{0}y$ path 가 $Q_k-N(\bar{0})$에서 존재한다고 가정합시다. 이 path를 $\bar{0}-x_1-x_2-...-y$라고 표시합니다. 그런데 $x_1 \in N(\bar{0})$이어야 하는데요. 이것은 불가능합니다. 따라서 $Q_k-N(\bar{0})$는 disconnected 합니다. 따라서 $|N(\bar{0}) =k$이므로 $\kappa(Q_k) \leq k $입니다.
이제 $\kappa(Q_k) \geq k$를 보임으로써 $\kappa(Q_k) = k$임을 보이겠습니다. 이를 위해 귀납법을 사용할게요.
$k=0$일 때 $\kappa(Q_k)=0$이고 $k=1$일때 $\kappa(Q_k)=1$임은 쉽게 보일 수 있습니다.
이제 $k\geq 2$ 일 때 $\kappa(Q_k) = k $라고 가정합시다.
$Q_{k+1} = Q_k^0 \cup Q_k^1$ 임을 알고 있죠. 여기서 $Q_k^i =\{x | x = (x_1,x_2,...,x_k,i), x_i \in \{0,1\}\}$ 입니다. $x \in Q_k^0, y\in Q_k^1$는 모든 $i=1,2,...k$에 대해 $x_i=y_i$ 일 때 $xy$ edge 가 있습니다.
이제 $S$ 를 $Q_{k+1}$의 vertex cut이라고 해보겠습니다. 경우 크게 세가지 나옵니다.
첫번째 경우. $Q_k^i-S$ 모두 connected 일 때
두번째 경우. $Q_k^0-S$가 connected 이고 $Q_k^1-S$가 disconnected 일 때
세번째 경우. $Q_k^i-S$ 모두 disconnected 일 때
첫번째 경우. $Q_k^i-S$ 모두 connected 일 때
$Q_k^i-S$모두 connected 라고 한다면 $Q-S$가 disconnected 이기 때문에 $Q_k^0$의 vertex 와 $Q_k^1$의 vertex를 잇는 모든 edge의 각 한점들을 $S$가 갖고 있어야 합니다. 방금 말한 edge의 총갯수는 $2^k$입니다. $k\geq 2$ 이므로 $|S| \geq 2^k \geq k+1$이 성립합니다.
두번째 경우. $Q_k^0-S$가 connected 이고 $Q_k^1-S$가 disconnected 일 때
$Q_k^1-S$이므로 귀납적인 가정에 의해 $|S|\geq k$ 입니다. 여기서도 두개의 경우로 나뉩니다.
1. $Q_k^0 \cap S = \emptyset$
이 때는 $Q_k^1-S$가 공집합이어야 합니다. $ |S| \geq |Q_k^1| =2^{k} \geq k+1$이 성립합니다.
2. $Q_k^0 \cap S \neq \emptyset$
이때는 $S$가 $Q_k^0$에서 vertex 갖고 이미 $Q_k^1$에서 $k$개의 vertex 를 가지므로 $|S| \geq k+1$입니다.
세번째 경우. $Q_k^i-S$ 모두 disconnected 일 때
이때 $Q_k^0-S$는 disconnected 이므로 귀납적인 가정에 의해 $|S| \geq k $입니다. $Q_k^1 -S$이 disconnected 라는 얘기는 $S$가 $Q_k^1$에서 교집합을 갖는다는 얘기입니다. 이 때 $Q_k^i$들은 disjoint 하므로 $|S| \geq k+1$입니다.