인접행렬

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수( 공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타	P-NP 문제^미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}

1. 개요2. 표현 방법3. 성질4. 경로의 개수

4.1. 예시

5. 특수한 인접행렬6. 관련 문서

1. 개요

隣接行列, adjacency matrix

그래프에서 각 정점(vertex)의 연결 관계, 즉 간선(edge)의 존재 여부를 행렬로 표현한 것이다. 그래프에서 정점이 [math(n)]개일 때, 각 정점을 행과 열로 하는 [math(n)]차 정사각행렬이다.

2. 표현 방법

정점이 n개인 그래프의 각 정점에 대해 순서대로 [math(1, 2, ..., n)]으로 번호를 매길 때, 이 그래프에 대한 인접행렬을 [math(A)]라고 하면 다음과 같은 규칙을 따른다. (단, [math(a, b=1, 2, ..., n)])

[math(A_{ab})] 성분의 값은 정점 [math(a)]에서 [math(b)]로 이동하는 간선이 있을 때 1, 없을 때 0이다.

무방향 그래프일 때는 [math(a)]와 [math(b)]를 연결하는 간선이 있으면 1, 그렇지 않으면 0이다.

[math(A_{aa})] 성분, 즉 주대각선상의 성분의 값은 항상 0이다.

단 자기 자신으로 연결되는 간선이 있으면 1이다.

예를 들어 위 그림에서 정점 A, B, C, D, E를 각각 숫자 1, 2, 3, 4, 5로 번호를 매기면 (가)는 무방향 그래프이므로 인접행렬은 다음과 같이 대칭행렬이다.

[math(A_{가}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})]

(나)는 방향 그래프이고, 그 인접행렬은 다음과 같다.

[math(A_{나}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})]

(다)는 무방향 간선이 존재하는 방향 그래프이고, 그 인접행렬은 다음과 같다.

[math(A_{다}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})]

(가), (나), (다) 모두 자기 자신으로 이동하는 간선은 존재하지 않으므로 주대각선상의 성분의 값은 항상 0이 된다.

3. 성질

무방향 그래프의 인접행렬은 항상 대칭행렬이다.
무방향 그래프라는 것은 정점 [math(a)]에서 [math(b)]로 이동하는 간선이 있을 때 정점 [math(b)]에서 [math(a)]로 이동하는 간선 역시 항상 존재한다는 것을 의미하고, 그 역도 성립한다. 따라서 인접행렬 [math(A)]에 대해서 [math(A_{ab}=A_{ba})]가 항상 성립한다.
인접행렬의 모든 성분의 합은 그래프의 화살표의 개수와 같다. 이때, 무방향 간선은 양쪽으로 이어지므로 화살표 2개로 간주한다.

무방향 그래프에서 인접행렬의 모든 성분의 합은 간선의 개수의 2배이다.

4. 경로의 개수

인접행렬을 이용하여 정점의 개수가 [math(v)]개인 그래프의 어떤 정점 [math(a)]에서 다른 정점 [math(b)]로 이동하는 경로의 개수를 구할 수 있다. 인접행렬 [math(A)]에 대하여 [math(A^n)]은 어떤 정점에서 다른 정점으로 [math(n)] step을 거쳐서 이동하는 경로의 수를 나타낸다. 즉, [math(A^n_{ab})]는 그래프의 정점 [math(a)]에서 정점 [math(b)]로 [math(n)] step을 거쳐 이동하는 가능한 경로의 수이다. 증명은 수학적 귀납법을 사용하면 다음과 같다.

