📂그래프이론

그래프의 집합 표현

정의 ¹

두 그래프 $G_{1}$ 과 $G_{2}$ 에 대해 $V(G_{1}) \cap V(G_{2}) = \emptyset$ 이라고 하자.

1. 두 그래프의 유니언^union $G = G_{1} \cup G_{2}$ 은 버텍스 셋 $V(G_{1}) \cup V(G_{2})$ 과 에지 셋 $E (G_{1}) \cup E ( G_{2} )$ 을 가지는 그래프다.
2. 그래프 $H$ 가 그래프들의 유니언으로 표현될 수 없으면 $H$ 를 연결되었다^connected고 하고, 그 외에는 단절되었다^disconnected고 한다.
3. 단절된 그래프를 이루는 각 연결 그래프^{connected Graph}를 컴포넌트^component라 부른다.
4. 특히 에지 $b \in G$ 가 지워짐으로써 그래프가 단절되면 $b$ 를 브릿지^bridge라 부른다.

설명

이러한 정의는 위상수학에서 연결성을 정의하는 방식과 흡사하다.

순수한 그래프의 정의에서 연결성^{connectedness}은 꽤 중요한 이야기처럼 보이지만, 아이러니하게도 연결되지 않은 컴포넌트끼리는 완전히 따로 다룰 수 있기 때문에 연결 그래프만을 생각하면 된다. 연결성이 중요하지 않다기보단, 보통은 연구를 위해서 굳이 단절된 경우를 생각할 필요가 없다는 것이다.

이러한 연결성이 조명을 받는 경우는 보통 실제 데이터를 반영한 분석이나 랜덤 네트워크를 다루는 응용 네트워크 이론이다. 랜덤 네트워크가 확실히 연결 그래프가 되느냐 마느냐는 여러가지 시뮬레이션 등에서 꽤 중요한 문제다. 네트워크의 연결성이 보장되지 않은 경우을 생각해보자. 고립 노드^{isolated Node}는 대부분의 수학적 모델에서 아무런 영향력이 없으며, 고립 노드가 없더라도 네트워크의 일부만 보고 나머지는 다 버려야하는 대참사가 일어날 수 있다.

정리 ²

심플 그래프 $G$ 가 $n$ 개의 버텍스를 갖고 있다고 하자. $G$ 가 $k$ 개의 컴포넌트를 가지면 $G$ 의 에지의 갯수 $m$ 은 다음을 만족한다. $$ n-k \le m \le (n-k)(n-k+1)/2 $$

증명

Part 1. $n-k \le m$

$G$ 가 널 그래프일 때, $n=k$ 이고 $m=0$ 이므로 $ n-k = 0 \le 0 = m$ 가 성립한다.

$G$ 의 컴포넌트가 $k$ 개일 때 $n - k \ge m$ 이 성립한다고 가정해보자. $G$ 가 $k$ 개의 컴포넌트를 가지게끔하는 최소한의 에지의 수를 $m_{0}$ 라고 두자. 여기서 하나의 에지를 지우면 컴포넌트의 수는 $k+1$, 에지의 수는 $m_{0}-1$ 이 된다. 따라서 $n - (k + 1) \le m_{0} - 1$ 이고, 정리해서 $n - k \le m_{0}$ 를 얻는다.

위의 두가지 사실에서 수학적 귀납법에 따라 $n-k \le m$ 이 일반적으로 성립한다.

---

Part 2. $m \le (n-k)(n-k+1)/2$

$G$ 의 모든 컴포넌트가 컴플리트 그래프라고 하자. 그러면 그 컴포넌트 중에서는 $1 \le j \le i \le n$ 인 두 컴플리트 그래프 $K_{i}$, $K_{j}$ 가 존재할 것이다. 이 두 개의 그래프를 각각 $K_{i+1}$, $K_{j-1}$ 로 바꾸면 총 버텍스 수는 변하지 않지만 총 에지 수는 다음과 같이 변한다. $$ \left[ (i+1)i - i(i-1) \right]/2 - \left[ j(j-1) - (j-1)(j-2) \right]/2 = i - j + 1 $$ 이는 양수고, 따라서 $m$ 이 최대화되려면 $G$ 는 버텍스의 수가 $(n-k+1)$ 개인 컴플리트 그래프 하나와 고립 버텍스 $k-1$ 개를 가져야한다. 이 경우 $G$ 의 에지의 수는 $(n-k)(n-(k-1))/2$ 이므로, 원하는 결과를 얻는다.

■