📂그래프이론

그래프의 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: 쉽게 말해서 제일 작은^minimal 단절 집합이 바로 컷셋이다. ‘단절 집합 중 단절 집합이 아닌 진부분집합을 갖지 않는 단절 집합’과 같이 어렵게 말하는 이유는 단순히 그냥 제일 작은 단절 집합이 아니라 수많은 단절집합을 잡음으로써 생기는 부분순서 집합의 센스에서 제일 작다는 것이다. 따라서 컷셋은 유일하다는 보장이 없으며, 위 예시에서의 컷셋은 아래의 다섯가지다. $$ \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$-연결 그래프가 연결 그래프의 일반화임을 알 수 있다. 연결성 $\kappa (G)$ 는 $G$ 가 $k$-연결 그래프일 때 $k$ 중 가장 큰 수로도 정의된다.보통 $k$-연결 그래프라고 하면 이 버텍스에 대한 $k$-연결 그래프를 말한다. 에지에 대해서도 $k$-(에지) 연결 그래프를 정의할 수 있지만 자세하게 언급되는 경우는 별로 많지 않다. 다만 이 포스트에서는 설명의 편의를 위해 에지 위주로 설명했다.

$k$-연결 그래프에 대해 가장 유명한 다음의 정리를 소개한다.

멩거 정리

버텍스의 수가 최소한 $k+1$ 개인 그래프 $G$ 가 주어져 있다고 하자. (1)과 (2)는 서로 동치다.

• (1): $G$ 는 $k$-연결 그래프다.
• (2): 임의의 두 버텍스 $u,v$ 를 시점과 종점으로 가지면서 서로소인 패스가 적어도 $k$ 개 존재한다.

---

• 여기서 패스가 서로소라는 것은 $u,v$ 를 제외하고는 어떤 원소도 공유하지 않는다는 것이다.