그래프 라플라스 연산자

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

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

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

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

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

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

이제, 다음과 같은 \mathbb K-선형 변환
:\Delta_\Gamma\colon V\to V
을 정의할 수 있다.
:\Delta_\Gamma f\colon v\mapsto \sum_{uv\in\operatorname E(\Gamma)}\left(f(v)-f(u)\right)
즉, 임의의 두 꼭짓점 u,v\in\operatorname V(\Gamma)에 대하여 다음과 같다.
:\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}

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

## 성질
그래프 라플라스 연산자는 유계 작용소이자 자기 수반 작용소이며, 그 성분들은 꼭짓점에 대한 표준 정규 직교 기저에서 모두 정수이다. 즉, 모든 꼭짓점의 차수가 유한한 임의의 그래프 \Gamma 및 u,v\in\operatorname V(\Gamma)에 대하여
:\langle u|\Delta_\Gamma|v\rangle = \langle v|\Delta_\Gamma|u\rangle \in\mathbb Z
이다. 또한, 그 고윳값들은 모두 음이 아닌 실수이다. 즉, 그래프 라플라스 연산자의 고윳값들을 (중복수를 고려하여)
:\lambda_0(\Delta_\Gamma)\le \lambda_1(\Delta_\Gamma) \le \lambda_2(\Delta_\Gamma)\le\dotsb
로 표기하면,
:0\le\lambda_0(\Delta_\Gamma)
이다.

그래프 라플라스 연산자의 작용소 노름은 다음과 같은 상계를 갖는다.
:\|\Delta_\Gamma\|\le2\max_{v\in\operatorname V(\Gamma)}\deg v

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

### 부분 그래프
다음이 주어졌다고 하자.
* 유한 그래프 \Gamma
* 꼭짓점 집합 S\subseteq\operatorname V(\Gamma)
그렇다면, 다음이 성립한다.
:\lambda_1(\Gamma)\le \lambda_1(\Gamma\setminus S)+|S|

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

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

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

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

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

## 각주

## 외부 링크
* 
* 

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