이행 폐포

수치해석 소프트웨어 마지막 수정: 2026-08-27 04:13:52

1. 개요[편집]

이행 폐포 Transitive closure
대상	이항관계 $R \subseteq X \times X$ — 그래프로는 도달 가능성
정의	$R$ 를 포함하는 가장 작은 이행적 관계
고전 해법	워셜(1962) 삼중 루프 $\Theta(V^3)$
실전 해법	비트셋 $\Theta(V^3/w)$ · SCC 축약 + 역위상 순서
이론 최선	불 행렬곱과 등가 — $O(n^{\omega})$
출력 크기	$\Theta(V^2)$ 까지 커질 수 있음 (하한이 여기서 온다)
역연산	이행 축소 (transitive reduction)

이행 폐포(transitive closure)는 어떤 이항관계 $R$ 에 « $a\,R\,b$ 이고 $b\,R\,c$ 이면 $a\,R\,c$ » 라는 규칙을 더 이상 새 쌍이 생기지 않을 때까지 적용해 얻는, $R$ 을 포함하는 가장 작은 이행적 관계 $R^{+}$ 다. 그래프의 언어로 옮기면 훨씬 친근해진다 — ” $u$ 에서 $v$ 로 가는 경로가 존재하는가” 를 모든 정점 쌍에 대해 미리 계산해 둔 표다.

이 문서가 다루는 것은 사실상 하나의 질문이다. 도달 가능성은 DFS 한 번이면 정점 하나에 대해 $O(V+E)$ 에 끝나는데, 모든 쌍을 원하는 순간 왜 갑자기 어려워지는가. 답은 두 갈래로 갈린다. 하나는 출력 자체가 $\Theta(V^2)$ 비트라 그 밑으로는 원리적으로 못 내려간다는 것이고, 다른 하나는 그 $V^2$ 를 채우는 비용이 불 행렬 곱셈과 정확히 같은 난이도라는 것이다. 실무에서 이기는 방법은 점근 복잡도가 아니라 워드 병렬화와 그래프 구조(강한 연결 성분)를 쓰는 쪽이다.

플로이드-워셜 알고리즘 문서가 이 계산을 ” $(\min,+)$ 를 $(\text{or},\text{and})$ 로 갈아 끼운 특수 사례”로 한 줄 짚고 넘어가니, 여기서는 그 한 줄이 실제로 어디까지 가는지를 본다.

2. 정의 — 관계의 거듭제곱[편집]

관계의 합성을 $R \circ S = \{(a,c) : \exists b,\ (a,b)\in R,\ (b,c)\in S\}$ 로 두고 $R^k$ 를 $k$ 번 합성한 것이라 하면

R^{+} \;=\; \bigcup_{k \ge 1} R^{k}, \qquad R^{*} \;=\; R^{+} \cup \Delta_X \;=\; \bigcup_{k \ge 0} R^{k}

이다. $\Delta_X$ 는 항등관계이고 $R^{*}$ 를 반사 이행 폐포라 부른다. 그래프로 읽으면 $R^k$ 는 “간선을 정확히 $k$ 개 써서 갈 수 있는 쌍”이고, $R^{+}$ 는 “길이 1 이상 경로”, $R^{*}$ 는 “자기 자신 포함”이다. 유한 집합 $|X| = n$ 에서는 단순 경로의 길이가 $n-1$ 을 넘지 못하므로 합집합이 $k = n-1$ 에서 멈춘다.

“가장 작다”는 조건은 폐포 연산자의 표준 정의를 그대로 따른다 — $R \subseteq R^{+}$ , $R^{+}$ 는 이행적, 그리고 $R$ 을 포함하는 모든 이행적 관계는 $R^{+}$ 를 포함한다. 이행적 관계들의 교집합이 다시 이행적이므로 ” $R$ 을 포함하는 이행적 관계 전부의 교집합”으로 잡아도 같은 것이 나오고, 그래서 $R^{+}$ 는 유일하다.

인접행렬 $A \in \{0,1\}^{n\times n}$ 로 옮기면 불 반환 $(\vee, \wedge)$ 위에서

A^{+} \;=\; \bigvee_{k\ge 1} A^{k}, \qquad A^{*} \;=\; (A \vee I)^{\,n-1}

이 된다. 여기서 $A \vee I$ 를 쓰는 것은 ” $k$ 번 이하”를 “정확히 $k$ 번”으로 바꾸는 표준 트릭이다. 자기 루프를 달아 두면 짧은 경로가 제자리걸음으로 길이를 채울 수 있다.

3. 워셜 알고리즘[편집]

스티븐 워셜이 1962년 두 쪽짜리 논문에서 제시한 것이 지금도 표준이다.¹