먼저 [math(n=1)]일 때, 인접행렬 [math(A)]의 성분 [math(A_{ab})] 그 자체는 그래프의 정점 [math(a)]에서 [math(b)]로 직접 이동하는 경로가 있으면 1, 없으면 0이다. 즉 1 step을 거쳐 [math(a)]에서 [math(b)]로 이동하는 경로가 있는지를 나타내므로, 이러한 경로의 개수와 같다.
[math(n=k)]일 때 [math(A^k_{ab})] 성분을 그래프에서 정점 [math(a)]에서 [math(b)]로 [math(k)] step을 거쳐 이동하는 경로의 개수라고 하자. 이때 [math(A^{k+1}_{ab})]은 [math(A^{k+1}_{ab}=\sum_{i=1}^v A^k_{ai}A_{ib})]와 같이 구할 수 있다. 이때 [math(A^k_{ai})]는 정점 [math(a)]에서 [math(i)]로 [math(k)] step을 거쳐 이동하는 경로의 개수를, 그리고 [math(A_{ib})]는 정점 [math(i)]에서 [math(b)]로 직접 이동할 수 있는지를 나타낸다. 이 식의 각 항 [math(A^k_{ai}A_{ib})] (단, [math(i=1,2,...,v)])은 이 둘을 곱한 것과 같으므로, 정점 [math(i)]에서 [math(b)]로 직접 이동할 수 있으면 정점 [math(a)]에서 [math(i)]로 [math(k)] step을 거쳐 이동하는 경로의 개수가 되고, 이동할 수 없으면 그 경로의 개수와 상관없이 0이 된다. 따라서 정점 [math(a)]에서 [math(k)] step 만에 정점 [math(i)]를 거치고, 이후 1 step 만에 정점 [math(b)]에 도달하는 경우의 수와 같다. 따라서 그 합인 [math(A^{k+1}_{ab}=\sum_{i=1}^v A^k_{ai}A_{ib})]는 각 정점 [math(i=1,2,...,v)]에 대해 그 경우의 수를 모두 합한 것이므로, 정점 [math(a)]에서 정점 [math(b)]까지 [math(k+1)] step 만에 이동하는 경우의 수가 된다. 즉 [math(n=k)]일 때 [math(A^k_{ab})] 성분이 정점 [math(a)]에서 [math(b)]로 [math(k)] step 만에 이동하는 경우의 수이면, [math(n=k+1)]일 때 [math(A^{k+1}_{ab})] 성분은 [math(k+1)] step 만에 이동하는 경우의 수이다.
따라서 수학적 귀납법에 의해 이것이 1 이상의 모든 자연수에 대해 성립한다.

더 간단히 말해보자.
[math((A(n))_{ab})]를 [math(a)]에서 [math(b)]까지 [math(n)]번 이동해 도달하는 경로의 수라고 하자.
[math((A(n+m))_{ab})]는 모든 [math(k)]에 대하여 [math(a)]에서 시작, [math(n)]번 이동해 [math(k)]에 경유하고 다시 [math(m)]번 이동해 [math(b)]에 도달하는 경로수의 합이다. [math(k)]를 경유하는 경로수는 [math(a)]에서 [math(k)]로 [math(n)]번 이동한 경로수와 [math(k)]에서 [math(b)]로 [math(m)]번 이동하는 경로수의 곱이다. 따라서 [math(A(n+m)_{ab} = \displaystyle \sum_{k} (A(n))_{ak}(A(m))_{kb})]이다. 행렬곱에 의해 즉, [math(A(n+m)=A(n)A(m))]이다.
내부 자연수를 쪼개 각 행렬의 곱으로 표현할 수 있으므로 [math(1)]로 모두 쪼개어 [math(A(n)=A(1)^n)]이다. [math(A(1)=A)]로 인접행렬이므로, [math(A(n)=A^n)]이다. 즉, 증명되었다.

무방향 그래프인 경우 인접행렬이 대칭행렬이므로 몇 제곱을 하든지 여전히 대칭행렬이다. 따라서 무방향 그래프에서 [math(A^n_{ab})], 즉 정점 [math(a)]에서 [math(b)]로 [math(n)] step 만에 이동하는 경로의 수는 [math(A^n_{ba})], 즉 정점 [math(b)]에서 [math(a)]로 [math(n)] step 만에 이동하는 경로의 수와 같음을 알 수 있다.

