개요
인접행렬(隣接行列, 영어: adjacency matrix)은 그래프 이론과 컴퓨터 과학에서 사용되는 개념으로, 그래프에서 어느 꼭짓점(정점)들이 변(간선)으로 연결되었는지를 나타내는 정사각 행렬이다. 행과 열에 꼭짓점을 대응시키고, 행렬의 성분으로 두 꼭짓점 사이에 간선의 존재 여부를 기록하는 방식으로 그래프의 구조를 표현한다.
정의
n개의 꼭짓점을 가진 그래프에서, 인접행렬은 크기가 n × n인 행렬로 정의된다. 일반적으로 단순 그래프(simple graph)의 경우 성분은 다음과 같이 정의된다.
- 두 꼭짓점 i와 j 사이에 간선이 존재하면 Aᵢⱼ = 1
- 간선이 존재하지 않으면 Aᵢⱼ = 0
이 정의에 따라 단순 그래프의 인접행렬은 (0,1)-행렬이며, 자기 자신으로 돌아오는 간선(고리)이 없는 그래프에서는 대각선 성분이 모두 0이 된다. 무방향 그래프의 인접행렬은 Aᵢⱼ = Aⱼᵢ를 만족하는 대칭 행렬이 되고, 방향 그래프의 경우 일반적으로 대칭이 아니다.
다중 그래프에 대해서는 Aᵢⱼ를 두 꼭짓점 사이의 간선 수로 확장할 수 있으며, 가중치가 부여된 그래프에서는 행렬의 성분에 간선의 가중치를 기록하는 방식(가중 인접행렬)도 널리 사용된다.
성질
- 무방향 그래프의 인접행렬은 대칭 행렬이므로, 모든 고윳값은 실수이다.
- 그래프의 인접행렬의 고윳값 집합을 그래프의 스펙트럼(spectrum)이라고 하며, 이를 다루는 분야를 스펙트럼 그래프 이론이라고 한다.
- 인접행렬 A의 거듭제곱 Aⁿ의 (i, j) 성분은 꼭짓점 i에서 꼭짓점 j로 가는 길이 n의 보행(walk)의 수를 나타낸다.
- 그래프가 동형일 필요충분조건은 적절한 치환행렬 P에 대하여 인접행렬이 P A P⁻¹의 관계로 연결되는 것이다. 단, 인접행렬(스펙트럼)이 같아도 동형이 아닌 그래프가 존재한다.
- 무방향 그래프에서 인접행렬의 모든 성분의 합은 간선 수의 2배와 같다.
컴퓨터 과학에서의 이용
그래프를 컴퓨터에 저장하는 표현 방식 중 하나로, 꼭짓점 수가 V일 때 공간 복잡도는 O(V²)이다. 두 꼭짓점 간의 간선 존재 여부를 상수 시간(O(1))에 확인할 수 있어 간선이 많은 밀집 그래프(dense graph)에 적합하며, 간선이 희소한 그래프에서는 인접 리스트 방식이 공간적으로 유리하다. 너비 우선 탐색, 깊이 우선 탐색 등의 그래프 탐색 알고리즘과 플로이드-워셜 알고리즘 등에서 활용된다.
예
꼭짓점 1, 2, 3으로 구성되고 간선 (1,2), (2,3)을 가지는 경로 그래프의 인접행렬은 다음과 같다.
0 1 0
A = 1 0 1
0 1 0
어원 및 표기
한국어 표기 "인접행렬"은 영어 adjacency matrix의 대역어로, 두 꼭짓점이 간선으로 직접 연결된 상태를 뜻하는 "인접(adjacent)"과 행렬(matrix)의 합성어이다. 한자 표기는 隣接行列(린접행렬)이다.
같이 보기
- 인접 리스트
- 그래프 라플라스 행렬
- 스펙트럼 그래프 이론
참고 자료
- Harary, Frank (1969). Graph Theory. Addison-Wesley.
- Wolfram MathWorld, "Adjacency Matrix"
- Encyclopedia of Mathematics (Springer), "Adjacency matrix"