for k in 0..V-1:
  for i in 0..V-1:
    if A[i][k]:
      for j in 0..V-1:
        A[i][j] |= A[k][j]

논리는 플로이드-워셜 알고리즘과 같다. $A^{(k)}[i][j]$ 를 “중간 정점을 $\{0,\dots,k\}$ 에서만 고를 때 $i \to j$ 도달 가능”으로 정의하면

A^{(k)}[i][j] \;=\; A^{(k-1)}[i][j] \;\vee\; \big(A^{(k-1)}[i][k] \wedge A^{(k-1)}[k][j]\big)

이고, $k$ 가 바깥 루프여야 한다는 것, 그리고 배열 하나로 제자리 갱신이 되는 것(패스 $k$ 동안 $k$ 행· $k$ 열이 안 변한다) 모두 그대로 물려받는다. 불 판에서는 후자가 더 쉽다 — $A[i][k] \vee (A[i][k] \wedge A[k][k])$ 는 어떤 경우에도 $A[i][k]$ 를 바꾸지 못한다. 최단경로판에서 “음수 사이클이 없어야 한다”고 조건을 달았던 자리에 불 판에서는 아무 가정도 필요 없다. 사이클이 있으면 있는 대로 도달 가능한 것이 맞기 때문이다.

위 코드에서 if A[i][k] 를 한 겹 밖으로 뺀 것이 실전에서 중요하다. 이 검사가 거짓이면 안쪽 $j$ 루프 전체를 건너뛰므로, 희소한 폐포에서는 삼중 루프의 상수가 크게 줄고 — 더 중요하게는 — 안쪽 루프가 A[i][*] |= A[k][*] 라는 순수한 벡터 OR 가 되어 다음 절의 최적화가 그대로 꽂힌다.

4. 비트셋 — 실무에서 실제로 이기는 방법[편집]

$\Theta(V^3)$ 이라는 숫자만 보면 $V = 10^4$ 는 $10^{12}$ 연산이라 포기해야 할 것 같지만, 실제로는 노트북에서 몇 초에 끝난다. 이유는 한 행을 비트로 채우면 안쪽 루프가 워드 단위로 처리되기 때문이다.

\Theta(V^3) \;\longrightarrow\; \Theta\!\left(\frac{V^3}{w}\right)

$w$ 는 워드 폭이고, 64비트 정수 배열이면 64배, AVX-512 로 벡터화하면 512배다. 실제 상수 감소가 두세 자릿수라, “점근적으로 더 빠른” 행렬곱 기반 알고리즘이 현실 규모에서 비트셋 워셜을 이기는 일은 거의 없다. 메모리도 $V^2/8$ 바이트라 $V = 10^5$ 이면 1.25 GB — 한계는 시간이 아니라 공간이라는 사정도 최단경로판과 같다.

희소 그래프라면 아예 다른 골격이 낫다. 정점마다 BFS/DFS 를 돌리면 $O(V(V+E))$ 이고, 폐포가 희소하다면(도달 가능 쌍이 별로 없다면) 이쪽이 압도적으로 싸다. 밀집 폐포에는 워셜, 희소 폐포에는 $V$ 번의 탐색 — 판단 기준은 입력의 밀도가 아니라 출력의 밀도라는 점이 함정이다. 간선 $2n$ 개짜리 긴 사슬도 폐포는 $n^2/2$ 쌍이다.

5. 행렬 곱셈으로 내려가기[편집]

$A^{*} = (A\vee I)^{n-1}$ 을 반복 제곱으로 계산하면 곱셈이 $\lceil \log_2 n\rceil$ 번이므로 $O(n^{\omega}\log n)$ 이다. $\omega$ 는 행렬 곱셈 지수이고, 현재 알려진 상한은 $2.372$ 언저리다. 불 행렬곱은 0/1 정수 행렬곱을 돌린 뒤 0 초과를 1로 바꾸면 되므로(성분값이 $n$ 을 넘지 않아 오버플로가 없다) 빠른 정수 행렬곱을 그대로 빌려 쓸 수 있다.

로그 인자는 지울 수 있다. 다음 절에 나오는 SCC 축약으로 그래프를 DAG 로 만들고 위상 순서대로 정점을 번호 매기면 인접행렬이 상삼각이 되는데, 상삼각 불 행렬의 폐포는 블록 분할 후 분할정복으로 $T(n) = 2T(n/2) + O(n^{\omega})$ 를 만족해 $\omega > 2$ 일 때 $O(n^{\omega})$ 에 끝난다. 반대 방향도 성립해서 — 폐포를 계산할 수 있으면 그것으로 불 행렬곱도 계산할 수 있다 — 이행 폐포와 불 행렬 곱셈은 상수배 안에서 계산적으로 등가라는 것이 1971년에 정리됐다.²

