관계와 그래프를 계산하는 행렬

관계 행렬의 1을 단순한 숫자로 계산할지 참으로 계산할지에 따라 답의 의미가 달라집니다. 선택 심화인 이 절은 행렬 곱, 관계 합성과 그래프 표현을 먼저 읽고 접근합니다.

같은 표에 다른 연산

보통 행렬 곱은 곱을 더하므로 연결 방법의 개수를 셀 수 있습니다. 부울 행렬 곱은 곱 대신 AND, 합 대신 OR를 사용해 하나라도 연결이 존재하는지만 표시합니다. 인접행렬 A의 $A^2_{ij}$는 i에서 j로 정확히 두 간선을 사용하는 보행의 수입니다. 부울 제곱은 그런 보행이 있으면 1입니다. 정점·간선이 반복될 수 있으므로 이를 항상 단순경로 수라고 부르면 안 됩니다.

1→2,1→3,2→4,3→4인 방향 그래프에서는 1→2→4와 1→3→4 두 보행이 있습니다. 보통 제곱의 (1,4)는 2이고 부울 제곱의 (1,4)는 1입니다. 둘 다 올바르지만 질문이 다릅니다.

원소별 OR·AND와 행렬의 부울곱은 다르다

같은 정점 순서로 쓴 R,S의 원소별 OR는 두 관계의 합집합, 원소별 AND는 교집합입니다. 같은 자리끼리만 계산하므로 가운데 정점을 찾는 부울곱과 다릅니다. 정점 1,2의 순서에서

합집합에는 R이나 S 어느 쪽에라도 있는 연결, 교집합에는 양쪽에 함께 있는 1→2만 남습니다. 반면 R의 연결 뒤 S의 연결을 따르는 부울곱은 $R\odot S=\begin{pmatrix}0&0\\1&1\end{pmatrix}$입니다. 2→1을 R에서 이동한 뒤 S에서 1→1 또는 1→2로 이어 갈 수 있기 때문입니다. 1→2 뒤에는 S의 2행이 모두 0이라 이어지는 연결이 없습니다. 여기서 $\odot$는 원소별 곱을 뜻하지 않고 부울 행렬곱이라고 정의한 기호입니다.

Warshall: 중간 정점을 하나씩 허용하기

관계 행렬 R에서 추이 폐포를 계산할 수 있습니다. k번째 단계에 정점 k를 중간에 써도 되도록 허용하여 $reach[i][j]$를 $reach[i][j]\lor(reach[i][k]\land reach[k][j])$로 갱신합니다. k는 가장 바깥 반복이어야 단계의 뜻이 유지됩니다.

def transitive_closure(matrix):
    reach = [row[:] for row in matrix]
    n = len(reach)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                reach[i][j] = bool(reach[i][j] or
                                   (reach[i][k] and reach[k][j]))
    return reach

matrix = [[False, True, False],
          [False, False, True],
          [False, False, False]]
print(transitive_closure(matrix))
# [[False, True, True], [False, False, True], [False, False, False]]

입력은 정사각 부울 행렬입니다. 코드가 입력 행렬을 복사하므로 원래 표를 바꾸지 않습니다. 길이 0 경로도 허용하는 $R^*$를 원한다면 계산 전에 대각선을 True로 설정합니다. 위 코드는 한 번 이상 이동하는 $R^+$라 대각선이 자동으로 전부 True가 되지는 않습니다. 시간은 n³번 조합 확인, 저장은 n²칸입니다.

스스로 풀어보기

문제 1. 위 4정점 예에서 두 단계로 1에서 4에 가는 결과를 보통 곱과 부울 곱으로 각각 구하세요.

풀이: 가운데 정점 2와 3이 각각 1·1을 제공해 보통 합은 2입니다. 부울 합은 True OR True=True, 숫자 표기로 1입니다. 보통 곱 결과를 부울 곱 결과와 같다고 쓰지 않습니다.

문제 2. 1→2,2→1인 그래프의 추이 폐포에서 대각선은 왜 참인가요?

풀이: 1→2→1과 2→1→2가 각각 양의 길이 보행이므로 (1,1),(2,2)가 포함됩니다. 반사 폐포를 별도로 요청해서가 아니라 원래 사이클로 도달 가능하기 때문입니다.

결과가 이상하면 행·열의 정점 순서와 연산 의미를 먼저 확인합니다. 무게의 합을 최소화하는 다른 행렬 갱신은 최단경로에서 다룹니다.