그래프 라플라스 연산자 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''그래프 라플라스 연산자'''(graph Laplace演算子, {{llang|en|graph Laplacian operator}})는 그래프의 꼭짓점들로 생성되는 [[힐베르트 공간]] 위에 정의되는 [[유계 작용소]]이다.<ref name="GR"/>{{rp|279–306, Chapter 13}}<ref>{{저널 인용|제목=A survey of graph Laplacians|이름=Russell|성=Merris|doi=10.1080/03081089508818377|저널=Linear and Multilinear Algebra|권=39|날짜=1995|호=1–2|쪽=19–31|언어=en}}</ref><ref>{{저널 인용|제목=Laplacian matrices of graphs: a survey|이름=Russell|성=Merris|doi=10.1016/0024-3795(94)90486-3|저널=Linear Algebra and its Applications|권=197–198|날짜=1994-01|쪽=143–176|언어=en}}</ref><ref>{{서적 인용|url=https://www.seas.upenn.edu/~jadbabai/ESE680/Laplacian_Thesis.pdf|제목=The Laplacian spectrum of graphs|이름=Michael Willian|성=Newman|기타=석사 학위 논문|출판사=[[매니토바 대학교]]|날짜=2000-07-01|isbn=0-612-57564-0|언어=en|access-date=2017-06-26|archive-date=2017-08-29|archive-url=https://web.archive.org/web/20170829122531/http://www.seas.upenn.edu/~jadbabai/ESE680/Laplacian_Thesis.pdf|url-status=dead}}</ref>

== 정의 ==
다음이 주어졌다고 하자.
* [[그래프]] <math>\Gamma</math>. 또한, <math>\Gamma</math>의 모든 꼭짓점의 차수가 유한한 상한을 갖는다고 하자 (<math>\textstyle\sup_{v\in\operatorname V(\Gamma)}\deg v<\aleph_0</math>).
* [[체 (수학)|체]] <math>\mathbb K\in\{\mathbb R,\mathbb C\}</math>

그렇다면, <math>\operatorname V(\Gamma)</math>로 생성되는 <math>\mathbb K</math>-[[힐베르트 공간]]
:<math>V=\operatorname L^2(\operatorname V(\Gamma);\mathbb K)</math>
를 생각하자.

'''그래프 라플라스 연산자'''
:<math>\Delta_\Gamma\colon V\to V</math>
는 [[유계 작용소]]이며, 다음과 같이 두 가지로 정의될 수 있으나, 이 두 정의는 서로 동치이다.

만약 <math>\Gamma</math>가 유한 그래프라면, <math>\operatorname V(\Gamma)</math> 위에 임의의 [[전순서]]를 부여하면 그래프 라플라스 연산자는 <math>|\operatorname V(\Gamma)|\times|\operatorname V(\Gamma)|</math> 정수 성분 [[대칭 행렬]]로 표현된다. 이를 <math>\Gamma</math>의 '''라플라스 행렬'''이라고 한다.<ref name="GR">{{서적 인용|제목=Algebraic graph theory|성=Godsil|이름=Christopher David|이름2=Gordon|성2=Royle|출판사=Springer Verlag|isbn= 978-0-387-95220-8|url=https://www.math.uwaterloo.ca/~cgodsil/agt2/|총서=Graduate Texts in Mathematics|권=207|issn=0072-5285|doi=10.1007/978-1-4613-0163-9|언어=en}}</ref>

=== 직접적 정의 ===
편의상, <math>V</math>의 원소는 함수
:<math>f\colon\operatorname V(\Gamma)\to\mathbb K</math>
:<math>\sum_{v\in\operatorname V(\Gamma)}|f(v)|^2<\infty</math>
로 여겨질 수 있다.

이제, 다음과 같은 <math>\mathbb K</math>-[[선형 변환]]
:<math>\Delta_\Gamma\colon V\to V</math>
을 정의할 수 있다.
:<math>\Delta_\Gamma f\colon v\mapsto \sum_{uv\in\operatorname E(\Gamma)}\left(f(v)-f(u)\right)</math>
즉, 임의의 두 꼭짓점 <Math>u,v\in\operatorname V(\Gamma)</math>에 대하여 다음과 같다.
:<math>\langle u|\Delta_\Gamma|v\rangle = \begin{cases}
-1&uv\in\operatorname E(\Gamma)\\
\deg v&u=v\\
0&u\ne v,\;uv\not\in\operatorname E(\Gamma)
\end{cases}</math>

=== 인접 연산자를 통한 정의 ===
그래프 <math>\Gamma</math>의 (방향이 없는) 변들로 생성되는 <math>\mathbb K</math>-[[힐베르트 공간]]을 정의하자.
:<math>W=\operatorname L^2(\operatorname E(\Gamma);\mathbb K)</math>
또한, <math>\Gamma</math> 위에 임의의 [[유향 그래프]] 구조를 주고, 그 유향 변들의 집합을
:<math>\operatorname{E_{or}}(\Gamma)\subseteq\operatorname V(\Gamma)^2</math>
라고 하자. 그렇다면, 다음과 같은 연산자를 정의할 수 있다.
:<math>E\colon W\to V</math>
:<math>E|u,v\rangle = |u\rangle - |v\rangle \qquad\left((u,v)\in\operatorname{E_{or}}(\Gamma)\right)</math>
이는 자명하게 [[유계 작용소]]를 정의한다. 따라서, 그 [[에르미트 수반]]
:<math>E^\dagger\colon V\to W</math>
를 정의할 수 있으며, 이들을 합성하여 [[유계 작용소]]
:<math>\Delta_\Gamma=EE^\dagger</math>
:<math>\Delta_\Gamma\colon V\to V</math>
를 정의할 수 있다. 또한, 이것이 <math>\Gamma</math>의 [[유향 그래프]] 구조에 의존하지 않음을 보일 수 있다. (반면, <math>E^\dagger E\colon W\to W</math>는 일반적으로 [[유향 그래프]] 구조에 의존한다.)

== 성질 ==
그래프 라플라스 연산자는 [[유계 작용소]]이자 [[자기 수반 작용소]]이며, 그 성분들은 꼭짓점에 대한 표준 [[정규 직교 기저]]에서 모두 정수이다. 즉, 모든 꼭짓점의 차수가 유한한 임의의 그래프 <math>\Gamma</math> 및 <math>u,v\in\operatorname V(\Gamma)</math>에 대하여
:<math>\langle u|\Delta_\Gamma|v\rangle = \langle v|\Delta_\Gamma|u\rangle \in\mathbb Z</math>
이다. 또한, 그 고윳값들은 모두 음이 아닌 실수이다.<ref name="AM">{{저널 인용|제목=Eigenvalues of the Laplacian of a graph|doi=10.1080/03081088508817681|이름=William N. Jr.|성=Anderson|이름2=Thomas D.|성2=Morley|저널=Linear and Multilinear Algebra|날짜=1985|권=18|호=2|쪽=141–145|zbl=0594.05046|언어=en}}</ref>{{rp|142, §2, Lemma 1}} 즉, 그래프 라플라스 연산자의 [[고윳값]]들을 (중복수를 고려하여)
:<math>\lambda_0(\Delta_\Gamma)\le \lambda_1(\Delta_\Gamma) \le \lambda_2(\Delta_\Gamma)\le\dotsb</math>
로 표기하면,
:<math>0\le\lambda_0(\Delta_\Gamma)</math>
이다.

그래프 라플라스 연산자의 [[작용소 노름]]은 다음과 같은 [[상계 (수학)|상계]]를 갖는다.<ref name="AM"/>{{rp|144, Corollary}}
:<math>\|\Delta_\Gamma\|\le2\max_{v\in\operatorname V(\Gamma)}\deg v</math>

=== 생성나무 ===
다음이 주어졌다고 하자.
* 유한 그래프 <math>\Gamma</math>
* 임의의 꼭짓점 <math>v\in\operatorname V(\Gamma)</math>
그렇다면, <math>\Delta_\Gamma</math>에서 <math>v</math>에 대응하는 행과 열을 생략한 <math>(|\operatorname V(\Gamma)|-1)\times(|\operatorname V(\Gamma)|-1)</math> 행렬을 <math>\Delta_\Gamma[v]</math>로 표기하자. 그렇다면, 다음이 성립한다.
* 정수 <math>\det\Delta_\Gamma[v]\in\mathbb Z</math>는 항상 [[자연수]]이다.
* <math>\det\Delta_\Gamma[v]</math>는 <math>v\in\operatorname V(\Gamma)</math>의 선택에 의존하지 않는다.
* <math>\det\Delta_\Gamma[v]</math>는 <math>\Gamma</math>의 [[생성나무]]의 수와 같다.<ref name="GR"/>{{rp|282, Theorem 13.2.1}}
* <math>\textstyle\det\Delta_\Gamma[v] = |\operatorname V(\Gamma)|^{-1}\sum_{i=1}^{|\operatorname V(\Gamma)|}\lambda_i(\Delta_\Gamma)</math>이다.<ref name="GR"/>{{rp|284, Lemma 13.2.4}}

=== 부분 그래프 ===
다음이 주어졌다고 하자.
* 유한 그래프 <math>\Gamma</math>
* 꼭짓점 집합 <math>S\subseteq\operatorname V(\Gamma)</math>
그렇다면, 다음이 성립한다.<ref name="GR"/>{{rp|288, Theorem 13.5.1}}
:<math>\lambda_1(\Gamma)\le \lambda_1(\Gamma\setminus S)+|S|</math>

=== 표현 ===
[[유클리드 공간]] <math>\mathbb R^n</math>이 주어졌다고 하자. 유한 그래프 <math>\Gamma</math>의 '''균형 직교 표현'''({{llang|en|balanced orthogonal representation}})은 다음 조건을 만족시키는 함수
:<math>\rho\colon\operatorname V(\Gamma)\to\mathbb R^n</math>
이다.
* (균형성) <math>\textstyle\sum_{v\in\operatorname V(\Gamma)}\rho(v)=0</math>
* (직교성) <math>\textstyle \sum_{v\in\operatorname V(\Gamma)}\rho_i(v)\rho_j(v) = \delta_{ij}\qquad\forall i,j\in\{1,\dotsc,n\}</math>
이 두 조건에 의하여, 균형 직교 표현이 존재하려면 <math>n\ge 1+\operatorname V(\Gamma)</math>이어야 한다.

유한 그래프 <math>\Gamma</math>의 <math>\mathbb R^n</math> 속의 균형 직교 표현 <math>\rho</math>가 주어졌으며, 또한
:<math>\lambda_1(\Delta_\Gamma)>0</math>
라고 하자. 그렇다면, 다음이 성립한다.<ref name="GR"/>{{rp|287, Theorem 13.4.1}}
:<math>\sum_{uv\in\operatorname E(\Gamma)}\|\rho(u)-\rho(v)\|
\ge \lambda_1(\Delta_\Gamma)+\lambda_2(\Delta_\Gamma)+\dotsb+\lambda_n(\Delta_\Gamma)</math>

== 예 ==
=== 완전 그래프 ===
유한 [[완전 그래프]] <math>K_n</math>의 라플라스 행렬은 다음과 같다.
:<math>\langle u|\Delta_{K_n}|v\rangle=n\langle u|v\rangle-1=
\begin{cases}
n-1 & u=v\\
-1 & u\ne v
\end{cases}</math>
즉,
:<math>\Delta_{K_n}=n - \mathsf J</math>
이며, 여기서 <math>\mathsf J</math>는 모든 성분이 1인 행렬([[아다마르 곱]]의 항등원)이다. 이에 따라, <math>K_n</math> 속의 생성 나무의 수는
:<math>\det \Delta_{K_n}[u] = \det(n - \mathsf J_{(n-1)\times(n-1)}) = n^{n-2}</math>
이다.

특히, <math>K_2</math>의 라플라스 행렬은 다음과 같다.
:<math>\Delta_{K_2} = \begin{pmatrix}
1&-1\\
-1&1
\end{pmatrix}</math>
즉, 그 [[고윳값]]은
:<math>\lambda_0(\Delta_{K_2})=0</math>
:<math>\lambda_1(\Delta_{K_2})=2</math>
이다.

=== 무변 그래프 ===
꼭짓점 차수가 [[상한]]을 갖는 (유한 또는 무한) 그래프에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* [[무변 그래프]]이다.
* 그래프 라플라스 연산자가 0이다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Incidence matrix}}
* {{매스월드|id=LaplacianMatrix|title=Laplacian matrix}}

[[분류:그래프 이론]]
[[분류:대수적 그래프 이론]]