이 등가성의 실무적 함의는 “빠른 폐포 알고리즘을 찾겠다”가 곧 “행렬곱 지수를 깎겠다”라는 것이다. 즉 더 나은 알고리즘을 스스로 발명할 생각은 접는 편이 낫다. 그리고 슈트라센 이상의 빠른 행렬곱은 상수가 커서 은하계 알고리즘 취급을 받으므로, 앞 절의 비트셋이 사실상의 최선이다.

6. SCC 축약 + 역위상 순서[편집]

밀집 그래프가 아니면서 폐포는 큰, 즉 가장 흔한 경우에 쓰는 실전 골격이다. 관찰 두 개가 전부다.

같은 강한 연결 요소 안의 정점들은 도달 집합이 완전히 같다. 서로 왕복이 되므로 당연하다. 그러니 SCC 를 하나의 슈퍼노드로 축약하면 $V$ 가 크게 줄고, 원래 정점의 답은 자기 SCC 의 답을 복사하면 된다.
축약된 그래프는 DAG 다. 위상 정렬의 역순으로 훑으면 후속 정점들의 답이 이미 완성돼 있으므로

\mathrm{reach}(v) \;=\; \{v\} \cup \bigcup_{v \to u} \mathrm{reach}(u)

를 비트셋 OR 한 번씩으로 채울 수 있다. 비용은 SCC 계산 $O(V+E)$ (타잔 또는 코사라주) 에 DAG 간선당 비트셋 OR $O(V/w)$ 를 더한 $O(V + E\cdot V/w)$ 다. 사이클이 많은 실제 그래프 — 호출 그래프, 모듈 의존성, 웹 링크 — 에서 SCC 축약 하나로 정점 수가 한 자릿수 배 줄어드는 일이 흔해서, 이 전처리는 거의 공짜로 이득이다.

주의할 것은 대각 성분이다. SCC 크기가 2 이상이면 그 안의 모든 정점은 자기 자신에게 도달 가능( $v \in \mathrm{reach}(v)$ )이고, 크기 1 인 SCC 는 자기 루프가 없는 한 그렇지 않다. $R^{+}$ 와 $R^{*}$ 를 구분해야 하는 이유가 정확히 여기다.

7. 어디에 쓰이나[편집]

2-SAT. 절 $(a \vee b)$ 를 함의 $\lnot a \to b$ , $\lnot b \to a$ 로 바꿔 리터럴 $2n$ 개의 함의 그래프를 만들면, 도달 가능성이 곧 ” $a$ 를 참으로 두면 $b$ 도 참이어야 한다”는 강제 관계다. 폐포를 통째로 계산할 필요는 없다 — 충족 가능성은 어떤 변수 $x$ 에 대해 $x$ 와 $\lnot x$ 가 같은 SCC 에 있는가만 보면 되고, 없으면 SCC 의 역위상 순서로 해까지 바로 읽어낼 수 있어 $O(n+m)$ 선형이다.³ 2-SAT 문서 쪽 주제이지만, “폐포를 다 만들지 말고 SCC 만 보라”는 이 문서의 교훈이 가장 선명하게 드러나는 예다.

데이터플로 해석. 데이터 흐름 분석의 도달 정의(reaching definitions)·생존 변수 분석은 격자 위의 최소 고정점 계산이고, 격자가 “집합의 합집합”인 경우가 정확히 이행 폐포다. 포인터 해석(Andersen 식)은 한 발 더 나가서, 제약을 풀다가 새 간선이 생기는 동적 이행 폐포 문제가 된다 — *p = q 를 처리하는 순간 $p$ 가 가리킬 수 있는 대상마다 새 부분집합 간선이 추가되므로, 폐포와 그래프 구축이 서로를 먹여 살린다. 그래서 이 분야에서는 폐포를 한 번에 계산하지 않고 증분(incremental)으로 굴린다.

재귀 질의. SQL:1999 의 WITH RECURSIVE 가 하는 일이 바로 이것이다.

WITH RECURSIVE reach(src, dst) AS (
    SELECT u, v FROM edge
  UNION
    SELECT r.src, e.v FROM reach r JOIN edge e ON r.dst = e.u
)
SELECT * FROM reach;

옵티마이저가 실제로 돌리는 것은 준나이브 평가(semi-naive evaluation)로, 매 반복마다 전체 reach 가 아니라 직전 반복에서 새로 생긴 델타만 조인한다. 나이브 평가가 $R^{k}$ 를 매번 처음부터 다시 만드는 것이라면 준나이브는 증가분만 전파하는 것이고, 이 차이가 실측에서 수십 배다. 데이터로그(Datalog) 엔진의 표준 실행 전략도 같다. UNION ALL 을 쓰면 중복 제거가 사라져 사이클이 있는 그래프에서 영원히 안 끝난다는 것이 이 쿼리의 국룰 함정이다.⁴

