인접행렬

틀:위키데이터 속성 추적 그래프 이론에서 인접 행렬(隣接行列, 틀:Llang)은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다.

정의

$n$개의 꼭짓점이 있는 그래프 $\mathrm{\Gamma }$가 주어졌다고 하자. 그렇다면, 실수 내적 공간

$H={ℝ}^{\mathrm{V}(\mathrm{\Gamma })}$

을 정의할 수 있다. $\mathrm{\Gamma }$의 인접 행렬 ${𝖠}_{\mathrm{\Gamma }}$은 $H$ 위의 선형 변환 $H\to H$이며, 그 성분은 다음과 같다.

$⟨j|{𝖠}_{\mathrm{\Gamma }}|i⟩=\{\begin{array}{cc}1& ij\in \mathrm{E}(\mathrm{\Gamma })\\ 0& ij\in ̸\mathrm{E}(\mathrm{\Gamma })\end{array}$

(편의상 브라-켓 표기법을 사용하였다.) 이는 정의에 따라 대칭 연산자이다.

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

화살집의 인접 행렬

국소 유한 화살집 (즉, 임의의 두 꼭짓점 사이의 변 집합이 유한한 화살집) $Q$의 인접 행렬은 실수 선형 변환

${𝖠}_Q:{ℝ}^{\mathrm{V}(Q)}\to {ℝ}^{\mathrm{V}(Q)}$

이며, 그 성분은 다음과 같다.

$⟨j|{𝖠}_Q|i⟩=|{\mathrm{hom}}_Q(i,j)|$

즉, $A_{ij}$는 $v_i$에서 시작하고 $v_j$에서 끝나는 변의 수이다. 만약 이러한 변이 없다면 $A_{ij}=0$이다. 특히, $A_{ii}$는 꼭짓점 $v_i$에서 스스로로 가는 변의 수이다. 이는 물론 일반적으로 대칭 연산자가 아니다.

이에 따라, 화살집 $Q$에 대하여,

$⟨j|{𝖠}_Q^n|i⟩\in \mathbb{N}$

은 꼭짓점 $i\in \mathrm{V}(\mathrm{\Gamma })$에서 꼭짓점 $j\in \mathrm{V}(\mathrm{\Gamma })$로 가는, 길이 $n$의 보행의 수이다. (여기서 편의상 브라-켓 표기법을 사용하였다.) 마찬가지로, 대각합

$\mathrm{tr}{𝖠}_Q^n$

은 길이 $n$의 순환의 수이다.

성질

유한 그래프 $\mathrm{\Gamma }$의 인접 행렬의 고윳값의 집합을 $\mathrm{\Gamma }$의 스펙트럼(틀:Llang)이라고 하고, $\mathrm{Spec}\mathrm{\Gamma }$로 표기하자.

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

$\mathrm{\Gamma }$의 스펙트럼의 최댓값 ${\lambda }_1(\mathrm{\Gamma })$은 $\mathrm{\Gamma }$의 최대 차수(한 꼭짓점에 연결된 변의 수의 최댓값)보다 같거나 작다.

$\max \mathrm{Spec}(\mathrm{\Gamma })\le \max {\mathrm{deg}}_{\mathrm{\Gamma }}=\underset{i\in \mathrm{V}(\mathrm{\Gamma })}{\max }{\mathrm{deg}}_{\mathrm{\Gamma }}i$

증명:

임의의 고윳값 $\lambda \in \mathrm{Spec}(\mathrm{\Gamma })$ 및 이에 대응하는 고유 벡터 $|v⟩\in {ℝ}^{\mathrm{V}(\mathrm{\Gamma })}$를 생각하자. 이제

$i={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}_{j\in \mathrm{V}(\mathrm{\Gamma })}|⟨j|v⟩|$

라고 하자. (최댓값이 되는 꼭짓점이 여러 개라면, 임의로 하나를 고른다.) 또한, 일반성을 잃지 않고 $⟨i|v⟩>0$으로 가정할 수 있다. (아니라면, $v\mapsto -v$를 취하면 된다.)

그렇다면,

$\lambda ⟨i|v⟩=⟨i|{𝖠}_{\mathrm{\Gamma }}v⟩=\sum _{j\in \mathrm{V}(\mathrm{\Gamma })}⟨i|{𝖠}_{\mathrm{\Gamma }}|j⟩⟨j|v⟩\le \sum _{j\in \mathrm{V}(\mathrm{\Gamma })}⟨i|{𝖠}_{\mathrm{\Gamma }}|j⟩⟨i|v⟩=({\mathrm{deg}}_{\mathrm{\Gamma }}i)⟨i|v⟩$

이다. 따라서,

$\lambda \le {\mathrm{deg}}_{\mathrm{\Gamma }}i\le \max {\mathrm{deg}}_{\mathrm{\Gamma }}$

이다.

또한, 유한 정규 그래프 $\mathrm{\Gamma }$에 대하여, 이 부등식이 포화된다.

$\max \mathrm{Spec}(\mathrm{\Gamma })=\max {\mathrm{deg}}_{\mathrm{\Gamma }}=\underset{i\in \mathrm{V}(\mathrm{\Gamma })}{\max }{\mathrm{deg}}_{\mathrm{\Gamma }}i$

정규 그래프의 경우 이 고윳값 $\max {\mathrm{deg}}_{\mathrm{\Gamma }}$의 중복수는 $\mathrm{\Gamma }$의 연결 성분의 수와 같다. 각 연결 성분 $C\subseteq \mathrm{\Gamma }$에 대응하는 고유 벡터 $|{\psi }_C⟩$는 각 연결 성분 $C$에 대하여

$⟨i|{\psi }_C⟩=\{\begin{array}{cc}1& i\in C\\ 0& i\in ̸C\end{array}$

의 꼴이다. 특히,

$(1,1,\dots ,1)$

는 항상 고윳값 $\max {\mathrm{deg}}_{\mathrm{\Gamma }}$의 고유 벡터를 이룬다.

연산에 대한 호환

임의의 두 그래프 $\mathrm{\Gamma }$, ${\mathrm{\Gamma }}^{\prime }$에 대하여,

$\mathrm{Spec}(\mathrm{\Gamma }\bigsqcup {\mathrm{\Gamma }}^{\prime })=\mathrm{Spec}\mathrm{\Gamma }\bigsqcup \mathrm{Spec}{\mathrm{\Gamma }}^{\prime }$

이다. 여기서 좌변은 그래프의 분리합집합이며, 우변은 중복집합의 분리합집합이다.

임의의 두 그래프 $\mathrm{\Gamma }$, ${\mathrm{\Gamma }}^{\prime }$에 대하여,

$\mathrm{Spec}(\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime })=\{\lambda +{\lambda }^{\prime }:\lambda \in \mathrm{Spec}\mathrm{\Gamma },{\lambda }^{\prime }\in \mathrm{Spec}{\mathrm{\Gamma }}^{\prime }\}$

이다. 여기서 $◻$는 그래프의 그래프 데카르트 곱을 뜻한다.

그래프 동형

같은 스펙트럼을 갖지만 서로 동형이 아닌 두 그래프

같은 수의 꼭짓점을 갖는 임의의 두 유한 그래프 $\mathrm{\Gamma }$, ${\mathrm{\Gamma }}^{\prime }$에 대하여, 두 그래프가 동형일 필요 충분 조건은

$P{𝖠}_{\mathrm{\Gamma }}={𝖠}_{{\mathrm{\Gamma }}^{\prime }}P$

인 치환행렬

$P:{ℝ}^{\mathrm{V}(\mathrm{\Gamma })}\to {ℝ}^{\mathrm{V}({\mathrm{\Gamma }}^{\prime })}$

가 존재하는 것이다.

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

응용

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

예

다음과 같은 유한 그래프를 생각하자.

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

$A=\left(\begin{array}{cccccc}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{array}\right)$

이 그래프의 스펙트럼은 다음과 같다.

$\{2.54,1.08,0.26,-0.54,-1.21,-2.14\}$

이들의 합은 0이며, 그 최댓값 2.54는 그래프의 최대 차수 3보다 작다.

무변 그래프

무변 그래프 ${\overline{𝖪}}_n$의 인접 행렬은 영행렬이다.

${𝖠}_{{\overline{𝖪}}_n}=0$

그 스펙트럼의 유일한 원소는 0이며, 그 중복수는 $n$이다.

완전 그래프

완전 그래프 ${𝖪}_n$의 인접 행렬은 다음과 같은 꼴이다.

${𝖠}_{{𝖪}_n}={\mu }_{n\times n}-1_{n\times n}$

여기서 $\mu$는 모든 성분이 1인 행렬이다.

그 스펙트럼은 다음과 같다.

$\mathrm{Spec}{𝖠}_{{𝖪}_n}=\{n-1,\underset{n-1}{\underbrace{-1,-1,\dots ,-1}}\}$

완전 이분 그래프

완전 이분 그래프 ${𝖪}_{m,n}$의 인접 행렬은 다음과 같은 꼴이다.

${𝖠}_{{𝖪}_{m,n}}=\left(\begin{array}{cc}{0}_{m\times m}& {\mu }_{m\times n}\\ {\mu }_{n\times m}& 0_{n\times n}\end{array}\right)$

여기서 $\mu$는 모든 성분이 1인 행렬이다.

완전 이분 그래프 ${𝖪}_{m,n}$의 스펙트럼은 다음과 같다.

$\mathrm{Spec}{𝖪}_{m,n}=\{+\sqrt{mn},-\sqrt{mn},\underset{m+n-2}{\underbrace{0,0,\dots ,0}}\}$

고윳값 $\pm \sqrt{mn}$의 고유 벡터는

$\sqrt{n}\sum _{i\in C_m}|i⟩\pm \sqrt{m}\sum _{j\in C_n}|j⟩$

이다. (여기서 $C_m,C_n\subseteq \mathrm{V}(\mathrm{\Gamma })$는 완전 이분 그래프의 꼭짓점 집합의 분할이다.)

순환 그래프

순환 그래프 ${𝖢}_n$의 인접 행렬은 다음과 같다.

${𝖢}_n=\sum _{i=0}^{n-1}(|i⟩⟨i+1|+|i+1⟩⟨i|)$

(여기서 $i\in \mathbb{Z}/(n)$으로 여긴다. 즉, $n\equiv 0$이다.)

그 스펙트럼은 다음과 같다.

$\mathrm{Spec}{𝖢}_n=\{2\cos \frac{2\pi i}{n}:i\in \{0,1,\dots ,n-1\}\}$

특히, $\pm 2$가 아닌 모든 고윳값들의 중복수는 2이다. ($\pm 2$의 중복수는 1이다.)

경로 그래프

$n$개의 꼭짓점을 갖는 경로 그래프 ${𝖯}_n$의 인접 행렬은 다음과 같다.

${𝖯}_n=\sum _{i=1}^{n-1}(|i⟩⟨i+1|+|i+1⟩⟨i|)$

그 스펙트럼은 다응과 같다.

$\mathrm{Spec}{𝖯}_n=\{2\cos \frac{\pi i}{n+1}:i\in \{1,\dots ,n\}\}$

특히, 만약 $\lambda$가 스펙트럼에 속한다면 $-\lambda$도 스펙트럼에 속한다. 모든 고윳값의 중복수는 1이다.

딘킨 도표

ADE형의 단순 리 대수 $𝔤$의 딘킨 도표는 그래프를 이룬다. 이 그래프의 스펙트럼은 다음과 같은 꼴이다.

$\{2\cos \frac{(d_i-1)\pi }{𝗁(𝔤)}:i\in \{1,\dots ,\mathrm{rank}𝔤\}\}$

여기서

• $\mathrm{rank}𝔤$는 $𝔤$의 계수($𝔤$의 최대 아벨 부분 리 대수의 차원 = 딘킨 도표의 꼭짓점의 수)이다.
• $𝗁(𝔤)$는 $𝔤$의 콕서터 수이다.
• $d_i$는 $𝔤$의 딘킨 도표의 각 꼭짓점에 대응되는 차수들이다. 예를 들어, 리 대수 ${𝔡}_n$의 경우 $d_i=2,4,6,\dots ,2n-2$이다.

같이 보기

• 그래프 라플라스 연산자

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:웹 인용