14. Digraphs and Relations

이번 챕터는 저번 Digraph에 이어서, 화살표 집합(relation)에 규칙을 부여하는 이야기다.
Digraph가 "그림"이라면, Relations는 그 그림이 어떤 성질을 만족하는지 따지는 것.

---

Binary Relation이란?

집합 S가 있을 때, S × S의 부분집합이 binary relation R이다.

S = {1, 2, 3}이면 S × S는 모든 ordered pair (1,1), (1,2), ... 인데, 거기서 일부를 골라낸 것.

Digraph로 표현하면:

• S = vertex 집합
• R = arc 집합

R(x,y)가 성립한다 = x → y 화살표가 있다.

---

성질 1: Transitivity (이행성)

x→y 이고 y→z 이면, x→z 도 반드시 있어야 한다

쉽게 말하면 중간을 건너뛰는 직접 연결이 있는지 여부를 확인하는 것이다.

 

예시

• < (less-than): 1 < 2이고 2 < 3이면 1 < 3. ✅ transitive
• pred (predecessor, n = m+1): 0→1, 1→2인데 0→2가 없다. ❌ not transitive

---

성질 2: Reflexivity (반사성)

모든 x에 대해 R(x,x) 가 성립한다 (self-loop)

종류	정의	예시
Reflexive	모든 x에 self-loop	≤ (x ≤ x 항상 참)
Irreflexive	어떤 x에도 self-loop 없음	< (x < x 항상 거짓)
(둘 다 아님)	어떤 건 있고 어떤 건 없음	가능

reflexive도 irreflexive도 아닌 경우가 존재한다는 점을 주의하자.

 

예시) R = {⟨1,1⟩, ⟨1,2⟩, ⟨2,3⟩} 

reflexive가 되려면 모든 vertex에 self-loop이 있어야 하는데 2랑 3에 없으니까 reflexive 아님.

irreflexive가 되려면 어떤 vertex에도 self-loop이 없어야 하는데 1에 있으니까 irreflexive도 아님.

---

성질 3: Symmetry (대칭성)

x→y 이면 y→x 도 성립한다

 

세 가지 변형이 있어서 헷갈리기 쉽다:

종류	조건	self-loop	예시
Symmetric	x→y ⟹ y→x	허용	"is married to"
Antisymmetric	x→y ∧ y→x ⟹ x = y	허용	≤
Asymmetric	x→y ⟹ ¬(y→x)	불가	<

 

핵심 차이:

• antisymmetric: "양방향이면 같은 원소" → self-loop은 ok
• asymmetric: "양방향 자체가 불가능" → self-loop도 금지 (irreflexive 포함)

---

Closure: 빠진 쌍 채워넣기

어떤 relation이 특정 성질을 안 갖고 있을 때, 최소한으로 쌍을 추가해서 그 성질을 만족시키는 것이 closure다.

Transitive Closure (R⁺)

R에서 길이 ≥ 1인 path가 있으면 R⁺(x,y)가 성립한다.

pred = {0→1, 1→2, 2→3}
pred⁺ = {0→1, 0→2, 0→3, 1→2, 1→3, 2→3}
      = lessThan (<)

Reflexive Closure

self-loop을 모든 vertex에 추가한다.

reflexive closure of R = R ∪ {⟨x,x⟩ : x ∈ S}

Reflexive, Transitive Closure (R*)

길이 ≥ 0인 path가 있으면 R*(x,y) 성립. (0이면 자기 자신)

R⁺ = path 길이 1 이상 ("한 번 이상 이동")
R* = path 길이 0 이상 ("이동 안 해도 됨")

 

CS 응용: R이 프로그램의 "한 단계 실행"이라면, R(s_start, s_halt)는 *"halt 상태에 도달 가능한가?"** 를 묻는 것이다.

---

핵심 관계 유형 1: Equivalence Relation

Reflexive + Transitive + Symmetric 세 가지를 모두 만족하면 equivalence relation.

왜 중요한가?

equivalence relation은 집합을 겹치지 않게 쪼개는 partition을 만들어준다.

 

예시: "같은 고향 출신" 관계

• Reflexive: 나와 나는 같은 고향 ✅
• Transitive: A,B 같은 고향 ∧ B,C 같은 고향 → A,C 같은 고향 ✅
• Symmetric: A,B 같은 고향 → B,A 같은 고향 ✅

자동으로 "서울팀", "부산팀" ... 으로 나뉘어진다. 이게 equivalence class.

Partition ↔ Equivalence Relation (Theorem 14.2)

partition의 3 조건:

1. Non-empty: 빈 block 없음
2. Mutually Disjoint: 겹치는 block 없음
3. Exhaustive: 모든 원소 포함

R-T-S 각각이 이 조건을 보장:

• Reflexive → Non-empty + Exhaustive
• Transitive + Symmetric → Disjoint

응용: SCC (Strongly Connected Components)

Mutual Reachability R_mutual 을 정의하자:

R_mutual(x,y) ⟺ R*(x,y) ∧ R*(y,x)

이 관계는 equivalence relation이고, 그 equivalence class들이 바로 SCC다.

SCC들을 super-vertex로 묶으면 DAG (Condensation Graph) 가 된다.

---

핵심 관계 유형 2: Partial Order

Reflexive + Transitive + Antisymmetric → partial order.

Equivalence relation과 딱 하나 다르다. Symmetric → Antisymmetric.

왜 "partial"인가?

비교 불가능한(incomparable) 원소가 있을 수 있기 때문이다.

예시: {0,1,2}의 부분집합에 대한 ⊆ 관계
{0}과 {1}은 어느 쪽도 다른 쪽의 부분집합이 아니다. 비교 자체가 안 된다.

Linear Order (Total Order)

모든 쌍이 비교 가능한 partial order.

• ≤ on integers → linear order ✅
• ⊆ on power set → not linear order ❌

Strict Partial Order

Irreflexive + Antisymmetric + Transitive. (reflexive 버전의 strict 변형)

DAG와의 연결

• Strict partial order의 digraph = DAG
• 어떤 partial order도 어떤 DAG의 R*

선수과목 예시:

DAG R = 즉각 선수과목 관계
R⁺   = "반드시 먼저 들어야 함" (strict partial order)
R*   = "먼저 듣거나 동시에 들어도 됨" (partial order)

---

정리 한 눈에 보기

성질 조합	관계 유형	대표 예시
R + T + Symmetric	Equivalence Relation	"같은 반", "합동", SCC
R + T + Antisymmetric	Partial Order	≤, ⊆, 선수과목
I + T + Antisymmetric	Strict Partial Order	<, ⊂, DAG
R + T + A + 모든 쌍 비교 가능	Linear (Total) Order	≤ on integers

• R⁺: Transitive closure, path 길이 ≥ 1
• R*: Reflexive Transitive closure, path 길이 ≥ 0