[Graph Theory] Connectivity, 2, 3-connected graph

그래프가 "잘 연결되어있다", "더 연결되어있다" 란 무슨 의미일까.

 

5.1 Connectivity

 

Definition.

Seperating set, vertex cut: a set $S \subseteq V(G)$ that $G-S$가 하나 이상의 component를 갖게 하는. 빼면 component가 늘어나게 되는 애들.

k-connected: $k$개보다 vertex가 많고, 모든 seperating set 이 사이즈가 최소 $k$다. 뭘 떼내려면 최소 $k$개 이상의 vertex는 뽑아야 한다.

Connectivity of $G$ <$\kappa(G)$>: G가 k-connected가 되게 하는 최대의 $k$. <????>

 

Fact.

$K_n$의 경우, separating set 이 없다. 뭘 뽑아도 다 연결되어있음. 하지만 maximum $k$ such that $K_n$ has more than $k$ vertices is $k=n-1$. 그래서 $K_n$의 connectivity = $n-1$.

 

Definition.

k-edge-connected: multigraph 에서 $k$개의 엣지보다 적게 제거했을 때 connected subgraph 가 유지됨. $k$개 이전까지는 connected.

edge-connectivity $\kappa'(G)$: max{k: G is k-edge-connected}. G가 k-edge-connected 를 유지하게 하는 최대한.

[$S, T$]: Set of edges from $S$ to $T$, vertex set $S$ 에서 $T$로 가는 edge 의 모임

edge cut: [$S, \overline{S}$]. $S \subset V(G)$ is a non empty set. $S$를 잡고 나머지로 가는 모든 edge. 얘네 없어지면 싹 끊어짐.

 

edge-connectivity 를 고려할 때에는, 모든 edge를 다 볼 필요 없고 저 edge cut만 보면 된다.

 

Proposition.

Every minimal disconnecting set of edges is an edge cut.

그래프를 끊는 edge의 모임 최소는 edge cut 이다.

$\textit{Proof}$

$F$가 어떤 edge set이고, $G-F$가 disconnected라고 하자. $S$가 $G-F$의 component 의 vertex set이라면, edge cut [$S, \overline{S}$] 는 F에 포함된다.

 

Theorem <Whitney>

$\kappa(G) \leq \kappa'(G) \leq \delta(G)$

끊기 위해 없애야 하는 vertex 수보다 edge수가 더 많고, 그거보다 최소 degree가 더 많다.

$\textit{Proof}$

일단 $\kappa(G) leq \kappa'(G)$. 일단 size 가 $k' = \kappa'(G)$ 짜리, 최소한인 smallest edge cut [$S, \overline{S}$] 이 있다 치자. 만약 모든 $S$가 $\overline{S}$랑 neighbor 관계가 있었다 해도 최대한 $k' \geq |S||\overline{S}|$니까, $k' \geq |S||\overline{S}| \geq |V(G)|-1 \geq \kappa(G)$ 가 성립.

비슷한 한편으로 $x \in S,  y \in \overline{S}$ 이고 $xy \notin E(G)$. 둘 다 $S$에 있지만 서로는 모르는 사이인 $x, y$를 생각해보자. [$S, \overline{S}$] 에 있는 edge $e$는 최소한 $\{x, y \}$에는 endpoint가 없을 거다. 서로 반대편에 있지만 edge는 없던 애들을 가상의 edge로 만들어서 $T$에 추가해보자. 그러면 $T \leq k' = |[S, \overline{S}]|$가 되고, $x, y$는 $G-T$에서 다른 component에 속하게 된다. 그러니까 $\kappa(G) leq \kappa'(G)$.

 

Definition.

vertex k-split: $G$ 중의 하나의 vertex $x$ 와 adjacent vertices $x_1$, $x-2$ 를 $N_H(x_1) \cup N_H(x_2) - N_G(x) \cup \{x_1, x_2\}$ 이고 $d_H(x_i) \geq k$가 되게 만든 그래프 $H$. 하나 있던 애들 찢어서 둘로 만들었을 때, 찢어놓은 애의 최소 degree 가 $k$보다 많게 만듦.

 

Lemma

$H$ 가 $k$-connected graph $G$를 vertex k-split 해서 만든 그래프 $Rightarrow$ H 도 $k$-connected.

$k$-split을 하면 connected graph 를 만들 수 있다.

$\textit{Proof}$

$x$를 $x_1$, $x_2$로 찢었다고 치고, $S$를 $H$의 vertex cut이라 치자. $x_1, x_2$ 둘 다 $S$에 포함이면 어차피 $x$가 $S$에 있는 거나 마찬가지니까, $|S| \geq k+1$이다. $x$는 어쨌거나 edge가 $d_H(x_1) $이나 $d_H(x_2)$보다는 많을테니까.

만약에 $H-S$ 가 $x_1$이나 $x_2$나 $x_1x_2$사이의 edge를 component로 가졌다면, $S$는 $N_H(x_1)$이나 $N_H(x_2)$나 $N_G(x)$를 포함하니까, 이것도 $|S| \geq k$다.