인접행렬 [math(A)]에 대해서 [math(A^2)]의 주대각선의 성분은 각 정점에서 출발하여 그 정점으로 2 step 만에 돌아오는 경우의 수를 의미하므로, 무방향 그래프에서는 해당 정점과 직접 연결된 다른 정점의 개수, 즉 간선의 개수를 나타내고, 방향 그래프에서는 해당 정점과 쌍방 직접 연결된 다른 정점의 개수를 나타낸다.

sparse graph가 아닌 경우, 즉 각 정점들이 어느 정도 이상 연결되어 있는 경우 [math(A^n)]에서 [math(n)]이 커질수록 각 성분의 값, 즉 특정 정점에서 다른 정점으로 [math(n)] step 만에 이동하는 경로의 수도 늘어나는 추세를 보인다. 각 정점들 간에 상당수 연결되어 있는 경우에는 기하급수적으로 늘어나는 추세를 보인다. sparse한 무방향 그래프이거나, 방향 그래프이더라도 일부 정점들이 cycle 형태로 연결된 그래프의 경우에는 같은 이동 경로를 무한히 반복할 수 있기 때문에 [math(n)]의 값이 커져도 각 성분의 값이 0으로 수렴하지 않지만, cycle이 없는 방향 그래프의 경우 그래프 내에서 정점의 개수 이상의 횟수로 이동하는 것이 불가능하므로 [math(n)]이 커지면 각 성분의 값이 0으로 수렴하며, 정점의 수 이상으로 커지면 반드시 영행렬이 된다. 정확히는 순서대로 이동할 수 있는 정점의 chain의 최대 길이가 [math(l)]인 경우, [math(A^{l-1})]까지는 영행렬이 아니며 [math(A^l)]부터 영행렬이다.

4.1. 예시

예를 들어 위 그림의 그래프 (가)의 인접행렬 [math(A_{가})]의 제곱은 다음과 같다.

[math(A_{가}^2=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix}^2=\begin{pmatrix}2 & 1 & 1 & 1 & 1 \\ 1 & 3 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 0 & 1\end{pmatrix})]

여기서 정점 C→정점 D로 2 step 만에 이동하는 경로의 수는 [math({A_{가}^2}_{34})] 성분과 같으므로 1개이다. 실제로 구해 보면 C→B→D의 1개밖에 존재하지 않는다. 주대각선을 보면 정점 A에서 자기 자신으로 2 step만에 이동하는 경로의 수는 [math({A_{가}^2}_{11}=2)]로, A와 이웃한 정점(B, D)의 개수와 같다. 실제로 경로를 찾아보면 A→B→A, A→D→A의 2가지뿐이다.

한편 이때 [math(A_{가})]의 세제곱은 다음과 같다.

[math(A_{가}^3=\begin{pmatrix}2 & 4 & 1 & 4 & 1 \\ 4 & 2 & 3 & 5 & 1 \\ 1 & 3 & 0 & 1 & 1 \\ 4 & 5 & 1 & 2 & 3 \\ 1 & 1 & 1 & 3 & 0\end{pmatrix})]

여기서 정점 B에서 D로 3 step 만에 이동하는 경로의 수는 [math({A_{가}^3}_{24})] 성분과 같으므로 5개이다. 실제로 찾아보면 B→A→B→D, B→C→B→D, B→D→A→D, B→D→B→D, B→D→E→D로 5가지이다.

방향 그래프인 그래프 (나)의 인접행렬 [math(A_{나})]의 제곱은 다음과 같다.

[math(A_{나}^2=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix}^2=\begin{pmatrix}0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0\end{pmatrix})]

여기서 정점 A→정점 D로 2 step 만에 이동하는 경로의 수는 [math({A_{나}^2}_{14})] 성분과 같으므로 1개이다. 실제로 구해 보면 A→B→D의 1개밖에 존재하지 않는다. 주대각선의 성분은 모두 0인데, 이는 모든 각 정점에 대해서 쌍방향으로 연결된 간선이 단 하나도 없다는 것을 의미한다.

한편, 여기서 [math(A_{나}^n)]은 [math(n)]이 3 이상일 때 영행렬이 되는데, 이것은 그래프 (나)에서 어떤 정점에서 3 step을 이동하여 다른 정점으로 이동할 수 있는 방법이 전혀 없음을 의미한다.

