본문 바로가기

장 실습: 한 그래프를 세 가지로 계산하기

한 그래프를 세 가지로 계산하기 과제를 단계별로 진행하고, 손 계산과 코드 출력을 비교합니다. 시작 상태와 체크포인트, 결과가 다를 때 확인할 곳, 완성 파일과 풀이를 함께 제공합니다.

같은 그래프를 보행의 수로 계산할 때와 도달 여부로 계산할 때는 결과의 뜻이 다릅니다. 관계와 그래프를 계산하는 행렬의 예에 앞서 배운 행렬 곱과 역행렬을 함께 적용합니다.

이 글을 마치면 다음을 할 수 있습니다.

  • 행렬의 거듭제곱을 더해 길이 3 이하인 보행의 수를 셉니다.
  • 양쪽 곱으로 역행렬을 확인하고, 개수와 부울 도달 여부를 비교합니다.

시작 상태

행렬의 연산과 행렬식의 multiply, 역행렬과 연립일차방정식의 역행렬 정의, 앞 글의 transitive_closure를 씁니다. 정점 순서는 1, 2, 3, 4이고 간선은 1→2, 1→3, 2→4, 3→4입니다. 이 실습은 7장과 같은 선택 심화입니다.

Python은 교재 첫머리의 준비를 그대로 쓰며 추가 패키지는 설치하지 않습니다. 새 파일 graph_matrix.py를 만들고 이 실습의 함수와 마지막 호출만 모읍니다. 실행 명령은 python graph_matrix.py입니다. 완성 파일에는 필요한 함수가 모두 들어 있으므로 앞 글 파일을 import하지 않습니다.

완성 조건

앞 글의 네 정점 그래프의 인접 행렬 A로 다음을 graph_matrix.py에 만드세요. 세 글에서 만든 곱셈, 역행렬의 정의, 추이 폐포를 모읍니다.

  • W=I+A+A2+A3W=I+A+A^2+A^3을 multiply로 구해 출력합니다. W의 i행 j열은 길이 3 이하(길이 0 포함)인 보행의 수입니다.
  • W가 I−AI-A의 역행렬인지 양쪽으로 곱해 확인합니다.
  • transitive_closure(A)의 대각선을 참으로 바꾼 표가, W에서 0이 아닌 칸을 참으로 바꾼 표와 같은지 출력합니다.

실행하기 전에 W를 손으로 구하고, (I−A)W=I(I-A)W=I인 이유를 A4A^4이 영행렬이라는 사실로 설명해 보세요. 힌트: (I−A)(I+A+A2+A3)(I-A)(I+A+A^2+A^3)을 전개하면 가운데 항들이 지워집니다.

1단계: 보행의 수 누적하기

I에서 시작해 A의 거듭제곱을 차례로 곱하고 W에 더합니다. 네 행을 손으로 계산한 값과 비교합니다.

체크포인트: W의 첫 행은 [1, 1, 1, 2]입니다. 마지막 2는 1→2→4와 1→3→4를 셉니다.

2단계: 양쪽 곱으로 역행렬 확인하기

I_minus_A를 만들고 W를 왼쪽과 오른쪽에서 각각 곱합니다.

체크포인트: 네 행을 출력한 다음 줄이 True True입니다.

3단계: 개수와 도달 여부 비교하기

추이 폐포의 대각선을 참으로 바꾼 표와 W에서 양수인 칸만 남긴 표를 비교합니다.

체크포인트: 마지막 줄이 True입니다. 한 번 이상 닿는지와 보행이 몇 개인지를 구별해 읽습니다.

다를 때 먼저 볼 곳

증상먼저 볼 곳
W의 (1, 4)가 1이다길이 2인 두 보행을 모두 곱셈으로 셌는지
역행렬 비교가 False다W에 단위행렬 I부터 포함했는지, A의 정점 순서가 같은지
마지막 비교만 False다추이 폐포에서 길이 0을 나타내는 대각선을 참으로 바꿨는지

완성 파일과 풀이

먼저 위 단계까지 직접 작성해 보세요. 예상한 결과와 비교할 준비가 되면 아래를 펼칩니다.

완성 파일과 풀이 보기

A2A^2은 (1, 4)만 2이고 A3A^3부터는 영행렬이므로, W는 I에 A를 더하고 (1, 4)에 2를 더한 것입니다. 전개하면 (I−A)(I+A+A2+A3)=I−A4(I-A)(I+A+A^2+A^3)=I-A^4이고, 앞 글의 4번 문제에 따라 A4A^4이 영행렬이라 I입니다. 반대 순서의 곱도 같은 전개로 I입니다.

graph_matrix.py
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 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

A = [[0, 1, 1, 0],
     [0, 0, 0, 1],
     [0, 0, 0, 1],
     [0, 0, 0, 0]]
n = len(A)
I = [[int(i == j) for j in range(n)] for i in range(n)]

W = I
term = I
for m in range(1, n):
    term = multiply(term, A)
    W = [[x + y for x, y in zip(r1, r2)] for r1, r2 in zip(W, term)]
for row in W:
    print(row)

I_minus_A = [[x - y for x, y in zip(r1, r2)] for r1, r2 in zip(I, A)]
print(multiply(I_minus_A, W) == I, multiply(W, I_minus_A) == I)

closure = transitive_closure(A)
star = [[closure[i][j] or i == j for j in range(n)] for i in range(n)]
print(star == [[x > 0 for x in row] for row in W])
[1, 1, 1, 2]
[0, 1, 0, 1]
[0, 0, 1, 1]
[0, 0, 0, 1]
True True
True

확인할 곳은 세 가지입니다. W의 (1, 4)가 2인 것은 1→2→4와 1→3→4를 센 것이고, 네 행 다음의 True True는 W가 양쪽 곱으로 역행렬임을 보여 줍니다. 마지막 True는 수로 센 결과에서 개수를 버리면 부울 계산의 결과가 된다는 뜻입니다.

더 해 보기

  • A에 간선 4→1을 더하고 어느 출력이 달라지는지 설명해 보세요. 앞 글의 3번·4번 문제를 함께 보세요.
  • 원래 그래프에서 W의 각 대각선 값이 무엇을 세는지 적고, I를 빼면 마지막 도달 여부 비교가 어떻게 달라질지 예상해 보세요.

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