17. Connectivity

connected 그래프라는 건 알겠는데, 얼마나 강하게 연결돼 있는지는 어떻게 측정할까? 이 챕터가 그 답이다.

---

1. 핵심 질문

 인터넷 네트워크를 생각해 보자. 서버 하나가 고장 나도 전체가 끊기지 않으려면 어떻게 설계해야 할까? 단순히 connected라는 사실만으로는 부족하다. 얼마나 robust(굳건하고 강력한)한지를 수치로 표현해야 한다.

---

2. Bridge와 Edge Connectivity

Bridge: 제거하면 connected component 수가 늘어나는 edge.

쉽게 말하면 "이 edge 하나만 끊어도 그래프가 두 덩어리로 나뉘는" edge다.

 

예시:

A - B - C - D
    |       |
    E - F - G

 

{A, B}를 제거하면:

A   B - C - D
    |       |
    E - F - G

A가 혼자 떨어진다 → {A, B}는 Bridge

반면 {B,C}를 제거해도 B-E-F-G-D-C로 우회 가능 → Bridge 아님

 

Edge Connectivity: 그래프를 disconnect하려면 edge를 최소 몇 개 제거해야 하는가?

• Bridge가 있으면 edge connectivity = 1
• Bridge가 없으면 edge connectivity ≥ 2

---

3. Articulation Point와 Vertex Connectivity

Articulation Point (Cut Vertex): 제거하면 connected component 수가 늘어나는 vertex.

 

위 예시에서 B를 제거하면:

A   C - D
        |
E - F - G

A 혼자, C-D-G-F-E 그룹으로 나뉜다 → B는 Articulation Point

 

Vertex Connectivity: 그래프를 disconnect하려면 vertex를 최소 몇 개 제거해야 하는가?

• Articulation point가 있으면 vertex connectivity = 1

* 특이 케이스: Kₙ(완전 그래프)의 vertex connectivity = n-1 (모든 vertex를 제거해야 disconnect되므로)

---

4. k-connected와 Biconnected

k-connected: vertex connectivity ≥ k인 그래프

k	의미
1-connected	그냥 connected
2-connected (Biconnected)	vertex 1개 고장나도 connected 유지
3-connected	vertex 2개 동시에 고장나도 connected 유지
k-connected	vertex k-1개 동시에 고장나도 connected 유지

 

Biconnected = connected이고 articulation point가 없는 그래프

Biconnected는 네트워크 설계의 최소 생존 조건이다. 노드 하나가 고장 나도 나머지가 연결을 유지할 수 있다.

---

5. Menger's Theorem 

 두 정점 s, t 사이의 연결을 보는 두 가지 관점이 있다.

Cut 관점: s와 t를 분리하려면 edge를 최소 몇 개 제거해야 해?

Path 관점: s에서 t로 가는 edge-disjoint path가 최대 몇 개야?

Edge-disjoint paths: 어떤 edge도 공유하지 않는 path들

 

Menger's Theorem:

최소 ⟨s, t⟩-edge-cut 크기 = 최대 edge-disjoint path 수

 

vertex 버전도 성립:

최소 ⟨s, t⟩-vertex-cut 크기 = 최대 vertex-disjoint path 수

 

직관: s에서 t로 가는 독립적인 경로가 많을수록, 그 경로들을 전부 막으려면 더 많은 edge를 잘라야 한다. 이 두 숫자가 항상 정확히 일치한다는 게 Menger's Theorem이다.

---

6. 예제로 확인하기

S - A - T
|   |   |
B - C - D

 

edge-disjoint paths 찾기:

• S→A→T : {S, A}, {A, T} 사용
• S→B→C→D→T : {S, B}, {B, C}, {C, D}, {D, T} 사용
• 겹치는 edge 없음 → 최대 2개

최소 edge-cut 찾기:

• {A, T}, {D, T} 제거 → T로 들어오는 edge가 없어서 S와 T 분리
• edge 1개만으로는 분리 불가
• → 최소 크기 2

Menger's Theorem 성립: 2 = 2 ✅

---

7. 정리

개념	정의
Bridge	제거하면 disconnect되는 edge
Articulation Point	제거하면 disconnect되는 vertex
Edge Connectivity	disconnect에 필요한 최소 edge 수
Vertex Connectivity	disconnect에 필요한 최소 vertex 수
Biconnected	2-connected = articulation point 없음
Menger's Theorem	min-cut = max-disjoint-paths

 

판별 순서:

1. Bridge/Articulation point 있어? → connectivity = 1
2. 없으면 → 직접 최소 cut 크기 계산
3. Menger's Theorem으로 cross-check 가능