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

관계 행렬은 0과 1만 적힌 표입니다. 행렬의 연산과 행렬식에서 배운 곱셈을 이 표에 그대로 쓰면 1을 수로 더하게 되고, 1을 참으로 보고 계산하면 연결이 있는지만 남습니다. 같은 표라도 어떤 연산을 쓰느냐에 따라 답이 뜻하는 바가 달라지는 것입니다. 이 글에서는 두 계산을 구분하고, 관계의 합성과 폐포에서 반복으로 구한 추이 폐포를 행렬로 계산합니다. 선택 심화이며, 그래프의 용어는 8장의 그래프의 모델과 표현에서 자세히 다룹니다.

관계 행렬은 방향 그래프의 인접 행렬이다

관계의 표현과 성질에서 본 것처럼, 집합 $\{1,2,\ldots,n\}$ 위의 관계 R은 $(i,j)\in R$일 때 i행 j열에 1을 적은 n × n 관계 행렬로 나타낼 수 있습니다. 같은 관계를 그림으로 그리면 원소마다 점을 찍고 i에서 j로 화살표를 그린 방향 그래프가 됩니다. 이때 점을 정점(vertex), 화살표를 간선(edge)이라 하고, 그래프의 간선을 표로 적은 것을 인접 행렬(adjacency matrix)이라고 합니다. 관계 행렬과 인접 행렬은 같은 표입니다. 이 글에서는 간선 1→2, 1→3, 2→4, 3→4가 있는 네 정점의 그래프를 주로 씁니다.

간선을 따라 이동하며 지나는 정점의 나열을 보행(walk)이라 하고, 지나간 간선의 개수를 보행의 길이라고 합니다. 보행에서는 같은 정점이나 같은 간선을 다시 지나도 되며, 정점을 반복하지 않는 보행은 단순 경로(simple path)라고 따로 부릅니다.

보통 곱은 보행의 수를 센다

$A^2$의 i행 j열은 $\sum_k a_{ik}a_{kj}$입니다. 각 항 $a_{ik}a_{kj}$는 i→k와 k→j가 모두 있을 때만 1이고 나머지 경우에는 0이므로, 이 합은 가운데 정점 k를 거쳐 i에서 j로 가는 길이 2인 보행의 수입니다. 예시 그래프에서 $A^2$의 (1, 4)는 1→2→4와 1→3→4를 세어 2가 됩니다.

같은 생각을 되풀이하면 $A^m$의 i행 j열은 i에서 j로 가는 길이 m인 보행의 수입니다. 길이 m인 보행은 길이 m − 1인 보행으로 어떤 정점 k에 간 뒤 간선 k→j를 하나 붙인 것이고, $A^m=A^{m-1}A$의 i행 j열이 바로 $\sum_k(A^{m-1})_{ik}a_{kj}$이기 때문입니다. m = 1에서 출발하면 수학적 귀납법으로 정리할 수 있습니다.

여기서 세는 것은 단순 경로가 아니라 보행입니다. 1→2와 2→1만 있는 그래프의 인접 행렬 B를 제곱하면 단위행렬이 되는데, (1, 1)의 1은 1에서 나갔다가 돌아오는 1→2→1을 센 것입니다. 이 보행은 정점 1을 두 번 지나므로 단순 경로가 아닙니다.

부울 곱은 연결이 있는지만 본다

곱 대신 AND를, 합 대신 OR를 쓰는 행렬 곱셈을 부울 곱(Boolean product)이라 하고, 이 글에서는 $A\odot B$로 씁니다. i행 j열은 어떤 k에 대해 $a_{ik}$와 $b_{kj}$가 모두 1이면 1이고, 그런 k가 하나도 없으면 0입니다. 보통 곱의 합은 0 이상의 수를 더한 것이라 항이 하나라도 1이면 양수가 되므로, 부울 곱은 보통 곱을 계산한 뒤 0이 아닌 칸을 모두 1로 바꾼 것과 같습니다.

def multiply(left, right):
    return [[sum(x * y for x, y in zip(row, column)) for column in zip(*right)] for row in left]


def boolean_multiply(left, right):
    return [[int(any(x and y for x, y in zip(row, column))) for column in zip(*right)] for row in left]


A = [[0, 1, 1, 0],
     [0, 0, 0, 1],
     [0, 0, 0, 1],
     [0, 0, 0, 0]]
print(multiply(A, A)[0], boolean_multiply(A, A)[0])
B = [[0, 1], [1, 0]]
print(multiply(B, B))

[0, 0, 0, 2] [0, 0, 0, 1]
[[1, 0], [0, 1]]