만약에 $\{x_1, x_2 \}$가$G-S$에 있다면, $S \cap \{x_1, x_2\} = \emptyset$ 이고 $S$가 $G$의 vertex cut이다. 만약 $|S \cap \{x_1, x_2\}| = 1$이라면, $S \backslash \{x_1, x_2\} \cup \{x\}$ 가 $G$의 vertex cut이다. 어찌됐건 $|S| \geq k$고, 그래서 $H$는 $k$-connected.

 

5.2. 2-connected graph

 

Definition

Subivision of an edge: edge $uv$를 $w$를 추가해서 path $u,, w, v$ 로 바꾼다. edge를 찢고 그 사이에 vertex하나 준다.

 

Fact.

$d(v) \geq 2$ 이고 $d(u) \geq 2$인 상황이라면, subdivison 은 vertex 2-split의 한 예시다. $u$나 $v$를 쪼개서 edge 를 할당한 케이스니까. 그러니까 일단 vertex기준으로 2-connectedness가 유지가 된다.

 

Lemma

Edge-subdivision 은 2-edge-connectedness 를 보존한다.

Edge-subdivision 을 계속 하면 2-edge-connected graph를 만들 수 있다.

$\textit{Proof}$

2-edge-connected 인 $G$를 고려하고, 여기에 edge-subdivision 을 먹인 $H$를 생각하자.

일단 cut-edge에 있는 들은 cycle에 속해있는 애들이 아님. 그러니까 $G$의 모든 edge는 cycle에 속함.

2-edge-connected 면 connected이고, cycle임.

그러니까 $H$에 edge들도 cycle에 속함. $H$도 connected되어있고, cut-edge가 없다.

 

Fact.

component를 떠올려봐. 얘는 완전히 connected야.

어차피 모든 그래프들은 disjoint union of component들이니까, 잘 상상해보면

모든 connected graph 들은 2-connected-graph 에다가 계속 edge를 추가해나가서 얻을 수 있는 거 아닐까.

그래서 2-connected graph, 즉 lack of cut-vertex 는 중요한 개념이다.

 

Definition

block: maximal connected subgraph of $G$, cut-vertex가 없는. cut vertex가 없는 하나의 뭉치.

(component: connected subgraph maximal, clique: 싹 다 연결되어있어야 함)

 

그런 의미에서

block 은 3가지 정도 케이스가 있음. 걍 vertex 1개 OR 걍 EDGE OR maximally 2-connected subgraph. 이 중에서 2개 이상의 vertex로 이루어진 케이스는 2-connected 임. cut vertex가 없다 -> 떼내려면 2개 이상 필요하다 -> 2-connected.

어떤 edge 가 cycle에 포함되어있다면, 그 edge 는 block이 아니다. 그러니까, edge가 block이 되려면 이건 cut-edge여야 한다.

2개의 block 은 최대 1개의 vertex 를 share한다. 그게 아니면 걔네 자체가 union 하면서 더 큰 block 을 만드니까.

graph 를 block의 partition 으로 나누면, 그게 edge set이다. 

block이 나눈다는 그 1개의 vertex 는 그래프 전체의 cut-vertex다.

block-cutpoint graph: cut vertex들을 모아둔 set $A$랑 block들의 모임 $B$ 에서, $a \in b$ for $a \in A$ and $b \in B$라고 했을 떄 edge $ab$를 추가해보자. 그럼 이게 바로 forest야.

그 block들 중에서 cut-vertex를 하나만 가지는 애가 있으면, 걔가 leaf-block.

 

2-<edge>-connectedness 를 유지하고, 그러한 그래프를 만들어내는 방식을 생각해보자.

 

Definition

ear: endpoints 는 $G$에 있지만 internal vertices 는 $G$에 없는 애들. $G$에 시작과 끝은 있지만 중간에는 나갔다 돌아옴

ear decomposition: decomposition $Q_0, ..., Q_k$, $Q_0$ 은 cycle 이고 $Q_i$가 $Q_0 \cup ... \cup Q_{i-1}$의 ear. 최초의 cycle로부터 양 끝점은 두고 밖에 나갔다가 돌아오는 cycle들을 추가.

Closed ear: $G$랑 딱 하나의 vertex 를 share 하는 cycle. 시작과 끝점이 같은 ear

A weak ear decomposition: decompsotion $Q_0, ..., Q_k$ 이고, $Q_0$는 cycle, $Q_i$가 $Q_0 \cup ... \cup Q_{i-1}$의 ear거나 closed ear인 경우. closed ear를 포함하는 ear decomposition

 

Theorem <Whitney>

Graph 가 2-connected $\Leftrightarrow$ an ear decomposition을 가짐.

multigraph 가 2-edge-connected $\Leftrightarrow$ a weak ear decomposition 을 가짐

2-<edge>-connectedness 는 ear decomposition 으로 쪼개기 가능. 또는 이거로 만들기 가능.

