정의 n {\displaystyle n} 개의 꼭짓점이 있는 그래프 Γ {\displaystyle \Gamma } 가 주어졌다고 하자. 그렇다면, 실수 내적 공간
H = R V ( Γ ) {\displaystyle H=\mathbb {R} ^{\operatorname {V} (\Gamma )}} 을 정의할 수 있다. Γ {\displaystyle \Gamma } 의 인접 행렬 A Γ {\displaystyle {\mathsf {A}}_{\Gamma }} 은 H {\displaystyle H} 위의 선형 변환 H → H {\displaystyle H\to H} 이며, 그 성분은 다음과 같다.
⟨ j | A Γ | i ⟩ = { 1 i j ∈ E ( Γ ) 0 i j ∉ E ( Γ ) {\displaystyle \langle j|{\mathsf {A}}_{\Gamma }|i\rangle ={\begin{cases}1&ij\in \operatorname {E} (\Gamma )\\0&ij\not \in \operatorname {E} (\Gamma )\\\end{cases}}} (편의상 브라-켓 표기법 을 사용하였다.)이는 정의에 따라 대칭 연산자 이다.
보다 일반적으로, 이와 같은 정의를 다중 그래프 에 대하여 일반화할 수 있다. 이 경우, ( A Γ ) i j {\displaystyle ({\mathsf {A}}_{\Gamma })_{ij}} 는 i {\displaystyle i} 와 j {\displaystyle j} 사이의 변의 수가 된다. 다만, 이 경우 문헌에 따라 고리(시작과 끝이 같은 변)를 세는 법이 다를 수 있다.
화살집의 인접 행렬 국소 유한 화살집 (즉, 임의의 두 꼭짓점 사이의 변 집합이 유한한 화살집) Q {\displaystyle Q} 의 인접 행렬 은 실수 선형 변환
A Q : R V ( Q ) → R V ( Q ) {\displaystyle {\mathsf {A}}_{Q}\colon \mathbb {R} ^{\operatorname {V} (Q)}\to \mathbb {R} ^{\operatorname {V} (Q)}} 이며, 그 성분은 다음과 같다.
⟨ j | A Q | i ⟩ = | hom Q ( i , j ) | {\displaystyle \langle j|{\mathsf {A}}_{Q}|i\rangle =|\hom _{Q}(i,j)|} 즉, A i j {\displaystyle A_{ij}} 는 v i {\displaystyle v_{i}} 에서 시작하고 v j {\displaystyle v_{j}} 에서 끝나는 변의 수이다. 만약 이러한 변이 없다면 A i j = 0 {\displaystyle A_{ij}=0} 이다. 특히, A i i {\displaystyle A_{ii}} 는 꼭짓점 v i {\displaystyle v_{i}} 에서 스스로로 가는 변의 수이다.이는 물론 일반적으로 대칭 연산자 가 아니다.
이에 따라, 화살집 Q {\displaystyle Q} 에 대하여,
⟨ j | A Q n | i ⟩ ∈ N {\displaystyle \langle j|{\mathsf {A}}_{Q}^{n}|i\rangle \in \mathbb {N} } 은 꼭짓점 i ∈ V ( Γ ) {\displaystyle i\in \operatorname {V} (\Gamma )} 에서 꼭짓점 j ∈ V ( Γ ) {\displaystyle j\in \operatorname {V} (\Gamma )} 로 가는, 길이 n {\displaystyle n} 의 보행 의 수이다. (여기서 편의상 브라-켓 표기법 을 사용하였다.) 마찬가지로, 대각합
tr A Q n {\displaystyle \operatorname {tr} {\mathsf {A}}_{Q}^{n}} 은 길이 n {\displaystyle n} 의 순환의 수이다.
성질 유한 그래프 Γ {\displaystyle \Gamma } 의 인접 행렬의 고윳값 의 집합을 Γ {\displaystyle \Gamma } 의 스펙트럼 (영어 : spectrum )이라고 하고, Spec Γ {\displaystyle \operatorname {Spec} \Gamma } 로 표기하자.
그래프는 자기 고리를 가질 수 없으므로, 그래프의 인접 행렬의 대각 성분들은 모두 0이다. 이에 따라, 그 대각합 은 항상 0이다. 즉, 스펙트럼의 원소들의 (중복수를 고려한) 합은 0이다.
Γ {\displaystyle \Gamma } 의 스펙트럼의 최댓값 λ 1 ( Γ ) {\displaystyle \lambda _{1}(\Gamma )} 은 Γ {\displaystyle \Gamma } 의 최대 차수(한 꼭짓점에 연결된 변의 수의 최댓값 )보다 같거나 작다.
max Spec ( Γ ) ≤ max deg Γ = max i ∈ V ( Γ ) deg Γ i {\displaystyle \max \operatorname {Spec} (\Gamma )\leq \max \deg _{\Gamma }=\max _{i\in \operatorname {V} (\Gamma )}\deg _{\Gamma }i} 또한, 유한 정규 그래프 Γ {\displaystyle \Gamma } 에 대하여, 이 부등식이 포화된다.
max Spec ( Γ ) = max deg Γ = max i ∈ V ( Γ ) deg Γ i {\displaystyle \max \operatorname {Spec} (\Gamma )=\max \deg _{\Gamma }=\max _{i\in \operatorname {V} (\Gamma )}\deg _{\Gamma }i} 정규 그래프의 경우 이 고윳값 max deg Γ {\displaystyle \max \deg _{\Gamma }} 의 중복수는 Γ {\displaystyle \Gamma } 의 연결 성분 의 수와 같다. 각 연결 성분 C ⊆ Γ {\displaystyle C\subseteq \Gamma } 에 대응하는 고유 벡터 | ψ C ⟩ {\displaystyle |\psi _{C}\rangle } 는 각 연결 성분 C {\displaystyle C} 에 대하여
⟨ i | ψ C ⟩ = { 1 i ∈ C 0 i ∉ C {\displaystyle \langle i|\psi _{C}\rangle ={\begin{cases}1&i\in C\\0&i\not \in C\end{cases}}} 의 꼴이다. 특히,
( 1 , 1 , … , 1 ) {\displaystyle (1,1,\dotsc ,1)} 는 항상 고윳값 max deg Γ {\displaystyle \max \deg _{\Gamma }} 의 고유 벡터 를 이룬다.
연산에 대한 호환 임의의 두 그래프 Γ {\displaystyle \Gamma } , Γ ′ {\displaystyle \Gamma '} 에 대하여,
Spec ( Γ ⊔ Γ ′ ) = Spec Γ ⊔ Spec Γ ′ {\displaystyle \operatorname {Spec} (\Gamma \sqcup \Gamma ')=\operatorname {Spec} \Gamma \sqcup \operatorname {Spec} \Gamma '} 이다. 여기서 좌변은 그래프의 분리합집합 이며, 우변은 중복집합 의 분리합집합 이다.
임의의 두 그래프 Γ {\displaystyle \Gamma } , Γ ′ {\displaystyle \Gamma '} 에 대하여,
Spec ( Γ ◻ Γ ′ ) = { λ + λ ′ : λ ∈ Spec Γ , λ ′ ∈ Spec Γ ′ } {\displaystyle \operatorname {Spec} (\Gamma \square \Gamma ')=\{\lambda +\lambda '\colon \lambda \in \operatorname {Spec} \Gamma ,\;\lambda '\in \operatorname {Spec} \Gamma '\}} 이다. 여기서 ◻ {\displaystyle \square } 는 그래프의 그래프 데카르트 곱 을 뜻한다.
그래프 동형 같은 스펙트럼을 갖지만 서로 동형이 아닌 두 그래프 같은 수의 꼭짓점을 갖는 임의의 두 유한 그래프 Γ {\displaystyle \Gamma } , Γ ′ {\displaystyle \Gamma '} 에 대하여, 두 그래프가 동형일 필요 충분 조건 은
P A Γ = A Γ ′ P {\displaystyle P{\mathsf {A}}_{\Gamma }={\mathsf {A}}_{\Gamma '}P} 인 치환행렬
P : R V ( Γ ) → R V ( Γ ′ ) {\displaystyle P\colon \mathbb {R} ^{\operatorname {V} (\Gamma )}\to \mathbb {R} ^{\operatorname {V} (\Gamma ')}} 가 존재하는 것이다.
반면, 서로 동형이 아니지만, 스펙트럼이 같은 그래프들이 알려져 있다.
응용 인접 행렬의 특정 원소에 접근하는 데 걸리는 시간이 상수 시간이라면 꼭짓점 i에서 꼭짓점 j로 가는 변이 있는지를 상수 시간에 알 수 있다. 꼭짓점의 개수를 n이라고 할 때 인접행렬을 만드는 데 O ( n 2 ) {\displaystyle O(n^{2})} 시간을 쓰게 되므로, 인접행렬을 이용한 그래프 알고리즘의 시간 복잡도는 이보다 더 좋을 수 없다. 따라서 변이 희소한 경우에는 인접 리스트 표현 방식이 유리하다.
예 다음과 같은 유한 그래프 를 생각하자.
이 그래프의 인접 행렬은 다음과 같은 대칭 행렬 이다.
A = ( 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 ) {\displaystyle 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 } {\displaystyle \{2.54,1.08,0.26,-0.54,-1.21,-2.14\}} 이들의 합은 0이며, 그 최댓값 2.54는 그래프의 최대 차수 3보다 작다.
무변 그래프 무변 그래프 K ¯ n {\displaystyle {\bar {\mathsf {K}}}_{n}} 의 인접 행렬은 영행렬이다.
A K ¯ n = 0 {\displaystyle {\mathsf {A}}_{{\bar {\mathsf {K}}}_{n}}=0} 그 스펙트럼의 유일한 원소는 0이며, 그 중복수는 n {\displaystyle n} 이다.
완전 그래프 완전 그래프 K n {\displaystyle {\mathsf {K}}_{n}} 의 인접 행렬은 다음과 같은 꼴이다.
A K n = μ n × n − 1 n × n {\displaystyle {\mathsf {A}}_{{\mathsf {K}}_{n}}=\mu _{n\times n}-1_{n\times n}} 여기서 μ {\displaystyle \mu } 는 모든 성분이 1인 행렬 이다.
그 스펙트럼은 다음과 같다.
Spec A K n = { n − 1 , − 1 , − 1 , … , − 1 ⏟ n − 1 } {\displaystyle \operatorname {Spec} {\mathsf {A}}_{{\mathsf {K}}_{n}}=\{n-1,\underbrace {-1,-1,\dotsc ,-1} _{n-1}\}}
완전 이분 그래프 완전 이분 그래프 K m , n {\displaystyle {\mathsf {K}}_{m,n}} 의 인접 행렬은 다음과 같은 꼴이다.
A K m , n = ( 0 m × m μ m × n μ n × m 0 n × n ) {\displaystyle {\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}}} 여기서 μ {\displaystyle \mu } 는 모든 성분이 1인 행렬 이다.
완전 이분 그래프 K m , n {\displaystyle {\mathsf {K}}_{m,n}} 의 스펙트럼은 다음과 같다.
Spec K m , n = { + m n , − m n , 0 , 0 , … , 0 ⏟ m + n − 2 } {\displaystyle \operatorname {Spec} {\mathsf {K}}_{m,n}=\{+{\sqrt {mn}},-{\sqrt {mn}},\underbrace {0,0,\dotsc ,0} _{m+n-2}\}} 고윳값 ± m n {\displaystyle \pm {\sqrt {mn}}} 의 고유 벡터는
n ∑ i ∈ C m | i ⟩ ± m ∑ j ∈ C n | j ⟩ {\displaystyle {\sqrt {n}}\sum _{i\in C_{m}}|i\rangle \pm {\sqrt {m}}\sum _{j\in C_{n}}|j\rangle } 이다. (여기서 C m , C n ⊆ V ( Γ ) {\displaystyle C_{m},C_{n}\subseteq \operatorname {V} (\Gamma )} 는 완전 이분 그래프의 꼭짓점 집합의 분할 이다.)
순환 그래프 순환 그래프 C n {\displaystyle {\mathsf {C}}_{n}} 의 인접 행렬은 다음과 같다.
C n = ∑ i = 0 n − 1 ( | i ⟩ ⟨ i + 1 | + | i + 1 ⟩ ⟨ i | ) {\displaystyle {\mathsf {C}}_{n}=\sum _{i=0}^{n-1}(|i\rangle \langle i+1|+|i+1\rangle \langle i|)} (여기서 i ∈ Z / ( n ) {\displaystyle i\in \mathbb {Z} /(n)} 으로 여긴다. 즉, n ≡ 0 {\displaystyle n\equiv 0} 이다.)
그 스펙트럼은 다음과 같다.
Spec C n = { 2 cos 2 π i n : i ∈ { 0 , 1 , … , n − 1 } } {\displaystyle \operatorname {Spec} {\mathsf {C}}_{n}=\left\{2\cos {\frac {2\pi i}{n}}\colon i\in \{0,1,\dotsc ,n-1\}\right\}} 특히, ± 2 {\displaystyle \pm 2} 가 아닌 모든 고윳값들의 중복수는 2이다. ( ± 2 {\displaystyle \pm 2} 의 중복수는 1이다.)
경로 그래프 n {\displaystyle n} 개의 꼭짓점을 갖는 경로 그래프 P n {\displaystyle {\mathsf {P}}_{n}} 의 인접 행렬은 다음과 같다.
P n = ∑ i = 1 n − 1 ( | i ⟩ ⟨ i + 1 | + | i + 1 ⟩ ⟨ i | ) {\displaystyle {\mathsf {P}}_{n}=\sum _{i=1}^{n-1}(|i\rangle \langle i+1|+|i+1\rangle \langle i|)} 그 스펙트럼은 다응과 같다.
Spec P n = { 2 cos π i n + 1 : i ∈ { 1 , … , n } } {\displaystyle \operatorname {Spec} {\mathsf {P}}_{n}=\left\{2\cos {\frac {\pi i}{n+1}}\colon i\in \{1,\dotsc ,n\}\right\}} 특히, 만약 λ {\displaystyle \lambda } 가 스펙트럼에 속한다면 − λ {\displaystyle -\lambda } 도 스펙트럼에 속한다. 모든 고윳값의 중복수는 1이다.
딘킨 도표 ADE형의 단순 리 대수 g {\displaystyle {\mathfrak {g}}} 의 딘킨 도표 는 그래프 를 이룬다. 이 그래프의 스펙트럼은 다음과 같은 꼴이다.
{ 2 cos ( d i − 1 ) π h ( g ) : i ∈ { 1 , … , rank g } } {\displaystyle \left\{2\cos {\frac {(d_{i}-1)\pi }{{\mathsf {h}}({\mathfrak {g}})}}\colon i\in \{1,\dotsc ,\operatorname {rank} {\mathfrak {g}}\}\right\}} 여기서
rank g {\displaystyle \operatorname {rank} {\mathfrak {g}}} 는 g {\displaystyle {\mathfrak {g}}} 의 계수( g {\displaystyle {\mathfrak {g}}} 의 최대 아벨 부분 리 대수의 차원 = 딘킨 도표의 꼭짓점의 수)이다. h ( g ) {\displaystyle {\mathsf {h}}({\mathfrak {g}})} 는 g {\displaystyle {\mathfrak {g}}} 의 콕서터 수이다. d i {\displaystyle d_{i}} 는 g {\displaystyle {\mathfrak {g}}} 의 딘킨 도표의 각 꼭짓점에 대응되는 차수들이다. 예를 들어, 리 대수 d n {\displaystyle {\mathfrak {d}}_{n}} 의 경우 d i = 2 , 4 , 6 , … , 2 n − 2 {\displaystyle d_{i}=2,4,6,\dotsc ,2n-2} 이다.
같이 보기
외부 링크