zip(*right)는 오른쪽 행렬의 열을 하나씩 꺼냅니다. 두 함수는 행과 열을 짝지어 곱의 합을 구하느냐, 짝 가운데 하나라도 둘 다 참인지 묻느냐만 다릅니다. 첫 줄을 보면 1에서 4로 가는 길이 2인 보행은 두 개이고, 부울 곱은 그런 보행이 있다는 사실만 1로 남깁니다. 둘 다 올바른 답이며, 묻는 질문이 다를 뿐입니다.

부울 곱은 관계의 합성을 행렬로 계산한 것이기도 합니다. $S\circ R$은 R로 한 번 이동한 뒤 S로 한 번 더 이동하는 관계이므로, 그 관계 행렬은 $M_R\odot M_S$입니다. 합성 기호에서는 S가 왼쪽에 오지만, 행렬에서는 먼저 따라가는 R의 행렬이 왼쪽에 온다는 점에 주의해야 합니다.

원소별 OR·AND는 부울 곱과 다르다

같은 정점 순서로 적은 두 관계 행렬에서 같은 자리끼리 OR를 하면 합집합 $R\cup S$의 행렬이, AND를 하면 교집합 $R\cap S$의 행렬이 됩니다. 같은 자리끼리만 계산하므로, 가운데 정점을 찾는 부울 곱과는 다른 연산입니다. 정점 1, 2 위의 두 관계로 비교해 보겠습니다.

합집합에는 R이나 S 어느 쪽에든 있는 연결이 모두 들어가고, 교집합에는 양쪽에 함께 있는 1→2만 남습니다. 부울 곱은 R로 먼저 이동한 뒤 S로 이어 가는 연결입니다. R의 2→1 다음에 S의 1→1이나 1→2를 이어 갈 수 있으므로 2행이 모두 1입니다. 반면 R의 1→2 다음에는 S의 2행이 모두 0이라 이어 갈 연결이 없으므로 1행이 모두 0입니다. 다른 책에서는 $\odot$를 같은 자리끼리의 곱에 쓰기도 하므로, 기호를 만나면 정의를 먼저 확인해야 합니다.

추이 폐포를 부울 거듭제곱으로 구한다

관계의 합성과 폐포에서 추이 폐포를 $R^+=R\cup R^2\cup R^3\cup\cdots$로 썼습니다. 관계 행렬 M으로 옮기면, 부울 곱으로 만든 거듭제곱 $M^{[k]}=M\odot M\odot\cdots\odot M$을 원소별 OR로 모은 것이 $R^+$의 행렬입니다.

끝없이 모을 필요는 없습니다. 정점이 n개일 때 i에서 j로 가는 보행이 있으면 길이가 n 이하인 보행도 있기 때문입니다. 길이가 n보다 긴 보행은 첫 정점 다음부터 n개보다 많은 자리에 정점이 놓이므로, 비둘기집 원리에 따라 어떤 정점이 두 번 나옵니다. 두 번 나온 자리 사이의 구간을 빼도 첫 간선은 남으므로, 같은 곳에서 출발해 같은 곳에 닿는 더 짧은 보행이 됩니다.

간선 1→2, 2→3, 3→4로 된 사슬에서는 $M^{[2]}$가 (1, 3)과 (2, 4)를, $M^{[3]}$이 (1, 4)를 더하고, $M^{[4]}$는 모든 칸이 0입니다. 관계의 합성과 폐포의 연습 문제에서 반복으로 구한 6개의 쌍과 같습니다. 다만 이 방법은 n × n 부울 곱을 n − 1번 하므로 계산량이 $n^4$에 비례합니다.

Warshall 알고리즘은 중간 정점을 하나씩 허용한다

Warshall 알고리즘은 같은 결과를 $n^3$에 비례하는 계산으로 구합니다. k번째 단계에서는 정점 1부터 k까지를 보행의 중간에 거쳐도 되도록 허용하고, 모든 i와 j에 대해 reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])로 표를 고칩니다. i에서 j로 이미 갈 수 있었거나, 앞 단계까지의 표로 i에서 k까지, k에서 j까지 갈 수 있으면 참이 된다는 뜻입니다. 단계의 뜻이 유지되려면 k가 가장 바깥 반복이어야 하며, 순서를 바꾸면 어떤 쌍을 놓치는지는 자료구조·알고리즘 교재의 Warshall과 도달 가능성의 논리에서 예로 보여 줍니다.

