그래프 라플라스 연산자

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

다음이 주어졌다고 하자.

  • 그래프 . 또한, 의 모든 꼭짓점의 차수가 유한한 상한을 갖는다고 하자 ().

그렇다면, 로 생성되는 -힐베르트 공간

를 생각하자.

그래프 라플라스 연산자

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

만약 가 유한 그래프라면, 위에 임의의 전순서를 부여하면 그래프 라플라스 연산자는 정수 성분 대칭 행렬로 표현된다. 이를 라플라스 행렬이라고 한다.[1]

직접적 정의[편집]

편의상, 의 원소는 함수

로 여겨질 수 있다.

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

을 정의할 수 있다.

즉, 임의의 두 꼭짓점 에 대하여 다음과 같다.

인접 연산자를 통한 정의[편집]

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

또한, 위에 임의의 유향 그래프 구조를 주고, 그 유향 변들의 집합을

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

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

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

를 정의할 수 있다. 또한, 이것이 유향 그래프 구조에 의존하지 않음을 보일 수 있다. (반면, 는 일반적으로 유향 그래프 구조에 의존한다.)

성질[편집]

그래프 라플라스 연산자는 유계 작용소이자 자기 수반 작용소이며, 그 성분들은 꼭짓점에 대한 표준 정규 직교 기저에서 모두 정수이다. 즉, 모든 꼭짓점의 차수가 유한한 임의의 그래프 에 대하여

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

로 표기하면,

이다.

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

생성나무[편집]

다음이 주어졌다고 하자.

  • 유한 그래프
  • 임의의 꼭짓점

그렇다면, 에서 에 대응하는 행과 열을 생략한 행렬을 로 표기하자. 그렇다면, 다음이 성립한다.

  • 정수 는 항상 자연수이다.
  • 의 선택에 의존하지 않는다.
  • 생성나무의 수와 같다.[1]:282, Theorem 13.2.1
  • 이다.[1]:284, Lemma 13.2.4

부분 그래프[편집]

다음이 주어졌다고 하자.

  • 유한 그래프
  • 꼭짓점 집합

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

표현[편집]

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

이다.

  • (균형성)
  • (직교성)

이 두 조건에 의하여, 균형 직교 표현이 존재하려면 이어야 한다.

유한 그래프 속의 균형 직교 표현 가 주어졌으며, 또한

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

[편집]

완전 그래프[편집]

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

즉,

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

이다.

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

즉, 그 고윳값

이다.

무변 그래프[편집]

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

참고 문헌[편집]

  1. Godsil, Christopher David; Royle, Gordon. 《Algebraic graph theory》. Graduate Texts in Mathematics (영어) 207. Springer Verlag. ISBN 978-0-387-95220-8. ISSN 0072-5285. doi:10.1007/978-1-4613-0163-9. 
  2. Merris, Russell (1995). “A survey of graph Laplacians”. 《Linear and Multilinear Algebra》 (영어) 39 (1–2): 19–31. doi:10.1080/03081089508818377. 
  3. Merris, Russell (1994년 1월). “Laplacian matrices of graphs: a survey”. 《Linear Algebra and its Applications》 (영어). 197–198: 143–176. doi:10.1016/0024-3795(94)90486-3. 
  4. Newman, Michael Willian (2000년 7월 1일). 《The Laplacian spectrum of graphs》 (PDF) (영어). 석사 학위 논문. 매니토바 대학교. ISBN 0-612-57564-0. 
  5. Anderson, William N. Jr.; Morley, Thomas D. (1985). “Eigenvalues of the Laplacian of a graph”. 《Linear and Multilinear Algebra》 (영어) 18 (2): 141–145. Zbl 0594.05046. doi:10.1080/03081088508817681. 

외부 링크[편집]