인접행렬 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''인접 행렬'''(隣接行列, {{llang|en|adjacency matrix}})은 [[그래프]]에서 어느 [[꼭짓점]]들이 변으로 연결되었는지 나타내는 [[정사각 행렬]]이다.

== 정의 ==
<math>n</math>개의 꼭짓점이 있는 [[그래프]] <math>\Gamma</math>가 주어졌다고 하자. 그렇다면, [[실수 내적 공간]]
:<math>H = \mathbb R^{\operatorname V(\Gamma)}</math>
을 정의할 수 있다. <math>\Gamma</math>의 '''인접 행렬''' <math>\mathsf A_\Gamma</math>은 <math>H</math> 위의 [[선형 변환]] <Math>H \to H</math>이며, 그 성분은 다음과 같다.
:<math>\langle j|\mathsf A_\Gamma|i\rangle = \begin{cases}
1 & ij\in\operatorname E(\Gamma) \\
0 & ij\not\in\operatorname E(\Gamma) \\
\end{cases}</math>
(편의상 [[브라-켓 표기법]]을 사용하였다.)
이는 정의에 따라 [[대칭 연산자]]이다.

보다 일반적으로, 이와 같은 정의를 [[다중 그래프]]에 대하여 일반화할 수 있다. 이 경우, <math>(\mathsf A_\Gamma)_{ij}</math>는 <math>i</math>와 <math>j</math> 사이의 변의 수가 된다. 다만, 이 경우 문헌에 따라 고리(시작과 끝이 같은 변)를 세는 법이 다를 수 있다.

=== 화살집의 인접 행렬 ===
국소 유한 [[화살집 (수학)|화살집]] (즉, 임의의 두 꼭짓점 사이의 변 집합이 유한한 화살집) <math>Q</math>의 '''인접 행렬'''은 [[실수 선형 변환]]
:<math>\mathsf A_Q \colon \mathbb R^{\operatorname V(Q)} \to \mathbb R^{\operatorname V(Q)}</math>
이며, 그 성분은 다음과 같다.
:<math>\langle j|\mathsf A_Q|i\rangle = |\hom_Q(i,j)|</math>
즉, <math>A_{ij}</math>는 <math>v_i</math>에서 시작하고 <math>v_j</math>에서 끝나는 변의 수이다. 만약 이러한 변이 없다면 <math>A_{ij}=0</math>이다. 특히, <math>A_{ii}</math>는 꼭짓점 <math>v_i</math>에서 스스로로 가는 변의 수이다.
이는 물론 일반적으로 [[대칭 연산자]]가 아니다.

이에 따라, [[화살집 (수학)|화살집]] <math>Q</math>에 대하여,
:<math>\langle j|\mathsf A_Q^n|i\rangle \in\mathbb N</math>
은 꼭짓점 <math>i\in\operatorname V(\Gamma)</math>에서 꼭짓점 <math>j\in\operatorname V(\Gamma)</math>로 가는, 길이 <math>n</math>의 [[경로 (그래프 이론)|보행]]의 수이다. (여기서 편의상 [[브라-켓 표기법]]을 사용하였다.) 마찬가지로, [[대각합]]
:<math>\operatorname{tr}\mathsf A_Q^n</math>
은 길이 <math>n</math>의 순환의 수이다.

== 성질 ==
[[유한 그래프]] <math>\Gamma</math>의 인접 행렬의 [[고윳값]]의 집합을 <math>\Gamma</math>의 '''스펙트럼'''({{llang|en|spectrum}})이라고 하고, <math>\operatorname{Spec}\Gamma</math>로 표기하자.

그래프는 자기 고리를 가질 수 없으므로, 그래프의 인접 행렬의 대각 성분들은 모두 0이다. 이에 따라, 그 [[대각합]]은 항상 0이다. 즉, 스펙트럼의 원소들의 (중복수를 고려한) 합은 0이다.

<math>\Gamma</math>의 스펙트럼의 [[최댓값]] <math>\lambda_1(\Gamma)</math>은 <math>\Gamma</math>의 최대 차수(한 꼭짓점에 연결된 변의 수의 [[최댓값]])보다 같거나 작다.
:<math>\max\operatorname{Spec}(\Gamma) \le \max\deg_\Gamma = \max_{i\in\operatorname V(\Gamma)}\deg_\Gamma i</math>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
임의의 고윳값 <math>\lambda\in\operatorname{Spec}(\Gamma)</math> 및 이에 대응하는 고유 벡터 <math>|v\rangle \in \mathbb R^{\operatorname V(\Gamma)}</math>를 생각하자. 이제
:<math>i = \operatorname{arg\,max}_{j\in\operatorname V(\Gamma)}|\langle j|v\rangle|</math>
라고 하자. (최댓값이 되는 꼭짓점이 여러 개라면, 임의로 하나를 고른다.) 또한, 일반성을 잃지 않고 <math>\langle i|v\rangle>0</math>으로 가정할 수 있다. (아니라면, <Math>v \mapsto -v</math>를 취하면 된다.)

그렇다면,
:<math>\lambda \langle i|v\rangle
=\langle i|\mathsf A_\Gamma v\rangle
=\sum_{j\in\operatorname V(\Gamma)} \langle i|\mathsf A_\Gamma |j\rangle \langle j|v\rangle
\le \sum_{j\in\operatorname V(\Gamma)} \langle i|\mathsf A_\Gamma |j\rangle \langle i|v\rangle
= (\deg_\Gamma i) \langle i|v\rangle</math>
이다. 따라서,
:<math>\lambda \le \deg_\Gamma i \le \max\deg_\Gamma</math>
이다.
</div></div>

또한, 유한 [[정규 그래프]] <math>\Gamma</math>에 대하여, 이 부등식이 포화된다.
:<math>\max\operatorname{Spec}(\Gamma) = \max\deg_\Gamma = \max_{i\in\operatorname V(\Gamma)}\deg_\Gamma i</math>
정규 그래프의 경우 이 고윳값 <math>\max\deg_\Gamma</math>의 중복수는 <math>\Gamma</math>의 [[연결 성분]]의 수와 같다. 각 [[연결 성분]] <math>C\subseteq\Gamma</math>에 대응하는 [[고유 벡터]] <math>|\psi_C\rangle</math>는 각 [[연결 성분]] <math>C</math>에 대하여
:<math>\langle i|\psi_C\rangle = \begin{cases}
1 & i \in C \\
0 & i \not\in C
\end{cases}</math>
의 꼴이다. 특히,
:<math>(1,1,\dotsc,1)</math>
는 항상 고윳값 <math>\max\deg_\Gamma</math>의 [[고유 벡터]]를 이룬다.

=== 연산에 대한 호환 ===
임의의 두 그래프 <math>\Gamma</math>, <math>\Gamma'</math>에 대하여,
:<math>\operatorname{Spec} (\Gamma\sqcup \Gamma') = \operatorname{Spec} \Gamma \sqcup \operatorname{Spec}\Gamma'</math>
이다. 여기서 좌변은 그래프의 [[분리합집합]]이며, 우변은 [[중복집합]]의 [[분리합집합]]이다.

임의의 두 그래프 <math>\Gamma</math>, <math>\Gamma'</math>에 대하여,
:<math>\operatorname{Spec} (\Gamma\square \Gamma') =\{\lambda + \lambda' \colon \lambda \in \operatorname{Spec} \Gamma , \;\lambda'\in\operatorname{Spec}\Gamma'\}
</math>
이다. 여기서 <math>\square</math>는 그래프의 [[그래프 데카르트 곱]]을 뜻한다.

=== 그래프 동형 ===
[[파일:Isospectral enneahedra.svg|섬네일|오른쪽|같은 스펙트럼을 갖지만 서로 동형이 아닌 두 그래프]]
같은 수의 꼭짓점을 갖는 임의의 두 [[유한 그래프]] <math>\Gamma</math>, <math>\Gamma'</math>에 대하여, 두 그래프가 동형일 [[필요 충분 조건]]은
:<math>P\mathsf A_\Gamma = \mathsf A_{\Gamma'}P</math>
인 [[치환행렬]]
:<math>P \colon \mathbb R^{\operatorname V(\Gamma)} \to \mathbb R^{\operatorname V(\Gamma')}</math>
가 존재하는 것이다.

반면, 서로 동형이 아니지만, 스펙트럼이 같은 그래프들이 알려져 있다.

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

== 예 ==
다음과 같은 [[유한 그래프]]를 생각하자.
:[[파일:6n-graf.svg|200px]]
이 그래프의 인접 행렬은 다음과 같은 [[대칭 행렬]]이다.
:<math>A=\begin{pmatrix}
0 & 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}</math>
이 그래프의 스펙트럼은 다음과 같다.
:<math>\{2.54, 1.08, 0.26, -0.54, -1.21, -2.14 \}</math>
이들의 합은 0이며, 그 최댓값 2.54는 그래프의 최대 차수 3보다 작다.

=== 무변 그래프 ===
[[무변 그래프]] <math>\bar\mathsf K_n</math>의 인접 행렬은 영행렬이다.
:<math>\mathsf A_{\bar\mathsf K_n} = 0</math>
그 스펙트럼의 유일한 원소는 0이며, 그 중복수는 <math>n</math>이다.

=== 완전 그래프 ===
완전 그래프 <math>\mathsf K_n</math>의 인접 행렬은 다음과 같은 꼴이다.
:<math>\mathsf A_{\mathsf K_n} = \mu_{n\times n} - 1_{n\times n}</math>
여기서 <math>\mu</math>는 모든 성분이 1인 [[행렬]]이다.

그 스펙트럼은 다음과 같다.
:<math>\operatorname{Spec}\mathsf A_{\mathsf K_n} = \{n-1, \underbrace{-1, -1,\dotsc,-1}_{n-1} \}</math>

=== 완전 이분 그래프 ===
[[완전 이분 그래프]] <math>\mathsf K_{m,n}</math>의 인접 행렬은 다음과 같은 꼴이다.
:<math>\mathsf A_{\mathsf K_{m,n}} = \begin{pmatrix}
0_{m\times m}& \mu_{m\times n} \\
\mu_{n\times m}&0_{n\times n}
\end{pmatrix}</math>
여기서 <math>\mu</math>는 모든 성분이 1인 [[행렬]]이다.

[[완전 이분 그래프]] <math>\mathsf K_{m,n}</math>의 스펙트럼은 다음과 같다.
:<math>\operatorname{Spec}\mathsf K_{m,n} = \{+ \sqrt{mn}, -\sqrt{mn},\underbrace{ 0,0,\dotsc,0}_{m+n-2}\}</math>
고윳값 <Math>\pm\sqrt{mn}</math>의 고유 벡터는
:<math>\sqrt n\sum_{i\in C_m} |i\rangle \pm \sqrt m\sum_{j\in C_n} |j\rangle </math>
이다. (여기서 <math>C_m, C_n \subseteq \operatorname V(\Gamma)</math>는 완전 이분 그래프의 꼭짓점 집합의 [[집합의 분할|분할]]이다.)

=== 순환 그래프 ===
[[순환 그래프]] <Math>\mathsf C_n</math>의 인접 행렬은 다음과 같다.
:<math>\mathsf C_n = \sum_{i = 0}^{n-1} (|i\rangle\langle i+1|+|i+1\rangle\langle i|)</math>
(여기서 <Math>i \in \mathbb Z/(n)</math>으로 여긴다. 즉, <math>n\equiv 0</math>이다.)

그 스펙트럼은 다음과 같다.
:<math>\operatorname{Spec}\mathsf C_n = \left\{2 \cos \frac{2\pi i}n \colon i \in \{0,1,\dotsc,n-1\} \right\}</math>
특히, <math>\pm2</math>가 아닌 모든 고윳값들의 중복수는 2이다. (<math>\pm2</math>의 중복수는 1이다.)

=== 경로 그래프 ===
<math>n</math>개의 꼭짓점을 갖는 [[경로 그래프]] <math>\mathsf P_n</math>의 인접 행렬은 다음과 같다.
:<math>\mathsf P_n = \sum_{i=1}^{n-1} (|i\rangle \langle i+1| + |i+1\rangle \langle i|)</math>

그 스펙트럼은 다응과 같다.
:<math>\operatorname{Spec}\mathsf P_n = \left\{2 \cos \frac{\pi i}{n+1} \colon i \in \{1,\dotsc,n\}\right\}</math>
특히, 만약 <math>\lambda</math>가 스펙트럼에 속한다면 <math>-\lambda</math>도 스펙트럼에 속한다. 모든 고윳값의 중복수는 1이다.

=== 딘킨 도표 ===
ADE형의 [[단순 리 대수]] <math>\mathfrak g</math>의 [[딘킨 도표]]는 [[그래프]]를 이룬다. 이 그래프의 스펙트럼은 다음과 같은 꼴이다.
:<math>\left\{2 \cos \frac{(d_i-1)\pi}{\mathsf h(\mathfrak g)} \colon i\in\{1,\dotsc,\operatorname{rank}\mathfrak g\}\right\}</math>
여기서
* <math>\operatorname{rank}\mathfrak g</math>는 <math>\mathfrak g</math>의 계수(<math>\mathfrak g</math>의 최대 아벨 부분 리 대수의 차원 = 딘킨 도표의 꼭짓점의 수)이다.
* <math>\mathsf h(\mathfrak g)</math>는 <Math>\mathfrak g</math>의 [[콕서터 수]]이다.
* <math>d_i</math>는 <math>\mathfrak g</math>의 딘킨 도표의 각 꼭짓점에 대응되는 차수들이다. 예를 들어, [[리 대수]] <math>\mathfrak d_n</math>의 경우 <math>d_i = 2,4,6,\dotsc,2n-2</math>이다.

== 같이 보기 ==
* [[그래프 라플라스 연산자]]

== 외부 링크 ==
* {{eom|title=Adjacency matrix}}
* {{매스월드|id=AdjacencyMatrix|title=Adjacency matrix}}
* {{웹 인용|url= https://www.win.tue.nl/~aeb/2WF02/easyspectra.pdf | 제목=Some simple graph spectra | 이름= Andries E. |성=Brouwer | 언어=en}}

{{그래프 표현}}

{{전거 통제}}

[[분류:그래프 이론]]
[[분류:행렬]]
[[분류:대수적 그래프 이론]]
[[분류:그래프 자료 구조]]