인접행렬

네 도시 1, 2, 3, 4 사이에 직항 노선이 1–2, 2–3, 3–1, 3–4로 놓여 있다. 노선마다 양방향으로 다닌다. 도시 1에서 출발해 비행기를 정확히 세 번 타서 도시 4에 도착하는 경로는 몇 가지일까? 같은 도시를 다시 지나도 된다. 노선이 많아지면 그림을 보고 세기가 어렵다. 그래프를 수의 표로 바꾸어 행렬의 곱셈으로 이런 경로의 수를 계산할 수 있다고 한다. 어떻게 할까?

4.3.1그래프를 표로 바꾸다

꼭짓점이 \(n\)개인 그래프에서, \(i\)번째와 \(j\)번째 꼭짓점이 변으로 이어져 있으면 1, 아니면 0을 \(i\)행 \(j\)열에 적은 \(n\times n\) 행렬을 인접행렬이라 한다. 변에 방향이 없으면 \(i\)와 \(j\)가 이어진 것과 \(j\)와 \(i\)가 이어진 것이 같으므로 인접행렬은 대칭행렬이다. 자기 자신과 잇는 변이 없으면 대각성분은 모두 0이다. 각 행의 성분을 더하면 그 꼭짓점과 이어진 꼭짓점의 수, 곧 차수가 된다. 그래프를 표로 바꾸면 컴퓨터가 다루기 쉽고, 행렬의 계산으로 그래프의 성질을 구할 수 있다.

\(A^2\)의 \(i\)행 \(j\)열 성분은 \(\sum_k a_{ik}a_{kj}\)인데, \(a_{ik}a_{kj}\)는 \(i\)에서 \(k\)로, \(k\)에서 \(j\)로 가는 변이 모두 있을 때만 1이다. 그래서 이 합은 \(i\)에서 한 번 갈아타 \(j\)로 가는 경로의 수이다. 같은 생각을 되풀이하면 \(A^k\)의 성분은 \(k\)번 이동하는 경로의 수이다. 삼각형 하나는 세 꼭짓점 각각에서 두 방향으로 돌아오는 길이 3인 길 6개를 만들므로, \(A^3\)의 대각합을 6으로 나누면 삼각형의 수가 된다.¹

4.3.2제곱이 알려 주는 것

그림 1의 인접행렬을 제곱하면 첫째 행은 \((2, 1, 1, 1)\)이다. 대각성분 2는 도시 1의 차수이고, 나머지 성분 1은 도시 1에서 한 번 갈아타 도시 2, 3, 4에 가는 경로가 하나씩 있다는 뜻이다. 예를 들어 1에서 4로는 1→3→4 하나뿐이다. 이렇게 행렬을 곱하는 계산이 경로를 일일이 따라가는 일을 대신한다. 노선이 수백 개인 실제 항공망에서도 행렬의 곱셈만으로 경로의 수를 셀 수 있다.

4.3.3예제 풀이

\(A^2\)의 1행은 \((2, 1, 1, 1)\)이고, \(A\)의 4열은 \((0, 0, 1, 0)\)이므로 \(A^3\)의 1행 4열은 \(2\times0 + 1\times0 + 1\times1 + 1\times0 = 1\)이다. 그래서 경로는 한 가지이고, 1→2→3→4이다. 1→3에서 바로 4로 가면 두 번이고, 세 번 타려면 3에 도착하기 전에 한 번 더 갈아타야 하는데 그런 길은 2를 거치는 것뿐이다.

\(A^3\)의 대각성분은 같은 방법으로 \((2, 2, 2, 0)\)이므로 대각합은 6이고, 삼각형은 \(6/6 = 1\)개이다. 실제로 그래프에는 1, 2, 3으로 이루어진 삼각형 하나가 있다. 도시 4는 삼각형에 속하지 않아 대각성분이 0이다. 즉 인접행렬은 그래프를 수의 표로 바꾼 것이며, 그 거듭제곱의 성분은 정해진 횟수만큼 이동하는 경로의 수여서, 그림을 따라가지 않고도 경로와 삼각형을 셀 수 있다.

아래 탐구 카드에서 그래프를 인접행렬로 바꾸어 보고, 행렬의 곱셈으로 세 번 갈아타는 항공편 경로의 수를 세어 보자.

1. 사회 연결망 연구에서는 인접행렬로 친구의 친구 수나 삼각형의 비율을 계산한다. 내 친구 둘이 서로도 친구인 비율을 뭉침 계수라 하며, 실제 사람들의 연결망은 아무렇게나 이은 그래프보다 이 값이 훨씬 크다.