인접행렬

위키백과, 우리 모두의 백과사전.
(인접 행렬에서 넘어옴)
이동: 둘러보기, 검색

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

정의[편집]

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

  • 인 경우 1, 아닌 경우 0이다.
  • 대각 원소 는 꼭짓점 에서 스스로로 가는 변의 수이다.

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

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

  • 에서 시작하고 에서 끝나는 변의 수이다. 만약 이러한 변이 없다면 이다.
  • 대각 원소 는 꼭짓점 에서 스스로로 가는 변의 수이다.

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

성질[편집]

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

[편집]

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

6n-graph2.svg

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

바깥 고리[편집]