인접 행렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

그래프 이론에서, 인접 행렬(隣接行列, 영어: adjacency matrix)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각행렬이다.

정의[편집]

n개의 꼭짓점이 있는 그래프 G인접 행렬 An\times n 정사각행렬이며, 그 성분들은 다음과 같다. G의 꼭짓점들에 대하여 임의의 순서를 매기자.

  • A_{ij}v_iv_j\in E(G)인 경우 1, 아닌 경우 0이다.
  • 대각 원소 A_{ii}는 꼭짓점 v_i에서 스스로로 가는 변의 수이다.

(단순) 그래프의 인접 행렬은 항상 대칭행렬이며, 대각 성분은 모두 0이다.

n개의 꼭짓점이 있는 유향 그래프 \Gamma인접 행렬 An\times n 정사각행렬이며, 그 성분들은 다음과 같다. \Gamma의 꼭짓점들에 대하여 임의의 순서를 매기자.

  • A_{ij}v_i에서 시작하고 v_j에서 끝나는 변의 수이다. 만약 이러한 변이 없다면 A_{ij}=0이다.
  • 대각 원소 A_{ii}는 꼭짓점 v_i에서 스스로로 가는 변의 수이다.

유향 그래프의 인접 행렬은 대칭행렬이 아닐 수 있다.

성질[편집]

인접 행렬의 특정 원소에 접근하는 데 걸리는 시간이 상수 시간이라면 꼭짓점 i에서 꼭짓점 j로 가는 변이 있는지를 상수 시간에 알 수 있다. 꼭짓점의 개수를 n이라고 할 때 인접 행렬을 만드는 데 O(n^2)시간을 쓰게 되므로, 인접 행렬을 이용한 그래프 알고리즘의 시간 복잡도는 이보다 더 좋을 수 없다. 따라서 변이 희소한 경우에는 인접 리스트 표현 방식이 유리하다.

[편집]

다음과 같은 고리 그래프를 생각하자.

6n-graph2.svg

이 그래프의 인접 행렬은 다음과 같은 대칭행렬이다.

A=\begin{pmatrix}
1 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}

바깥 고리[편집]