인접행렬

그래프 이론에서 **인접 행렬**(隣接行列, adjacency matrix)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다.
# 정의
n개의 꼭짓점이 있는 그래프 \Gamma가 주어졌다고 하자. 그렇다면, 실수 내적 공간 :H = \mathbb R^{\operatorname V(\Gamma)} 을 정의할 수 있다. \Gamma의 **인접 행렬** \mathsf A_\Gamma은 H 위의 선형 변환 H \to H이며, 그 성분은 다음과 같다. :\langle j|\mathsf A_\Gamma|i\rangle = \begin{cases} 1 & ij\in\operatorname E(\Gamma) \\\ 0 & ij\not\in\operatorname E(\Gamma) \\\ \end{cases} (편의상 브라-켓 표기법을 사용하였다.) 이는 정의에 따라 대칭 연산자이다. 보다 일반적으로, 이와 같은 정의를 다중 그래프에 대하여 일반화할 수 있다. 이 경우, (\mathsf A_\Gamma)_{ij}는 i와 j 사이의 변의 수가 된다. 다만, 이 경우 문헌에 따라 고리(시작과 끝이 같은 변)를 세는 법이 다를 수 있다.
## 화살집의 인접 행렬
국소 유한 화살집 (즉, 임의의 두 꼭짓점 사이의 변 집합이 유한한 화살집) Q의 **인접 행렬**은 실수 선형 변환 :\mathsf A_Q \colon \mathbb R^{\operatorname V(Q)} \to \mathbb R^{\operatorname V(Q)} 이며, 그 성분은 다음과 같다. :\langle j|\mathsf A_Q|i\rangle = |\hom_Q(i,j)| 즉, A_{ij}는 v_i에서 시작하고 v_j에서 끝나는 변의 수이다. 만약 이러한 변이 없다면 A_{ij}=0이다. 특히, A_{ii}는 꼭짓점 v_i에서 스스로로 가는 변의 수이다. 이는 물론 일반적으로 대칭 연산자가 아니다. 이에 따라, 화살집 Q에 대하여, :\langle j|\mathsf A_Q^n|i\rangle \in\mathbb N 은 꼭짓점 i\in\operatorname V(\Gamma)에서 꼭짓점 j\in\operatorname V(\Gamma)로 가는, 길이 n의 보행의 수이다. (여기서 편의상 브라-켓 표기법을 사용하였다.) 마찬가지로, 대각합 :\operatorname{tr}\mathsf A_Q^n 은 길이 n의 순환의 수이다.
# 성질
유한 그래프 \Gamma의 인접 행렬의 고윳값의 집합을 \Gamma의 **스펙트럼**(spectrum)이라고 하고, \operatorname{Spec}\Gamma로 표기하자. 그래프는 자기 고리를 가질 수 없으므로, 그래프의 인접 행렬의 대각 성분들은 모두 0이다. 이에 따라, 그 대각합은 항상 0이다. 즉, 스펙트럼의 원소들의 (중복수를 고려한) 합은 0이다. \Gamma의 스펙트럼의 최댓값 \lambda_1(\Gamma)은 \Gamma의 최대 차수(한 꼭짓점에 연결된 변의 수의 최댓값)보다 같거나 작다. :\max\operatorname{Spec}(\Gamma) \le \max\deg_\Gamma = \max_{i\in\operatorname V(\Gamma)}\deg_\Gamma i

**증명:**

임의의 고윳값 \lambda\in\operatorname{Spec}(\Gamma) 및 이에 대응하는 고유 벡터 |v\rangle \in \mathbb R^{\operatorname V(\Gamma)}를 생각하자. 이제 :i = \operatorname{arg\,max}_{j\in\operatorname V(\Gamma)}|\langle j|v\rangle| 라고 하자. (최댓값이 되는 꼭짓점이 여러 개라면, 임의로 하나를 고른다.) 또한, 일반성을 잃지 않고 \langle i|v\rangle>0으로 가정할 수 있다. (아니라면, v \mapsto -v를 취하면 된다.) 그렇다면, :\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 이다. 따라서, :\lambda \le \deg_\Gamma i \le \max\deg_\Gamma 이다.