5. 특수한 인접행렬

단위행렬
어떤 그래프의 인접행렬이 단위행렬이라면 각 정점에 대해 자기 자신과 연결되는 간선만 존재하는 그래프이다. 이때 몇 step이든 간에 자기 자신으로만 이동할 수 있고 그 경우의 수는 자기 자신으로만 계속해서 이동하는 경우 1가지뿐이므로 인접행렬의 몇 제곱이든 간에 주대각선의 성분만 1이고 나머지 성분은 모두 0인 단위행렬이 된다.
영행렬
인접행렬이 영행렬이라는 것은 그래프의 간선이 하나도 없다는 뜻이다. 즉, 어떤 정점에서 자기 자신이든 다른 정점으로든 이동이 전혀 불가능하다는 것을 의미한다. 따라서 몇 step이든 간에 이동 자체가 불가능하므로 인접행렬의 몇 제곱이든 간에 똑같이 영행렬이다.
주대각선의 성분은 모두 0이고 나머지 성분은 모두 1인 경우
각 정점에서 모든 다른 각 정점으로의 쌍방으로 연결하는 간선이 존재하는 그래프의 인접행렬이다. 정점의 개수가 [math(v)]개일 때 간선의 개수는 [math(\displaystyle\frac{v(v+1)}{2})]개, 모든 성분의 합은 [math(v(v+1))]이다. 인접행렬을 [math(A)]라 하면 [math(A^n)]은 다음과 같다.
[math(A^n=\begin{pmatrix}\displaystyle\frac{(v-1)^n+v-1}{v} & \displaystyle\frac{(v-1)^n-1}{v} & \cdots & \displaystyle\frac{(v-1)^n-1}{v} \\ \displaystyle\frac{(v-1)^n-1}{v} & \displaystyle\frac{(v-1)^n+v-1}{v} & \cdots & \displaystyle\frac{(v-1)^n-1}{v} \\ \vdots & \vdots & \ddots & \vdots \\ \displaystyle\frac{(v-1)^n-1}{v} & \displaystyle\frac{(v-1)^n-1}{v} & \cdots & \displaystyle\frac{(v-1)^n+v-1}{v}\end{pmatrix})] (단, [math(n)]은 짝수)
[math(A^n=\begin{pmatrix}\displaystyle\frac{(v-1)^n+1-v}{v} & \displaystyle\frac{(v-1)^n+1}{v} & \cdots & \displaystyle\frac{(v-1)^n+1}{v} \\ \displaystyle\frac{(v-1)^n+1}{v} & \displaystyle\frac{(v-1)^n+1-v}{v} & \cdots & \displaystyle\frac{(v-1)^n+1}{v} \\ \vdots & \vdots & \ddots & \vdots \\ \displaystyle\frac{(v-1)^n+1}{v} & \displaystyle\frac{(v-1)^n+1}{v} & \cdots & \displaystyle\frac{(v-1)^n+1-v}{v}\end{pmatrix})] (단, [math(n)]은 홀수)
따라서 서로 다른 정점 간에 항상 간선이 있는 그래프에서 같은/다른 정점으로 [math(n)] step 만에 이동하는 경우의 수는 다음과 같다.

n이 짝수, 같은 정점 : [math(\displaystyle\frac{(v-1)^n+v-1}{v})]가지
n이 짝수, 다른 정점 : [math(\displaystyle\frac{(v-1)^n-1}{v})]가지
n이 홀수, 같은 정점 : [math(\displaystyle\frac{(v-1)^n+1-v}{v})]가지
n이 홀수, 다른 정점 : [math(\displaystyle\frac{(v-1)^n+1}{v})]가지