의존성 그래프 일반. 빌드 시스템의 “이 타깃이 바뀌면 무엇을 다시 빌드하나”, 태스크 DAG 스케줄링의 선후 관계 검사, 온톨로지의 개념 포함관계, 분산 시스템의 인과 순서(happens-before) — 전부 폐포다. 시뮬레이션 쪽에서는 조립 순서 제약, 다물체 시스템의 구속 전파, 회로 넷리스트의 팬아웃 추적에서 같은 표가 나온다.

8. 이행 축소[편집]

폐포가 “함의되는 간선을 전부 채워 넣는” 연산이라면, 이행 축소(transitive reduction)는 정확히 반대로 같은 폐포를 유지하면서 간선을 최대한 지우는 연산이다. 알고리즘적으로는 역연산 관계다.

R^{+}\big(\mathrm{TR}(G)\big) \;=\; R^{+}(G), \qquad \mathrm{TR}\big(R^{+}(G)\big) \;=\; \mathrm{TR}(G)

DAG 에서는 이행 축소가 유일하고 원래 그래프의 부분그래프이며, ” $u \to v$ 간선을 지웠을 때도 $u$ 가 $v$ 에 도달하면 지운다”로 얻는다. 하세 다이어그램이 바로 부분순서의 이행 축소이고, 의존성 그래프를 사람이 볼 만하게 그리는 도구들이 내부에서 돌리는 것도 이것이다.

일반 방향그래프에서는 이야기가 갈린다. 축소 그래프가 원래 간선만 써야 한다는 조건을 붙이면(최소 등가 그래프, minimum equivalent graph) 문제는 NP-난해다 — 강하게 연결된 그래프에서 최소 등가 그래프는 해밀턴 회로가 있으면 그것이므로, 해밀턴 회로 문제가 그대로 환원된다. 조건을 풀어 새 간선을 만들어도 된다고 하면 다항시간이지만, 이때 결과는 부분그래프가 아니다. 아호·게리·울먼(1972)이 이 구분을 정리하면서 DAG 의 이행 축소 계산과 이행 폐포 계산이 같은 복잡도임을 보였다.⁵ 어느 방향으로 가든 행렬곱의 벽이 서 있는 셈이다.

9. 관련 문서[편집]

Warshall, S. (1962). “A theorem on Boolean matrices”. JACM 9(1), 11–12. 제목이 “정리”인 이유가 있다 — 논문의 대부분이 알고리즘이 아니라 존재 증명이고, 코드에 해당하는 부분은 문장 몇 개다. 요즘 기준으로는 스택오버플로 답변 분량인데, 60년 넘게 인용되고 있다. ↩
Fischer, M. J. & Meyer, A. R. (1971), Munro, I. (1971). 두 결과가 같은 해에 나왔고 방향이 반대다. 하나는 “폐포를 곱셈으로”, 다른 하나는 “곱셈을 폐포로” 환원한다. 이런 쌍방 환원이 나오면 그 순간 문제 두 개는 한 문제가 되고, 후속 연구자들은 둘 중 편한 쪽만 붙잡고 늘어지면 된다. ↩
함의 그래프에는 대칭성이 하나 있다 — $u \to v$ 간선이 있으면 반드시 $\lnot v \to \lnot u$ 간선도 있다(대우). 그래서 SCC 구조 자체가 대칭이고, 역위상 순서에서 나중에 나오는 쪽을 참으로 두면 모순이 안 생긴다는 논증이 깔끔하게 돌아간다. 3-SAT 로 넘어가는 순간 이 대칭이 사라지고 난이도가 NP-완전으로 점프한다. ↩
UNION 과 UNION ALL 의 차이는 평소엔 성능 취향 문제지만 재귀 CTE 에서는 종료성 문제다. 게다가 조직도나 부품표(BOM)처럼 “사이클이 있을 리 없는” 데이터에 사이클이 들어가는 일이 현업에서는 정말 자주 일어난다. 방어 코드는 보통 경로 배열을 들고 다니며 재방문을 거르는 것인데, 그러면 메모리가 경로 길이만큼 곱해진다. 공짜는 없다. ↩
Aho, A. V., Garey, M. R. & Ullman, J. D. (1972). “The transitive reduction of a directed graph”. SIAM J. Comput. 1(2), 131–137. 참고로 “이행 축소”라는 용어 자체가 이 논문에서 나왔다. 그 전까지는 다들 각자 다른 이름으로 같은 것을 계산하고 있었다. ↩