$\textit{Proof}$

<$\Leftarrow$> cycle 은 2-connected 니까 ear/closed ear을 추가하는 건 2-connectedness/2-edge-connectedness 를 유지. 왜냐하면 subdivision 으로 edge 추가하는 거랑 같으니까.

<$\Rightarrow$> $G$가 2-connected 일 때, $G$는 cycle을 포함. $H$ 가  ear decomposition 을 가지는 maximal subgraph 라고 치자. 일단 cycle이 있으니 $H$가 empty 는 아니고, 만약 $H \notequal G$면 $G$랑 $H$를 잇는 edge $uv \in E(G) \backslash E(H)$ with $u \in V(H)$가 있을 거다. 왜냐하면 $G$가 conneced니까. 그러면 2-connected 여서 $G-u$ from $v$ to $V(H)$ 인 path $P$가 있다는 뜻이다. 그런데 이 $P$에다가 $H$의 $v$를 추가하면 ear가 되는데, 아까 $H$가 maximal 이었다는 가정에 위배. 그러니까 $G=H$다.

weak ear decomposition에 대해서는 $G-uv$로 바꿔보면 금방 할 수 있을 거다.

 

Definition

digraph is strongly connected <strong>: 어떠한 $u, v \in V(D)$에 대해서도 from $u$ to $v$인 <directed> path가 있다. 어떻게든 $u$에서 $v$로 가는 path가 있을 때.

 

Corollary <Robbins>

multigraph 는 strong orientation $\Leftrightarrow$ 2-edge-connected

2-edge connected 면 뭔 짓을 해도 두 vertex 사이에 길이 있다.

$\textit{Proof}$

<$\Rightarrow$> cut-edge가 한 개 밖에 없으면 둘 사이 왔다갔다 못돌아오니까 오류

<$\Leftarrow$> $G$의 weak ear decomposition 을 생각해. initial cycle 에 orient를 줘보면 strong digraph가 나온다. 그 때마다 새로운 ear <또는 closed ear>에 $u$ to $v$의 orent 를 준다.

transitivity<$a \rightarrow b, b \rightarrow c, then a \rightarrow c$> 는 new digraph가 strong 함을 보인다. 왜냐하면 원래 있던 애들이 $u$에 닿을 수 있고, $u$도 새로운 애들에 닿을 수 있으니까, 새로 ear가 추가될 때마다 old vertices 들은 걔에 닿을 수 있다. 그러니까, $G$는 strong orientation을 가진다.

 

5.3. 3-connected graphs

 

Definition

Contraction <$G/e$>: $e$의 endpoint 를 하나의 vertex 로 바꾸고, 원래 $e$의 neighbor들로 새로운 vertex의 neighbor를 구성해서 만든 그래프. edge를 vertex로 압축해서 만드는거.

k-contractible edge: contraction 하면 $k$-connected graph 를 만드는 edge. 얘를 압축해도 여전히 k-connected.

 

Lemma <Contraction lemma, Tutte>

모든 3-connected graph $ <K_4$ 제외> 는 3-contractible edge를 가진다.

3-connected graph에서 무슨 edge를 constract해도 3-connectedness 는 유지된다.

$\textit{Proof}$

3-connected graph, vertex 최소 5개 이상의 그래프 $G$를 생각. 만약에 얘가 contractible edge가 없으면 $G/e$ 는 seperating 2-set을 가지고, 이 2개 중에 하나는 $e$를 줄여서 생긴 vertex 일거야. 나머지 영문도 모르고 온 애는 $z$라하자. If $e =xy$, $\{x, y z\}$ 가 원래 $G$의 seperating set이었겠지.

$G$의 모든 edge 중에서 하나 골랐는데 그 끝점이 딱 $x, y$이고, 거기에 companion $z$를 합치면, $G-\{x, y, z\}$가 disconnected 하게 되었을 때 생기는 maximal order의 component 하나를 $H$라 하자. 그 반대편을 $H'$이라고 하자구. $\{x, y, z\}$가 minimal separating set이니까 걔들은 $H$랑 $H'$에 다 친구가 있어야 해. 

하필 $u$라는 애가 $H'$에 있는 $z$의 친구라고 하자.

$zu$가 edge 니까, $\{z, u, v\}$ 라는 seperating set도 있을 거다. <?????>

$V(H) \cup \{x, y\}$로 induce 된 subgraph of $G$ 는 connected 야. 여기에서 $v$를 없앤다고 해도 $V(H) \cup {x, y}$ 를 끊을 순 없어.

그러니까 $G[V(H) \cup \{x, y\}]-v$ 는 $G-\{z, u, v\}$ 의 component 중에 있고, 걔는 $H$보다 vertex가 많아.

이러면 $\{x, y, z\}$의 선택에 contradiction. 그러니까 $G$는 3-contractible edge를 가진다.

 

Theorem

3-connected $\Leftrightarrow$ $K_4$ 에 vertex 3-split$을 반복해서 얻는 그래프.