13. Directed Graphs

Directed Graph란?

Directed Graph(방향 그래프, Digraph)는 화살표로 연결된 점들의 집합이다.

인스타그램 팔로우 관계로 생각하면 쉽다.

• 내가 아이유를 팔로우하면: 나 → 아이유
• 아이유가 나를 팔로우 안 하면: 아이유 → 나 없음
• 내가 나 자신을 팔로우하면: 나 → 나 (self-loop)

수학적으로 Digraph = ⟨V, A⟩로 표현한다.

• V: vertex(점)들의 집합
• A: arc(화살표)들의 집합. A ⊆ V × V

주요 특징:

• Self-loop: 자기 자신으로 향하는 화살표 (e.g., c → c)
• Bi-directional arc: 두 vertex 사이에 양방향 화살표 (e.g., b → d이면서 d → b)
• Isolated vertex: 아무 화살표도 없는 혼자 있는 점 (e.g., e)
• Constraint: A는 집합이라서 같은 방향의 arc가 두 개 있을 수 없음

---

Walk, Path, Circuit, Cycle

Walk: 화살표를 따라 vertex를 이동하는 것. 아무 제약 없이 걷는 거라서 같은 vertex나 arc를 반복해도 된다. 길이는 arc의 개수.

Path: Walk인데 vertex를 반복하지 않는 것. 한 번 지나간 곳은 다시 못 간다.

Circuit: Walk인데 시작점과 끝점이 같은 것.

Cycle: Circuit인데 시작/끝점 외에 반복되는 vertex가 없는 것.

• b → d: Walk이자 Path (length 1)
• b → c → d: Walk이자 Path (length 2)
• b → d → b → d: Walk이지만 Path 아님 (b, d 반복)
• b → c → d → b: Cycle (length 3)

Trivial vs Nontrivial:

• Trivial path/cycle: 길이 0. 모든 vertex가 trivially 자기 자신으로 돌아올 수 있음.
• Nontrivial path/cycle: 길이 >0. 실제로 화살표를 따라 이동하는 것.

---

Walk → Path 핵심 성질

Walk가 존재하면 Path도 반드시 존재한다.

Walk가 Path가 아니라면 반드시 반복되는 vertex가 있다. 반복되는 vertex가 있다는 건 그 사이에 cycle이 있다는 뜻이고, 그 cycle을 잘라내면 더 짧은 Walk가 된다. 이 과정을 반복하면 결국 Path가 나온다.

예를 들어 b → d → b → c → d에서 d → b → c → d 부분이 cycle이니까 잘라내면 b → d라는 Path가 나온다.

---

Reachability & Distance

Reachable: v에서 w로 가는 path가 존재하면 w는 v에서 reachable하다.

Distance d(v,w): v에서 w로 가는 가장 짧은 path의 길이. path가 없으면 ∞.

예를 들어 a에서 d로 가는 방법이 a → c → d (길이 2)와 a → b → c → d (길이 3)가 있으면 d(a,d) = 2.

Nontrivially reachable: 길이 >0인 walk로 도달 가능한 것. path가 아닌 walk여도 됨. "w ≠ v이고 reachable"이랑 다를 수 있는데, self-loop가 있으면 v가 자기 자신으로부터 nontrivially reachable해지기 때문이다.

---

Strongly Connected & Subgraph

Strongly Connected: 모든 vertex에서 다른 모든 vertex로 갈 수 있는 digraph.

Subgraph: 원래 그래프의 vertex랑 arc 일부만 가져온 그래프. ⟨V', A'⟩ where V' ⊆ V, A' ⊆ A.

Induced Subgraph: vertex 집합 V'를 고르면 그 사이의 모든 arc를 자동으로 포함하는 subgraph. 내가 arc를 직접 고르는 게 아니라 vertex만 고르면 arc는 자동으로 따라온다.

예를 들어 {b, c, d}로 induced subgraph를 만들면, b와 c, d 사이에 있는 모든 arc가 자동으로 포함된다. 이 subgraph는 strongly connected이다.

