이번 글에서 connectivity 와 edge수의 관계, Harary graph, disconnecting set, k-edge connected, edge-connectivity에 대해 알아보겠습니다.
이 글을 읽기전에 먼저 아래의 글을 쭉 읽어오시길 바랍니다.
[그래프 이론] separating set, vertex cut, connectivity, k-connected, hypercube의 connectivity,
connectivity와 edge수의 관계
그래프 $G$가 있다고 합시다. 이것의 connectivity $\kappa(G)$에 대해 생각해보겠습니다. 어떤 $x \in V(G)$라고 합시다. 그러면 $G-N(x)$ 는 disconnected 합니다. 따라서 $\kappa(G) \leq |N(x)| $입니다. 그렇다면 $deg_{G}(x)=|N(x)|$이므로 $\kappa(G) \leq deg_G (x)$입니다. 모든 $x\in V(G)$에 대해 성립하므로 아래의 부등식또한 성립합니다.
$$\kappa(G) \leq \delta(G)$$
$\kappa ( 2 K_m ) = 0, \delta(2 K_m) =m-1$ 이므로 $\kappa(2 K_m) < \delta(2 K_m) $입니다.
k-connected 이면 $k \leq \kappa(G) $이고 $ k \leq \kappa (G) \leq \delta(G)$입니다.
$2 e(G) = \sum_{x \in V(G)} deg_G(x) \geq \sum_{x \in V(G)} \delta(G) = n \delta(G)$ 이므로 $e(G) \geq \frac{n \delta(G)}{2} \geq \frac{nk}{2} $ 입니다. 따라서 $e(G) \geq \lceil \frac{nk}{2} \rceil$
Harary graph
$k < n$라고 합시다. 단위원의 각도를 균등분할하고 그거에 맞추어서 n개의 vertex를 단위원 위에 놓습니다. 이제 Harary graph 를 정의해보겠습니다.
$k$가 짝수일때 $H_{k,n}$ 을 어떻게 만드는지 보겠습니다. 각각의 vertex 가 시계방향으로 $k/2$개의 vertex 와 adjacent하게 그리고 반대방향으로 $k/2$개의 vertex와 adjacent 하게 두면 만들어집니다.
$k$가 홀수이고 $n$이 짝수일 때 만드는 방법 보겠습니다. 각각의 vertex가 시계방향으로 $(k-1)/2$개의 vertex와 adjacent 하게끔 그리고 반대방향으로 $(k-1)/2$개의 vertex와 adjacent하게끔 만듭니다. 그리고 각각의 vertex 와 정확히 반대 방향에 있는 vertex 와 adjacent하게 둡니다.
$k$와 $n$이 홀 수 일때 만드는 방법 알아보겠습니다. vertex들을 modulo n 으로 index 합니다. $H_{k-1, n}$으로 부터 각각의 vertex $i$에 대하여 $i$와 $i+\frac{(n-1)}{2}$를 adjacent하게끔 edge를 만듭니다.
disconnecting set,k-edge connected, edge-connectivity
그래프 $G$가 있다고 합시다. $F \subset E(G)$라고 합시다. $G-F$가 한개 보다 많은 component 를 가질 때 $F$를 disconnecting set 이라고 부릅니다. 만약에 모든 disconnecting set 이 적어도 k개의 edge를 갖는다면 $G$를 k-edge connected 라고 부릅니다. edge-connectivity 는 $\kappa \prime (G)$이라고 표시하며 disconnecting set 이 가질 수 있는 최소의 size를 의미합니다.
$S,T \subset V(G)$일 때 $[S,T]$를 정의하겠습니다. $[S,T]$는 $S$와 $T$에 동시에 matching 하는 edge를 모아둔 set을 의미합니다. edge cut 은 $[S, \bar{S}]$ 형태의 edge set을 의미합니다. $\bar{S} = V(G)-S$입니다.
Edge cut이 disconnecting 인 이유
$[S, \bar{S}]$를 $G$의 edge cut이라고 부릅니다.$H=G-[S,\bar{S}]$이라고 합시다. $u,v$를 $H$위의 vertex라고 합시다. 이 때 $u \in S$이고 $v \in \bar{S}$라고 합시다. 만약에 $uv$ path 가 $H$위에 있다고 합시다. 이 path를 $u=v_0 - v_1 -v_2 -...-v_{n-1}-v = v_n$이라고 표시합시다. $i\star = \max\{ j | v_j \in S\}$라고 합시다. 그러면 $i\star <n$이죠. 그렇게 되면 $v_i* v_{i*+1} \in E[H]$인데요 $v_{i*+1} \in \bar{S}$이므로 모순입니다.
minimal disconnecting set이 edge cut인 이유
$F$를 그래프 $G$의 disconnecting set 이라고 합시다. $G-F$에 대해 생각해봅시다. $G-F$는 당연히 disconnected 이겠지요. $H$를 $G-F$의 component 중의 하나라고 합시다. 그러면 $[V[H], \bar{V[H]}] \subset F$이 됩니다. 왜일까요? $[V[H], \bar{V[H]}] \subset F$가 아니라면 $xy \in E[G]$이고 $xy \notin F$인 $x\in V[H], y \in \bar{V[H]}$가 존재합니다. 그래서 $xy$가 $G-F$에 존재하게 됩니다. 그러므로 모순이지요. 따라서 $[V[H], \bar{V[H]}] \subset F$입니다. $F$가 minimal 이라면 $F=[V[H], \bar{V[H]}]$가 성립합니다.
edge connectivity 와 minimum degree의 관계
$v$를 $deg_G(v) = \delta(G)$인 vertex라고 합시다. 그리고 $F= \{ e \in E[G] | e \text{ is incident to $v$} \}$라고 합시다. 그러면 $G-F$는 disconnected 입니다. 따라서 $\kappa \prime (G) \leq |F| = \delta(G)$ 입니다.