또한, 유한 정규 그래프 \Gamma에 대하여, 이 부등식이 포화된다. :\max\operatorname{Spec}(\Gamma) = \max\deg_\Gamma = \max_{i\in\operatorname V(\Gamma)}\deg_\Gamma i 정규 그래프의 경우 이 고윳값 \max\deg_\Gamma의 중복수는 \Gamma의 연결 성분의 수와 같다. 각 연결 성분 C\subseteq\Gamma에 대응하는 고유 벡터 |\psi_C\rangle는 각 연결 성분 C에 대하여 :\langle i|\psi_C\rangle = \begin{cases} 1 & i \in C \\\ 0 & i \not\in C \end{cases} 의 꼴이다. 특히, :(1,1,\dotsc,1) 는 항상 고윳값 \max\deg_\Gamma의 고유 벡터를 이룬다.
## 연산에 대한 호환
임의의 두 그래프 \Gamma, \Gamma'에 대하여, :\operatorname{Spec} (\Gamma\sqcup \Gamma') = \operatorname{Spec} \Gamma \sqcup \operatorname{Spec}\Gamma' 이다. 여기서 좌변은 그래프의 분리합집합이며, 우변은 중복집합의 분리합집합이다. 임의의 두 그래프 \Gamma, \Gamma'에 대하여, :\operatorname{Spec} (\Gamma\square \Gamma') =\\{\lambda + \lambda' \colon \lambda \in \operatorname{Spec} \Gamma , \;\lambda'\in\operatorname{Spec}\Gamma'\\} 이다. 여기서 \square는 그래프의 그래프 데카르트 곱을 뜻한다.
## 그래프 동형
같은 스펙트럼을 갖지만 서로 동형이 아닌 두 그래프 같은 수의 꼭짓점을 갖는 임의의 두 유한 그래프 \Gamma, \Gamma'에 대하여, 두 그래프가 동형일 필요 충분 조건은 :P\mathsf A_\Gamma = \mathsf A_{\Gamma'}P 인 치환행렬 :P \colon \mathbb R^{\operatorname V(\Gamma)} \to \mathbb R^{\operatorname V(\Gamma')} 가 존재하는 것이다. 반면, 서로 동형이 아니지만, 스펙트럼이 같은 그래프들이 알려져 있다.
# 응용
인접 행렬의 특정 원소에 접근하는 데 걸리는 시간이 상수 시간이라면 꼭짓점 i에서 꼭짓점 j로 가는 변이 있는지를 상수 시간에 알 수 있다. 꼭짓점의 개수를 n이라고 할 때 인접행렬을 만드는 데 O(n^2)시간을 쓰게 되므로, 인접행렬을 이용한 그래프 알고리즘의 시간 복잡도는 이보다 더 좋을 수 없다. 따라서 변이 희소한 경우에는 인접 리스트 표현 방식이 유리하다.
# 예
다음과 같은 유한 그래프를 생각하자. : 이 그래프의 인접 행렬은 다음과 같은 대칭 행렬이다. :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} 이 그래프의 스펙트럼은 다음과 같다. :\\{2.54, 1.08, 0.26, -0.54, -1.21, -2.14 \\} 이들의 합은 0이며, 그 최댓값 2.54는 그래프의 최대 차수 3보다 작다.
## 무변 그래프
무변 그래프 \bar\mathsf K_n의 인접 행렬은 영행렬이다. :\mathsf A_{\bar\mathsf K_n} = 0 그 스펙트럼의 유일한 원소는 0이며, 그 중복수는 n이다.
## 완전 그래프
완전 그래프 \mathsf K_n의 인접 행렬은 다음과 같은 꼴이다. :\mathsf A_{\mathsf K_n} = \mu_{n\times n} - 1_{n\times n} 여기서 \mu는 모든 성분이 1인 행렬이다. 그 스펙트럼은 다음과 같다. :\operatorname{Spec}\mathsf A_{\mathsf K_n} = \\{n-1, \underbrace{-1, -1,\dotsc,-1}_{n-1} \\}
## 완전 이분 그래프
완전 이분 그래프 \mathsf K_{m,n}의 인접 행렬은 다음과 같은 꼴이다. :\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} 여기서 \mu는 모든 성분이 1인 행렬이다. 완전 이분 그래프 \mathsf K_{m,n}의 스펙트럼은 다음과 같다. :\operatorname{Spec}\mathsf K_{m,n} = \\{+ \sqrt{mn}, -\sqrt{mn},\underbrace{ 0,0,\dotsc,0}_{m+n-2}\\} 고윳값 \pm\sqrt{mn}의 고유 벡터는 :\sqrt n\sum_{i\in C_m} |i\rangle \pm \sqrt m\sum_{j\in C_n} |j\rangle 이다. (여기서 C_m, C_n \subseteq \operatorname V(\Gamma)는 완전 이분 그래프의 꼭짓점 집합의 분할이다.)
## 순환 그래프
순환 그래프 \mathsf C_n의 인접 행렬은 다음과 같다. :\mathsf C_n = \sum_{i = 0}^{n-1} (|i\rangle\langle i+1|+|i+1\rangle\langle i|) (여기서 i \in \mathbb Z/(n)으로 여긴다. 즉, n\equiv 0이다.) 그 스펙트럼은 다음과 같다. :\operatorname{Spec}\mathsf C_n = \left\\{2 \cos \frac{2\pi i}n \colon i \in \\{0,1,\dotsc,n-1\\} \right\\} 특히, \pm2가 아닌 모든 고윳값들의 중복수는 2이다. (\pm2의 중복수는 1이다.)
## 경로 그래프
n개의 꼭짓점을 갖는 경로 그래프 \mathsf P_n의 인접 행렬은 다음과 같다. :\mathsf P_n = \sum_{i=1}^{n-1} (|i\rangle \langle i+1| + |i+1\rangle \langle i|) 그 스펙트럼은 다응과 같다. :\operatorname{Spec}\mathsf P_n = \left\\{2 \cos \frac{\pi i}{n+1} \colon i \in \\{1,\dotsc,n\\}\right\\} 특히, 만약 \lambda가 스펙트럼에 속한다면 -\lambda도 스펙트럼에 속한다. 모든 고윳값의 중복수는 1이다.
## 딘킨 도표
ADE형의 단순 리 대수 \mathfrak g의 딘킨 도표는 그래프를 이룬다. 이 그래프의 스펙트럼은 다음과 같은 꼴이다. :\left\\{2 \cos \frac{(d_i-1)\pi}{\mathsf h(\mathfrak g)} \colon i\in\\{1,\dotsc,\operatorname{rank}\mathfrak g\\}\right\\} 여기서 * \operatorname{rank}\mathfrak g는 \mathfrak g의 계수(\mathfrak g의 최대 아벨 부분 리 대수의 차원 = 딘킨 도표의 꼭짓점의 수)이다. * \mathsf h(\mathfrak g)는 \mathfrak g의 콕서터 수이다. * d_i는 \mathfrak g의 딘킨 도표의 각 꼭짓점에 대응되는 차수들이다. 예를 들어, 리 대수 \mathfrak d_n의 경우 d_i = 2,4,6,\dotsc,2n-2이다.