---

In-degree, Out-degree & DAG

In-degree: 해당 vertex로 들어오는 arc의 수.
Out-degree: 해당 vertex에서 나가는 arc의 수.

DAG (Directed Acyclic Graph): nontrivial cycle이 없는 digraph. 시작점으로 절대 돌아올 수 없는 구조. 한 방향으로만 흘러간다.

수강신청으로 생각하면 쉽다. CS1 → CS2 → CS10처럼 선수과목 관계를 나타낼 수 있다. 뒤로 돌아가는 cycle이 없다.

• Source: in-degree가 0인 vertex. 들어오는 화살표가 없음. (e.g., CS1)
• Sink: out-degree가 0인 vertex. 나가는 화살표가 없음. (e.g., CS10)

---

Theorem 13.3: 유한한 DAG는 source와 sink가 반드시 존재한다

증명 (귀류법, sink 존재 증명):

1. sink가 없다고 가정 → 모든 vertex의 out-degree > 0
2. 아무 vertex v₀을 골라. out-degree > 0이니까 v₀ → v₁이 존재
3. v₁도 out-degree > 0이니까 v₁ → v₂가 존재
4. 이걸 무한히 반복하면 v₀ → v₁ → v₂ → … walk가 만들어짐
5. vertex가 유한하니까 무한히 걷다 보면 반드시 이미 지나간 vertex가 나옴
6. 그러면 cycle이 생겨 → DAG라는 전제에 모순!
7. 따라서 sink는 반드시 존재한다.

주의: 이 정리는 유한한 DAG에서만 성립한다. 0 → 1 → 2 → 3 → … 처럼 무한한 DAG는 sink가 없을 수 있다.

---

Tournament Graph

Tournament Graph: 모든 vertex 쌍 사이에 정확히 하나의 방향으로 arc가 있는 digraph.

리그전을 생각하면 된다. 모든 팀이 서로 한 번씩 싸우고, 무승부 없이 반드시 승패가 결정된다. 이긴 팀에서 진 팀으로 화살표를 그리면 Tournament Graph가 된다.

n개 팀이 있으면 arc의 개수는 항상 n(n-1)/2개다.

• Inconclusive (cycle 있음): H가 Y를 이기고, Y가 D를 이기고, D가 H를 이기면 cycle 발생. DAG 아님.
• Clear Winner (cycle 없음): H → Y → P → D처럼 명확한 순위가 있으면 DAG.

---

Linear Order

Linear Order (⪯): 원소들을 일렬로 나열할 수 있는 순서 관계. 자기 자신도 포함 (x ⪯ x 성립).

Strict Linear Order (≺): 자기 자신 제외 (x ≺ x 불성립).

알파벳 순서 예시:

• apple ⪯ banana ✅, apple ⪯ apple ✅
• apple ≺ banana ✅, apple ≺ apple ❌

핵심 Theorem: "Tournament graph가 DAG ⟺ strict linear order를 나타낸다"

명확한 순위가 있으면 DAG이고 strict linear order다. cycle이 생기면 DAG도 아니고 linear order도 아니다.

---

정리

• Digraph: ⟨V, A⟩. vertex(점)와 arc(화살표)로 이루어진 binary relation.
• Walk: 화살표를 따라 이동. 반복 허용.
• Path: 반복 없는 Walk.
• Cycle: 시작점으로 돌아오는 walk. nontrivial cycle은 길이 >0.
• Walk → Path: Walk에서 cycle을 제거하면 Path가 된다.
• DAG: nontrivial cycle 없는 digraph. 한 방향으로만 흘러감.
• Source: in-degree 0. Sink: out-degree 0.
• Theorem 13.3: 유한한 DAG는 source와 sink가 반드시 존재 (무한 DAG는 아닐 수 있음).
• Tournament Graph: 모든 쌍 사이에 정확히 하나의 방향으로 arc. DAG ⟺ strict linear order.