그래프 라플라스 연산자

틀:위키데이터 속성 추적 그래프 이론에서 그래프 라플라스 연산자(graph Laplace演算子, 틀:Llang)는 그래프의 꼭짓점들로 생성되는 힐베르트 공간 위에 정의되는 유계 작용소이다.틀:Rp

정의

다음이 주어졌다고 하자.

• 그래프 $\mathrm{\Gamma }$. 또한, $\mathrm{\Gamma }$의 모든 꼭짓점의 차수가 유한한 상한을 갖는다고 하자 ($\underset{v\in \mathrm{V}(\mathrm{\Gamma })}{\sup }\mathrm{deg}v<{\mathrm{\aleph }}_0$).
• 체 $𝕂\in \{ℝ,ℂ\}$

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

$V={\mathrm{L}}^2(\mathrm{V}(\mathrm{\Gamma });𝕂)$

를 생각하자.

그래프 라플라스 연산자

${\mathrm{\Delta }}_{\mathrm{\Gamma }}:V\to V$

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

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

직접적 정의

편의상, $V$의 원소는 함수

$f:\mathrm{V}(\mathrm{\Gamma })\to 𝕂$

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

로 여겨질 수 있다.

이제, 다음과 같은 $𝕂$-선형 변환

${\mathrm{\Delta }}_{\mathrm{\Gamma }}:V\to V$

을 정의할 수 있다.

${\mathrm{\Delta }}_{\mathrm{\Gamma }}f:v\mapsto \sum _{uv\in \mathrm{E}(\mathrm{\Gamma })}(f(v)-f(u))$

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

$⟨u|{\mathrm{\Delta }}_{\mathrm{\Gamma }}|v⟩=\{\begin{array}{cc}-1& uv\in \mathrm{E}(\mathrm{\Gamma })\\ \mathrm{deg}v& u=v\\ 0& u\ne v,uv\in ̸\mathrm{E}(\mathrm{\Gamma })\end{array}$

인접 연산자를 통한 정의

그래프 $\mathrm{\Gamma }$의 (방향이 없는) 변들로 생성되는 $𝕂$-힐베르트 공간을 정의하자.

$W={\mathrm{L}}^2(\mathrm{E}(\mathrm{\Gamma });𝕂)$

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

${\mathrm{E}}_{\mathrm{or}}(\mathrm{\Gamma })\subseteq \mathrm{V}(\mathrm{\Gamma }{)}^2$

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

$E:W\to V$

$E|u,v⟩=|u⟩-|v⟩((u,v)\in {\mathrm{E}}_{\mathrm{or}}(\mathrm{\Gamma }))$

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

$E^{†}:V\to W$

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

${\mathrm{\Delta }}_{\mathrm{\Gamma }}=E{E}^{†}$

${\mathrm{\Delta }}_{\mathrm{\Gamma }}:V\to V$

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

성질

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

$⟨u|{\mathrm{\Delta }}_{\mathrm{\Gamma }}|v⟩=⟨v|{\mathrm{\Delta }}_{\mathrm{\Gamma }}|u⟩\in \mathbb{Z}$

이다. 또한, 그 고윳값들은 모두 음이 아닌 실수이다.틀:Rp 즉, 그래프 라플라스 연산자의 고윳값들을 (중복수를 고려하여)

${\lambda }_0({\mathrm{\Delta }}_{\mathrm{\Gamma }})\le {\lambda }_1({\mathrm{\Delta }}_{\mathrm{\Gamma }})\le {\lambda }_2({\mathrm{\Delta }}_{\mathrm{\Gamma }})\le \cdots$

로 표기하면,

$0\le {\lambda }_0({\mathrm{\Delta }}_{\mathrm{\Gamma }})$

이다.

그래프 라플라스 연산자의 작용소 노름은 다음과 같은 상계를 갖는다.틀:Rp

$\Vert {\mathrm{\Delta }}_{\mathrm{\Gamma }}\Vert \le 2\underset{v\in \mathrm{V}(\mathrm{\Gamma })}{\max }\mathrm{deg}v$

생성나무

다음이 주어졌다고 하자.

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

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

• 정수 $\det {\mathrm{\Delta }}_{\mathrm{\Gamma }}[v]\in \mathbb{Z}$는 항상 자연수이다.
• $\det {\mathrm{\Delta }}_{\mathrm{\Gamma }}[v]$는 $v\in \mathrm{V}(\mathrm{\Gamma })$의 선택에 의존하지 않는다.
• $\det {\mathrm{\Delta }}_{\mathrm{\Gamma }}[v]$는 $\mathrm{\Gamma }$의 생성나무의 수와 같다.틀:Rp
• $\det {\mathrm{\Delta }}_{\mathrm{\Gamma }}[v]=|\mathrm{V}(\mathrm{\Gamma }){|}^{-1}{\sum }_{i=1}^{|\mathrm{V}(\mathrm{\Gamma })|}{\lambda }_i({\mathrm{\Delta }}_{\mathrm{\Gamma }})$이다.틀:Rp

부분 그래프

다음이 주어졌다고 하자.

• 유한 그래프 $\mathrm{\Gamma }$
• 꼭짓점 집합 $S\subseteq \mathrm{V}(\mathrm{\Gamma })$

그렇다면, 다음이 성립한다.틀:Rp

${\lambda }_1(\mathrm{\Gamma })\le {\lambda }_1(\mathrm{\Gamma }\setminus S)+|S|$

표현

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

$\rho :\mathrm{V}(\mathrm{\Gamma })\to {ℝ}^n$

이다.

• (균형성) $\sum _{v\in \mathrm{V}(\mathrm{\Gamma })}\rho (v)=0$
• (직교성) $\sum _{v\in \mathrm{V}(\mathrm{\Gamma })}{\rho }_i(v){\rho }_j(v)={\delta }_{ij}\mathrm{\forall }i,j\in \{1,\dots ,n\}$

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

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

${\lambda }_1({\mathrm{\Delta }}_{\mathrm{\Gamma }})>0$

라고 하자. 그렇다면, 다음이 성립한다.틀:Rp

$\sum _{uv\in \mathrm{E}(\mathrm{\Gamma })}\Vert \rho (u)-\rho (v)\Vert \ge {\lambda }_1({\mathrm{\Delta }}_{\mathrm{\Gamma }})+{\lambda }_2({\mathrm{\Delta }}_{\mathrm{\Gamma }})+\cdots +{\lambda }_n({\mathrm{\Delta }}_{\mathrm{\Gamma }})$

예

완전 그래프

유한 완전 그래프 $K_n$의 라플라스 행렬은 다음과 같다.

$⟨u|{\mathrm{\Delta }}_{K_n}|v⟩=n⟨u|v⟩-1=\{\begin{array}{cc}n-1& u=v\\ -1& u\ne v\end{array}$

즉,

${\mathrm{\Delta }}_{K_n}=n-𝖩$

이며, 여기서 $𝖩$는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. 이에 따라, $K_n$ 속의 생성 나무의 수는

$\det {\mathrm{\Delta }}_{K_n}[u]=\det (n-{𝖩}_{(n-1)\times (n-1)})=n^{n-2}$

이다.

특히, $K_2$의 라플라스 행렬은 다음과 같다.

${\mathrm{\Delta }}_{K_2}=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$

즉, 그 고윳값은

${\lambda }_0({\mathrm{\Delta }}_{K_2})=0$

${\lambda }_1({\mathrm{\Delta }}_{K_2})=2$

이다.

무변 그래프

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

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

외부 링크

• 틀:Eom
• 틀:매스월드