그래프 라플라스 연산자

그래프 이론에서 그래프 라플라스 연산자(graph Laplace演算子, 영어: graph Laplacian operator)는 그래프의 꼭짓점들로 생성되는 힐베르트 공간 위에 정의되는 유계 작용소이다.^{[1]:279–306, Chapter 13[2][3][4]}

다음이 주어졌다고 하자.

• 그래프 ${\displaystyle \Gamma }$. 또한, ${\displaystyle \Gamma }$의 모든 꼭짓점의 차수가 유한한 상한을 갖는다고 하자 (${\displaystyle \textstyle \sup _{v\in \operatorname {V} (\Gamma )}\deg v<\aleph _{0}}$).
• 체 ${\displaystyle \mathbb {K} \in \{\mathbb {R} ,\mathbb {C} \}}$

그렇다면, ${\displaystyle \operatorname {V} (\Gamma )}$로 생성되는 ${\displaystyle \mathbb {K} }$-힐베르트 공간

${\displaystyle V=\operatorname {L} ^{2}(\operatorname {V} (\Gamma );\mathbb {K} )}$

를 생각하자.

그래프 라플라스 연산자

${\displaystyle \Delta _{\Gamma }\colon V\to V}$

는 유계 작용소이며, 다음과 같이 두 가지로 정의될 수 있으나, 이 두 정의는 서로 동치이다.

만약 ${\displaystyle \Gamma }$가 유한 그래프라면, ${\displaystyle \operatorname {V} (\Gamma )}$ 위에 임의의 전순서를 부여하면 그래프 라플라스 연산자는 ${\displaystyle |\operatorname {V} (\Gamma )|\times |\operatorname {V} (\Gamma )|}$ 정수 성분 대칭 행렬로 표현된다. 이를 ${\displaystyle \Gamma }$의 라플라스 행렬이라고 한다.^[1]

편의상, ${\displaystyle V}$의 원소는 함수

${\displaystyle f\colon \operatorname {V} (\Gamma )\to \mathbb {K} }$

${\displaystyle \sum _{v\in \operatorname {V} (\Gamma )}|f(v)|^{2}<\infty }$

로 여겨질 수 있다.

이제, 다음과 같은 ${\displaystyle \mathbb {K} }$-선형 변환

${\displaystyle \Delta _{\Gamma }\colon V\to V}$

을 정의할 수 있다.

${\displaystyle \Delta _{\Gamma }f\colon v\mapsto \sum _{uv\in \operatorname {E} (\Gamma )}\left(f(v)-f(u)\right)}$

즉, 임의의 두 꼭짓점 ${\displaystyle u,v\in \operatorname {V} (\Gamma )}$에 대하여 다음과 같다.

${\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 }$의 (방향이 없는) 변들로 생성되는 ${\displaystyle \mathbb {K} }$-힐베르트 공간을 정의하자.

${\displaystyle W=\operatorname {L} ^{2}(\operatorname {E} (\Gamma );\mathbb {K} )}$

또한, ${\displaystyle \Gamma }$ 위에 임의의 유향 그래프 구조를 주고, 그 유향 변들의 집합을

${\displaystyle \operatorname {E_{or}} (\Gamma )\subseteq \operatorname {V} (\Gamma )^{2}}$

라고 하자. 그렇다면, 다음과 같은 연산자를 정의할 수 있다.

${\displaystyle E\colon W\to V}$

${\displaystyle E|u,v\rangle =|u\rangle -|v\rangle \qquad \left((u,v)\in \operatorname {E_{or}} (\Gamma )\right)}$

이는 자명하게 유계 작용소를 정의한다. 따라서, 그 에르미트 수반

${\displaystyle E^{\dagger }\colon V\to W}$

를 정의할 수 있으며, 이들을 합성하여 유계 작용소

${\displaystyle \Delta _{\Gamma }=EE^{\dagger }}$

${\displaystyle \Delta _{\Gamma }\colon V\to V}$

를 정의할 수 있다. 또한, 이것이 ${\displaystyle \Gamma }$의 유향 그래프 구조에 의존하지 않음을 보일 수 있다. (반면, ${\displaystyle E^{\dagger }E\colon W\to W}$는 일반적으로 유향 그래프 구조에 의존한다.)

그래프 라플라스 연산자는 유계 작용소이자 자기 수반 작용소이며, 그 성분들은 꼭짓점에 대한 표준 정규 직교 기저에서 모두 정수이다. 즉, 모든 꼭짓점의 차수가 유한한 임의의 그래프 ${\displaystyle \Gamma }$ 및 ${\displaystyle u,v\in \operatorname {V} (\Gamma )}$에 대하여

${\displaystyle \langle u|\Delta _{\Gamma }|v\rangle =\langle v|\Delta _{\Gamma }|u\rangle \in \mathbb {Z} }$

이다. 또한, 그 고윳값들은 모두 음이 아닌 실수이다.^{[5]:142, §2, Lemma 1} 즉, 그래프 라플라스 연산자의 고윳값들을 (중복수를 고려하여)

