다음이 주어졌다고 하자.
그래프
Γ
{\displaystyle \Gamma }
. 또한,
Γ
{\displaystyle \Gamma }
의 모든 꼭짓점의 차수가 유한한 상한을 갖는다고 하자 (
sup
v
∈
V
(
Γ
)
deg
v
<
ℵ
0
{\displaystyle \textstyle \sup _{v\in \operatorname {V} (\Gamma )}\deg v<\aleph _{0}}
).
체
K
∈
{
R
,
C
}
{\displaystyle \mathbb {K} \in \{\mathbb {R} ,\mathbb {C} \}}
그렇다면,
V
(
Γ
)
{\displaystyle \operatorname {V} (\Gamma )}
로 생성되는
K
{\displaystyle \mathbb {K} }
-힐베르트 공간
V
=
L
2
(
V
(
Γ
)
;
K
)
{\displaystyle V=\operatorname {L} ^{2}(\operatorname {V} (\Gamma );\mathbb {K} )}
를 생각하자.
그래프 라플라스 연산자
Δ
Γ
:
V
→
V
{\displaystyle \Delta _{\Gamma }\colon V\to V}
는 유계 작용소 이며, 다음과 같이 두 가지로 정의될 수 있으나, 이 두 정의는 서로 동치이다.
만약
Γ
{\displaystyle \Gamma }
가 유한 그래프라면,
V
(
Γ
)
{\displaystyle \operatorname {V} (\Gamma )}
위에 임의의 전순서 를 부여하면 그래프 라플라스 연산자는
|
V
(
Γ
)
|
×
|
V
(
Γ
)
|
{\displaystyle |\operatorname {V} (\Gamma )|\times |\operatorname {V} (\Gamma )|}
정수 성분 대칭 행렬 로 표현된다. 이를
Γ
{\displaystyle \Gamma }
의 라플라스 행렬 이라고 한다.[1]
편의상,
V
{\displaystyle V}
의 원소는 함수
f
:
V
(
Γ
)
→
K
{\displaystyle f\colon \operatorname {V} (\Gamma )\to \mathbb {K} }
∑
v
∈
V
(
Γ
)
|
f
(
v
)
|
2
<
∞
{\displaystyle \sum _{v\in \operatorname {V} (\Gamma )}|f(v)|^{2}<\infty }
로 여겨질 수 있다.
이제, 다음과 같은
K
{\displaystyle \mathbb {K} }
-선형 변환
Δ
Γ
:
V
→
V
{\displaystyle \Delta _{\Gamma }\colon V\to V}
을 정의할 수 있다.
Δ
Γ
f
:
v
↦
∑
u
v
∈
E
(
Γ
)
(
f
(
v
)
−
f
(
u
)
)
{\displaystyle \Delta _{\Gamma }f\colon v\mapsto \sum _{uv\in \operatorname {E} (\Gamma )}\left(f(v)-f(u)\right)}
즉, 임의의 두 꼭짓점
u
,
v
∈
V
(
Γ
)
{\displaystyle u,v\in \operatorname {V} (\Gamma )}
에 대하여 다음과 같다.
⟨
u
|
Δ
Γ
|
v
⟩
=
{
−
1
u
v
∈
E
(
Γ
)
deg
v
u
=
v
0
u
≠
v
,
u
v
∉
E
(
Γ
)
{\displaystyle \langle u|\Delta _{\Gamma }|v\rangle ={\begin{cases}-1&uv\in \operatorname {E} (\Gamma )\\\deg v&u=v\\0&u\neq v,\;uv\not \in \operatorname {E} (\Gamma )\end{cases}}}
그래프
Γ
{\displaystyle \Gamma }
의 (방향이 없는) 변들로 생성되는
K
{\displaystyle \mathbb {K} }
-힐베르트 공간 을 정의하자.
W
=
L
2
(
E
(
Γ
)
;
K
)
{\displaystyle W=\operatorname {L} ^{2}(\operatorname {E} (\Gamma );\mathbb {K} )}
또한,
Γ
{\displaystyle \Gamma }
위에 임의의 유향 그래프 구조를 주고, 그 유향 변들의 집합을
E
o
r
(
Γ
)
⊆
V
(
Γ
)
2
{\displaystyle \operatorname {E_{or}} (\Gamma )\subseteq \operatorname {V} (\Gamma )^{2}}
라고 하자. 그렇다면, 다음과 같은 연산자를 정의할 수 있다.
E
:
W
→
V
{\displaystyle E\colon W\to V}
E
|
u
,
v
⟩
=
|
u
⟩
−
|
v
⟩
(
(
u
,
v
)
∈
E
o
r
(
Γ
)
)
{\displaystyle E|u,v\rangle =|u\rangle -|v\rangle \qquad \left((u,v)\in \operatorname {E_{or}} (\Gamma )\right)}
이는 자명하게 유계 작용소 를 정의한다. 따라서, 그 에르미트 수반
E
†
:
V
→
W
{\displaystyle E^{\dagger }\colon V\to W}
를 정의할 수 있으며, 이들을 합성하여 유계 작용소
Δ
Γ
=
E
E
†
{\displaystyle \Delta _{\Gamma }=EE^{\dagger }}
Δ
Γ
:
V
→
V
{\displaystyle \Delta _{\Gamma }\colon V\to V}
를 정의할 수 있다. 또한, 이것이
Γ
{\displaystyle \Gamma }
의 유향 그래프 구조에 의존하지 않음을 보일 수 있다. (반면,
E
†
E
:
W
→
W
{\displaystyle E^{\dagger }E\colon W\to W}
는 일반적으로 유향 그래프 구조에 의존한다.)
그래프 라플라스 연산자는 유계 작용소 이자 자기 수반 작용소 이며, 그 성분들은 꼭짓점에 대한 표준 정규 직교 기저 에서 모두 정수이다. 즉, 모든 꼭짓점의 차수가 유한한 임의의 그래프
Γ
{\displaystyle \Gamma }
및
u
,
v
∈
V
(
Γ
)
{\displaystyle u,v\in \operatorname {V} (\Gamma )}
에 대하여
⟨
u
|
Δ
Γ
|
v
⟩
=
⟨
v
|
Δ
Γ
|
u
⟩
∈
Z
{\displaystyle \langle u|\Delta _{\Gamma }|v\rangle =\langle v|\Delta _{\Gamma }|u\rangle \in \mathbb {Z} }
이다. 또한, 그 고윳값들은 모두 음이 아닌 실수이다.[5] :142, §2, Lemma 1 즉, 그래프 라플라스 연산자의 고윳값 들을 (중복수를 고려하여)
λ
0
(
Δ
Γ
)
≤
λ
1
(
Δ
Γ
)
≤
λ
2
(
Δ
Γ
)
≤
⋯
{\displaystyle \lambda _{0}(\Delta _{\Gamma })\leq \lambda _{1}(\Delta _{\Gamma })\leq \lambda _{2}(\Delta _{\Gamma })\leq \dotsb }
로 표기하면,
0
≤
λ
0
(
Δ
Γ
)
{\displaystyle 0\leq \lambda _{0}(\Delta _{\Gamma })}
이다.
그래프 라플라스 연산자의 작용소 노름 은 다음과 같은 상계 를 갖는다.[5] :144, Corollary
‖
Δ
Γ
‖
≤
2
max
v
∈
V
(
Γ
)
deg
v
{\displaystyle \|\Delta _{\Gamma }\|\leq 2\max _{v\in \operatorname {V} (\Gamma )}\deg v}
다음이 주어졌다고 하자.
유한 그래프
Γ
{\displaystyle \Gamma }
임의의 꼭짓점
v
∈
V
(
Γ
)
{\displaystyle v\in \operatorname {V} (\Gamma )}
그렇다면,
Δ
Γ
{\displaystyle \Delta _{\Gamma }}
에서
v
{\displaystyle v}
에 대응하는 행과 열을 생략한
(
|
V
(
Γ
)
|
−
1
)
×
(
|
V
(
Γ
)
|
−
1
)
{\displaystyle (|\operatorname {V} (\Gamma )|-1)\times (|\operatorname {V} (\Gamma )|-1)}
행렬을
Δ
Γ
[
v
]
{\displaystyle \Delta _{\Gamma }[v]}
로 표기하자. 그렇다면, 다음이 성립한다.
정수
det
Δ
Γ
[
v
]
∈
Z
{\displaystyle \det \Delta _{\Gamma }[v]\in \mathbb {Z} }
는 항상 자연수 이다.
det
Δ
Γ
[
v
]
{\displaystyle \det \Delta _{\Gamma }[v]}
는
v
∈
V
(
Γ
)
{\displaystyle v\in \operatorname {V} (\Gamma )}
의 선택에 의존하지 않는다.
det
Δ
Γ
[
v
]
{\displaystyle \det \Delta _{\Gamma }[v]}
는
Γ
{\displaystyle \Gamma }
의 생성나무 의 수와 같다.[1] :282, Theorem 13.2.1
det
Δ
Γ
[
v
]
=
|
V
(
Γ
)
|
−
1
∑
i
=
1
|
V
(
Γ
)
|
λ
i
(
Δ
Γ
)
{\displaystyle \textstyle \det \Delta _{\Gamma }[v]=|\operatorname {V} (\Gamma )|^{-1}\sum _{i=1}^{|\operatorname {V} (\Gamma )|}\lambda _{i}(\Delta _{\Gamma })}
이다.[1] :284, Lemma 13.2.4
다음이 주어졌다고 하자.
유한 그래프
Γ
{\displaystyle \Gamma }
꼭짓점 집합
S
⊆
V
(
Γ
)
{\displaystyle S\subseteq \operatorname {V} (\Gamma )}
그렇다면, 다음이 성립한다.[1] :288, Theorem 13.5.1
λ
1
(
Γ
)
≤
λ
1
(
Γ
∖
S
)
+
|
S
|
{\displaystyle \lambda _{1}(\Gamma )\leq \lambda _{1}(\Gamma \setminus S)+|S|}
유클리드 공간
R
n
{\displaystyle \mathbb {R} ^{n}}
이 주어졌다고 하자. 유한 그래프
Γ
{\displaystyle \Gamma }
의 균형 직교 표현 (영어 : balanced orthogonal representation )은 다음 조건을 만족시키는 함수
ρ
:
V
(
Γ
)
→
R
n
{\displaystyle \rho \colon \operatorname {V} (\Gamma )\to \mathbb {R} ^{n}}
이다.
(균형성)
∑
v
∈
V
(
Γ
)
ρ
(
v
)
=
0
{\displaystyle \textstyle \sum _{v\in \operatorname {V} (\Gamma )}\rho (v)=0}
(직교성)
∑
v
∈
V
(
Γ
)
ρ
i
(
v
)
ρ
j
(
v
)
=
δ
i
j
∀
i
,
j
∈
{
1
,
…
,
n
}
{\displaystyle \textstyle \sum _{v\in \operatorname {V} (\Gamma )}\rho _{i}(v)\rho _{j}(v)=\delta _{ij}\qquad \forall i,j\in \{1,\dotsc ,n\}}
이 두 조건에 의하여, 균형 직교 표현이 존재하려면
n
≥
1
+
V
(
Γ
)
{\displaystyle n\geq 1+\operatorname {V} (\Gamma )}
이어야 한다.
유한 그래프
Γ
{\displaystyle \Gamma }
의
R
n
{\displaystyle \mathbb {R} ^{n}}
속의 균형 직교 표현
ρ
{\displaystyle \rho }
가 주어졌으며, 또한
λ
1
(
Δ
Γ
)
>
0
{\displaystyle \lambda _{1}(\Delta _{\Gamma })>0}
라고 하자. 그렇다면, 다음이 성립한다.[1] :287, Theorem 13.4.1
∑
u
v
∈
E
(
Γ
)
‖
ρ
(
u
)
−
ρ
(
v
)
‖
≥
λ
1
(
Δ
Γ
)
+
λ
2
(
Δ
Γ
)
+
⋯
+
λ
n
(
Δ
Γ
)
{\displaystyle \sum _{uv\in \operatorname {E} (\Gamma )}\|\rho (u)-\rho (v)\|\geq \lambda _{1}(\Delta _{\Gamma })+\lambda _{2}(\Delta _{\Gamma })+\dotsb +\lambda _{n}(\Delta _{\Gamma })}
유한 완전 그래프
K
n
{\displaystyle K_{n}}
의 라플라스 행렬은 다음과 같다.
⟨
u
|
Δ
K
n
|
v
⟩
=
n
⟨
u
|
v
⟩
−
1
=
{
n
−
1
u
=
v
−
1
u
≠
v
{\displaystyle \langle u|\Delta _{K_{n}}|v\rangle =n\langle u|v\rangle -1={\begin{cases}n-1&u=v\\-1&u\neq v\end{cases}}}
즉,
Δ
K
n
=
n
−
J
{\displaystyle \Delta _{K_{n}}=n-{\mathsf {J}}}
이며, 여기서
J
{\displaystyle {\mathsf {J}}}
는 모든 성분이 1인 행렬(아다마르 곱 의 항등원)이다. 이에 따라,
K
n
{\displaystyle K_{n}}
속의 생성 나무의 수는
det
Δ
K
n
[
u
]
=
det
(
n
−
J
(
n
−
1
)
×
(
n
−
1
)
)
=
n
n
−
2
{\displaystyle \det \Delta _{K_{n}}[u]=\det(n-{\mathsf {J}}_{(n-1)\times (n-1)})=n^{n-2}}
이다.
특히,
K
2
{\displaystyle K_{2}}
의 라플라스 행렬은 다음과 같다.
Δ
K
2
=
(
1
−
1
−
1
1
)
{\displaystyle \Delta _{K_{2}}={\begin{pmatrix}1&-1\\-1&1\end{pmatrix}}}
즉, 그 고윳값 은
λ
0
(
Δ
K
2
)
=
0
{\displaystyle \lambda _{0}(\Delta _{K_{2}})=0}
λ
1
(
Δ
K
2
)
=
2
{\displaystyle \lambda _{1}(\Delta _{K_{2}})=2}
이다.
꼭짓점 차수가 상한 을 갖는 (유한 또는 무한) 그래프에 대하여, 다음 두 조건이 서로 동치 이다.