정의
인접행렬(adjacency matrix)은 그래프 이론에서 그래프의 구조를 표현하는 데 사용되는 정사각행렬이다. 그래프의 각 정점(노드) 사이의 연결 관계를 0과 1로 나타내며, 두 정점 사이에 간선(에지)이 존재하면 1, 존재하지 않으면 0으로 표시한다. 가중치 그래프의 경우에는 연결 여부에 따라 가중치 값을 사용하기도 한다.
개요
인접행렬은 그래프를 수학적으로 표현하는 방식 중 하나로, 주로 컴퓨터 과학, 이산수학, 네트워크 이론 등에서 활용된다. n개의 정점을 가진 그래프의 경우, 인접행렬은 n×n 크기의 정사각행렬로 구성되며, 행과 열은 각각 그래프의 정점을 나타낸다. 무향 그래프에서 인접행렬은 대칭행렬이 되며, 유향 그래프에서는 대칭성이 보장되지 않는다. 또한, 단순 그래프에서는 자기 자신으로의 간선(자기 루프)이 없는 경우 주대각선의 원소가 모두 0이 되지만, 자기 루프가 허용되는 경우에는 해당 원소가 1이 될 수 있다.
어원/유래
‘인접행렬’이라는 용어는 영어 'adjacency matrix'를 직역한 것으로 구성된다. 여기서 'adjacency'는 '인접성', '접해 있음'을 의미하며, 'matrix'는 '행렬'을 뜻한다. 이 용어는 20세기 초반 그래프 이론의 발전 과정에서 수학자들에 의해 정립되었으며, 특히 레온하르트 오일러의 그래프 관련 연구를 바탕으로 한 후속 연구에서 체계화되었다고 알려져 있다. 다만, 'adjacency matrix'라는 표현이 처음 사용된 정확한 문헌과 시기는 확인되지 않는다.
특징
- 인접행렬은 그래프의 구조를 명확하고 체계적으로 표현할 수 있다는 장점이 있다.
- 두 정점 사이의 연결 여부를 상수 시간(O(1))에 확인할 수 있어 탐색이 빠르다.
- 그러나 정점의 수가 많을 경우, 희소 그래프(sparse graph)에서도 n² 크기의 메모리를 필요로 하므로 메모리 효율이 낮을 수 있다.
- 행렬의 연산을 통해 그래프의 경로 수, 연결성 등을 분석할 수 있다. 예를 들어, 인접행렬을 k제곱하면 두 정점 간에 길이가 k인 경로의 수를 구할 수 있다.
관련 항목
- 그래프 이론
- 인접 리스트
- 가중치 행렬
- 라플라시안 행렬
- 그래프의 표현 방법