그래프의 k-연결성과 멩거 정리

그래프의 k-연결성과 멩거 정리

정의

주어진 그래프 $G$ 에 대해 컴포넌트의 수를 $\text{comp} (G)$ 라고 나타내자.

설명

1-2: 홑원소 집합인 컷셋 $\left\{ e \right\}$ 에 대해 $e$ 를 브릿지라고 정의할 수 있다. 다음의 그림에서는 $e_{5}$ 가 브릿지다.

1

2-3: 컴플리트 그래프 $K_{n}$ 의 연결성은 자명하게도 $\kappa \left( K_{n} \right) = n-1$ 이다.

20200422\_164411.png

위 그림의 그래프를 예시로 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$ 개 존재한다.



  1. Wilson. (1970). Introduction to Graph Theory: p28. ↩︎

댓글