주대각선을 포함한 모든 성분이 1인 경우
모든 정점에서 자기 자신을 포함한 모든 정점으로 직접 연결되는 간선이 있는 그래프의 경우이다. 이때의 인접행렬을 [math(A)]라 하고, 정점의 개수를 [math(v)]라고 하면 [math(A^n)]은 모든 성분이 [math(v^{n-1})]인 행렬이다. 따라서 이 그래프에서 어떤 정점이든 한 정점에서 다른 정점으로 [math(n)] step 만에 이동하는 방법의 수는 [math(v^{n-1})]이다. 이것은 중복순열을 이용해서도 쉽게 알 수 있는데, [math(n)] step 동안 중간에 지나는 정점의 개수가 [math(n-1)]이고 자기 자신을 포함한 총 [math(v)]개의 정점 중 아무 것이나 선택할 수 있기 때문이다.
방향 그래프의 사이클
방향 그래프의 정점 [math(v_1, v_2, ..., v_p)]에 대해서 정점 [math((v_1, v_2), (v_2, v_3), ..., (v_{p-1}, v_p), (v_p, v_1))]이 그 순서대로만 연결된 사이클 형태인 경우 그 인접행렬 [math(A)]는 다음과 같다. (단, [math(v_1, v_2, ..., v_p)] 순서)
[math(A=\begin{pmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 0 & 0 & \cdots & 0 & 0\end{pmatrix})]
위와 같이 주대각선의 바로 오른쪽 성분만 1이고 나머지 성분은 모두 0인 것을 알 수 있다. 이때 [math(A^n)]은 이 그래프에서 [math(n)] step만큼 이동한 것을 나타내는데, 그 경우의 수는 각 정점 [math(v_i)]에서 [math(v_{i+n})]으로 이동하는 경우 하나뿐이다. 따라서 [math(A_{1,1+n}, A_{2,2+n}, ..., A_{p-1,n-1}, A_{p,n})] 성분의 값만 1이 되고 나머지는 모두 0이 된다. 정점의 개수인 [math(p)] step만큼 이동하는 경우는 각 정점에 대해서 다시 제자리로 돌아오는 한 가지 경우밖에 없으므로 [math(A^p=I)]가 된다. 예를 들어 [math(p=3)]인 경우 인접행렬은 다음과 같다.
[math(A=\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix})]
또한 인접행렬의 제곱, 세제곱은 차례로 다음과 같다. 이때 [math(A^3=I)]이다.
[math(A^2=\begin{pmatrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{pmatrix}, A^3=\begin{pmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix})]
방향 그래프에서 사이클이 없는 경우
방향 그래프의 정점 [math(v_1, v_2, ..., v_p)]에 대해서 정점 [math((v_1, v_2), (v_2, v_3), ..., (v_{p-1}, v_p))]가 그 순서대로만 연결된 사이클 형태인 경우 그 인접행렬 [math(A)]는 다음과 같다. 사이클인 경우에서 [math((v_p, v_1))]의 간선만 제외한 경우이다. (단, [math(v_1, v_2, ..., v_p)] 순서)
[math(A=\begin{pmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0\end{pmatrix})]
단지 성분 하나만 1에서 0이 되었을 뿐인데 계속 제곱했을 때의 결과는 천지 차이이다. 이때는 [math(v_p)]에서 [math(v_1)]로 이동할 수 없으므로 [math(A^n)]은 [math(A_{1,1+n}, A_{2,2+n}, ..., A_{p-n-1,p-1}, A_{p-n,p})] 성분의 값만 1이 되고 나머지는 모두 0이 된다. step 수가 가장 큰 경우는 [math(v_1)]에서 [math(v_p)]로 이동하는 경우이고 이때의 step 수는 [math(p-1)]이므로, [math(A^p)]부터는 반드시 영행렬이다. 예를 들어 [math(p=3)]인 경우 [math(A, A^2, A^3)]은 각각 다음과 같고, [math(A^3)]부터 영행렬이 된다.
[math(A=\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0\end{pmatrix}, A^2=\begin{pmatrix}0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{pmatrix}, A^3=\begin{pmatrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{pmatrix})]

인접행렬

1. 개요

2. 표현 방법

3. 성질

4. 경로의 개수

4.1. 예시

5. 특수한 인접행렬

6. 관련 문서

분류