def transitive_closure(matrix):
    reach = [[bool(x) for x in 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] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach


def show(matrix):
    for row in matrix:
        print(" ".join("1" if x else "0" for x in row))


chain = [[0, 1, 0, 0],
         [0, 0, 1, 0],
         [0, 0, 0, 1],
         [0, 0, 0, 0]]
show(transitive_closure(chain))
print()
show(transitive_closure([[0, 1, 0], [1, 0, 0], [0, 0, 0]]))

0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0

1 1 0
1 1 0
0 0 0

입력을 bool로 바꾸어 복사하므로 0과 1로 된 표를 넣어도 되고, 원래 표는 바뀌지 않습니다. 사슬의 결과는 앞에서 거듭제곱으로 구한 것과 같습니다. 단계별로 보면 정점 1로 들어오는 간선이 없어 첫 단계에서는 아무것도 바뀌지 않고, 둘째 단계에서 1→2→3으로 (1, 3)이, 셋째 단계에서 (1, 4)와 (2, 4)가 생깁니다. 정점 4에서 나가는 간선이 없으므로 넷째 단계에서는 바뀌는 칸이 없습니다.

두 번째 결과에서는 대각선의 (1, 1)과 (2, 2)가 참입니다. 반사 폐포를 따로 구해서가 아니라, 1→2→1과 2→1→2라는 길이 2인 보행이 있기 때문입니다. 정점 3에서는 나가는 간선이 없어 (3, 3)은 거짓입니다. 길이 0인 보행까지 인정하는 $R^*$가 필요하면 결과의 대각선을 모두 참으로 바꾸면 됩니다. 세 겹의 반복이 각각 n번씩 돌므로 계산은 $n^3$번이고, 표는 $n^2$칸을 씁니다.

더 깊이: 표 하나를 덮어써도 되는 이유

수학적으로는 단계마다 새 표를 앞 단계의 표로 만들지만, 코드는 표 하나를 덮어쓰며 고칩니다. 그래도 결과가 같은 이유는 k번째 단계에서 k행과 k열이 바뀌지 않기 때문입니다. 갱신식에 j = k를 넣으면 reach[i][k] or (reach[i][k] and reach[k][k])가 되어 원래 값 그대로이고, i = k를 넣어도 마찬가지입니다. 갱신식이 고칠 칸 말고 읽는 칸은 k행과 k열뿐이므로, 같은 단계 안에서 먼저 고친 칸이 나중 계산에 쓰여도 값이 달라지지 않습니다.

정리

• 관계 행렬은 방향 그래프의 인접 행렬과 같은 표이며, 보통 곱으로 만든 $A^m$의 i행 j열은 i에서 j로 가는 길이 m인 보행의 수입니다. 보행은 정점을 반복할 수 있으므로 단순 경로의 수와 다릅니다.
• 부울 곱은 곱 대신 AND, 합 대신 OR를 쓰며, 보통 곱에서 0이 아닌 칸을 1로 바꾼 것과 같습니다. 관계의 합성 $S\circ R$의 행렬은 $M_R\odot M_S$입니다.
• 원소별 OR와 AND는 같은 자리끼리 계산해 합집합과 교집합을 만들며, 가운데 정점을 찾는 부울 곱과 다릅니다.
• 정점이 n개이면 추이 폐포의 행렬은 $M\lor M^{[2]}\lor\cdots\lor M^{[n]}$이고, Warshall 알고리즘은 중간 정점을 하나씩 허용하며 같은 결과를 $n^3$에 비례하는 계산으로 구합니다.
• 추이 폐포의 대각선은 그 정점으로 돌아오는 보행이 있을 때만 참이고, $R^*$가 필요하면 대각선을 모두 참으로 바꿉니다.

연습 문제

1. 길이가 정확히 2인 보행

예시 그래프에 간선 1→4를 더하면 $A^2$의 (1, 4)는 바뀌나요? 1에서 4로 가는 길이 2 이하의 보행은 모두 몇 개인가요?

2. 보행이 끝나는 그래프

예시 그래프의 $A^3$은 어떤 행렬인가요? 간선 4→1을 더하면 어떻게 달라지나요?

3. 부울 곱의 순서

본문의 R과 S로 $S\odot R$을 구하고, $R\odot S$와 같은지 비교하세요.

행렬로 계산한 결과가 이상하면 행과 열의 정점 순서, 그리고 수로 계산했는지 참·거짓으로 계산했는지를 먼저 확인해 보세요. 같은 세 겹 반복에서 OR와 AND를 최솟값과 덧셈으로 바꾸면 모든 정점 쌍의 최단 거리를 구할 수 있으며, 이 방법은 최단 경로에서 다룹니다. 다음 장의 그래프의 모델과 표현에서는 이 글에서 표로 다룬 그래프를 정점과 간선의 언어로 다시 정리합니다.