관계 — 누가 누구와 이어져 있는가

8강 끝에서 곱집합 A × B — 가능한 모든 짝의 모임 — 을 만들었습니다. 그 짝들 중에서 우리가 관심 있는 것만 골라낸 것이 관계(relation)입니다.

예를 들어 사람 집합 {민준, 서연, 지호} 에서 "~는 ~를 팔로우한다"는 관계는 이런 짝들의 집합이에요.

R = {(민준, 서연), (서연, 지호), (지호, 민준), (민준, 지호)}

(a, b) ∈ R 을 a R b 라고도 씁니다. "a와 b가 이 관계에 있다"는 뜻이에요. 우리가 아는 <, =, "~의 부모이다", "같은 반이다" 모두 관계입니다.

🎮 칸을 눌러 관계를 만들어 보세요

표의 칸을 클릭하면 화살표가 생기고 사라집니다. 그때그때 이 관계가 반사적인지 · 대칭적인지 · 추이적인지 판정해 드립니다. 성질이 깨지면 어느 짝 때문에 깨졌는지도 알려 줘요.

관계의 세 가지 성질

세 가지를 모두 만족하면 동치관계(equivalence relation)라고 합니다. 동치관계는 집합을 겹치지 않는 조각으로 깔끔하게 쪼갭니다 — 이걸 분할이라고 해요. "같은 반이다"라는 관계가 전교생을 반별로 쪼개는 것처럼요.

순서관계 — 줄을 세우는 관계

반사적 · 반대칭적(aRb이고 bRa이면 a = b) · 추이적인 관계를 부분순서(partial order)라고 합니다. ≤, "~의 부분집합이다", "~를 먼저 해야 한다" 같은 것들이에요.

작업 사이의 "먼저 해야 한다" 관계를 순서대로 늘어놓는 것을 위상 정렬이라 하고, 빌드 시스템·패키지 설치·과목 선수 관계가 전부 이 문제입니다.