${\displaystyle \lambda _{0}(\Delta _{\Gamma })\leq \lambda _{1}(\Delta _{\Gamma })\leq \lambda _{2}(\Delta _{\Gamma })\leq \dotsb }$

로 표기하면,

${\displaystyle 0\leq \lambda _{0}(\Delta _{\Gamma })}$

이다.

그래프 라플라스 연산자의 작용소 노름은 다음과 같은 상계를 갖는다.^{[5]:144, Corollary}

${\displaystyle \|\Delta _{\Gamma }\|\leq 2\max _{v\in \operatorname {V} (\Gamma )}\deg v}$

다음이 주어졌다고 하자.

• 유한 그래프 ${\displaystyle \Gamma }$
• 임의의 꼭짓점 ${\displaystyle v\in \operatorname {V} (\Gamma )}$

그렇다면, ${\displaystyle \Delta _{\Gamma }}$에서 ${\displaystyle v}$에 대응하는 행과 열을 생략한 ${\displaystyle (|\operatorname {V} (\Gamma )|-1)\times (|\operatorname {V} (\Gamma )|-1)}$ 행렬을 ${\displaystyle \Delta _{\Gamma }[v]}$로 표기하자. 그렇다면, 다음이 성립한다.

• 정수 ${\displaystyle \det \Delta _{\Gamma }[v]\in \mathbb {Z} }$는 항상 자연수이다.
• ${\displaystyle \det \Delta _{\Gamma }[v]}$는 ${\displaystyle v\in \operatorname {V} (\Gamma )}$의 선택에 의존하지 않는다.
• ${\displaystyle \det \Delta _{\Gamma }[v]}$는 ${\displaystyle \Gamma }$의 생성나무의 수와 같다.^{[1]:282, Theorem 13.2.1}
• ${\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 }$
• 꼭짓점 집합 ${\displaystyle S\subseteq \operatorname {V} (\Gamma )}$

그렇다면, 다음이 성립한다.^{[1]:288, Theorem 13.5.1}

${\displaystyle \lambda _{1}(\Gamma )\leq \lambda _{1}(\Gamma \setminus S)+|S|}$

유클리드 공간 ${\displaystyle \mathbb {R} ^{n}}$이 주어졌다고 하자. 유한 그래프 ${\displaystyle \Gamma }$의 균형 직교 표현(영어: balanced orthogonal representation)은 다음 조건을 만족시키는 함수

${\displaystyle \rho \colon \operatorname {V} (\Gamma )\to \mathbb {R} ^{n}}$

이다.

• (균형성) ${\displaystyle \textstyle \sum _{v\in \operatorname {V} (\Gamma )}\rho (v)=0}$
• (직교성) ${\displaystyle \textstyle \sum _{v\in \operatorname {V} (\Gamma )}\rho _{i}(v)\rho _{j}(v)=\delta _{ij}\qquad \forall i,j\in \{1,\dotsc ,n\}}$

이 두 조건에 의하여, 균형 직교 표현이 존재하려면 ${\displaystyle n\geq 1+\operatorname {V} (\Gamma )}$이어야 한다.

유한 그래프 ${\displaystyle \Gamma }$의 ${\displaystyle \mathbb {R} ^{n}}$ 속의 균형 직교 표현 ${\displaystyle \rho }$가 주어졌으며, 또한

${\displaystyle \lambda _{1}(\Delta _{\Gamma })>0}$

라고 하자. 그렇다면, 다음이 성립한다.^{[1]:287, Theorem 13.4.1}

${\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 })}$

유한 완전 그래프 ${\displaystyle K_{n}}$의 라플라스 행렬은 다음과 같다.

${\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}}}$

즉,

${\displaystyle \Delta _{K_{n}}=n-{\mathsf {J}}}$

이며, 여기서 ${\displaystyle {\mathsf {J}}}$는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. 이에 따라, ${\displaystyle K_{n}}$ 속의 생성 나무의 수는

${\displaystyle \det \Delta _{K_{n}}[u]=\det(n-{\mathsf {J}}_{(n-1)\times (n-1)})=n^{n-2}}$

이다.

특히, ${\displaystyle K_{2}}$의 라플라스 행렬은 다음과 같다.

${\displaystyle \Delta _{K_{2}}={\begin{pmatrix}1&-1\\-1&1\end{pmatrix}}}$

즉, 그 고윳값은

${\displaystyle \lambda _{0}(\Delta _{K_{2}})=0}$

${\displaystyle \lambda _{1}(\Delta _{K_{2}})=2}$

이다.

꼭짓점 차수가 상한을 갖는 (유한 또는 무한) 그래프에 대하여, 다음 두 조건이 서로 동치이다.

• 무변 그래프이다.
• 그래프 라플라스 연산자가 0이다.

• “Incidence matrix”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Laplacian matrix”. 《Wolfram MathWorld》 (영어). Wolfram Research.