쓰기로 했으니까 힘들어도 써야겠지... 일단 시작해봅시다.
나는 라플라시안, 사인리스 라플라시안 안 다루고 일단 인접행렬만 다뤄보도록 할게.
인접행렬은 그래프의 정보를 저장해놓은 행렬이라고 보면 된다. 아래 그림을 보자.
각각 위의 그래프에 아래의 인접행렬이 대응한다고 보면 되겠다.
첫 번째 녀석은 K_{1,3} (완전이분그래프), 두 번째 녀석은 4-cycle, 세 번째 녀석은 K_4라고 부른다 (완전그래프).
나중에 또 소개하겠지만 하여간 그렇다고.
이렇게 꼭지점에 라벨링을 매기고, 두 꼭지점 사이에 변이 있으면 1, 없으면 0을 매긴다고 보면 되겠다.
라벨링을 달라져도 그래프는 동형이고 인접행렬도 닮은 행렬이 나오기 때문에 라벨링 방법은 중요하지 않다.
본질적으로 그래프나 인접행렬이나 가지고 있는 정보의 양은 똑같다고 볼 수 있겠지?
근데 정사각행렬이 있으면 보통 고유값을 생각하는게 자연스럽지.
우리가 선형대수 때 배웠듯이, 인접행렬은 실수행렬이고, 대칭행렬이므로 대각화가 잘 되고 실수 고유값을 가지게 된다.
인접행렬이 그래프의 정보를 가지고 있는건 이해하겠는데, 이 고유값들도 그래프에 대한 정보를 가지고 있을까?
더 나아가서, 인접행렬의 고유값만 가지고 그래프를 만들어낼 수 있을까?
첫 번째 질문에 대한 대답은 당연히 Yes야. 고유값들도 그래프에 대한 정보를 "어느 정도는" 가지고 있어.
두 번째 질문에 대한 대답은 일반적으로는 No야. 이게 가능한 그래프들은 DS(Determined by Spectrum)라고 하는데, DS임을 보이기는 꽤 어려워.
일단 인접행렬의 고유값(앞으로는 그래프의 고유값, 혹은 고유값이라고만 해도 얘를 말하는지 눈치를 까자)을 공부하기 전에,
인접행렬의 성질을 조금 알아보도록 하자. 아니다, 그 이전에 고유값과 행렬의 성질부터 해야하나?
0. 어떤 행렬의 rank는 0이 아닌 고유값의 중복도의 합이고, nullity는 0인 고유값의 중복도이다.
위에 올렸던 그래프의 그림을 다시 보도록 하자.
두 번째 인접행렬을 보면 선형독립인 열이 둘 뿐이므로, nullity가 2고, 고유값 0을 두 개 가진다는 것을 알 수 있다.
여기서 (1, 1, 1, 1)이 고유값 2인 고유벡터가 되고, 행렬의 대각합이 0이므로 고유값들의 합이 0이 된다.
여기서 (1, 1, 1, 1)이 왜 나왔냐? 급발진하는거 아니냐? 라는 의문을 가질 수 있다. 이 의문은 곧 풀어주겠다.
따라서 나머지 하나의 고유값은 -2가 되고, 고유값은 2, 0, 0, -2가 됨을 알 수 있다.
첫 번째 인접행렬에 같은 논의를 적용하면 고유값 0을 두 개 가지고, x와 -x라는 0이 아닌 고유값을 가지겠지?
x를 구하는건 다음 항에서 하도록 하자.
세 번째 인접행렬은... 항등행렬을 더해주면 nullity가 3이고 고유값 0을 세 개 가진다는 것을 알 수 있다.
항등행렬을 더해줬을 때 대각합은 4이므로, 고유값은 4, 0, 0, 0이 된다.
여기서 다시 항등행렬을 빼주면 고유값이 3, -1, -1, -1이 된다는걸 확인 가능하다.
1. 인접행렬을 A라고 했을 때, A^n의 (i, j) 성분은 꼭지점 i에서 j로 가는 길이 n인 경로의 수를 나타낸다.
증명은 n에 대한 귀납법을 사용하고, 이산수학 대부분의 책에서 다루는 것으로 알고 있다.
그렇다면 A^2의 대각합은 뭘 나타낼까? 대각합은 A^2의 (i, i) 성분들의 합이다.
꼭지점 i에서 i로 가는 길이 2인 경로는 결국 i의 이웃의 갯수만큼 존재할 수밖에 없다.
즉, A^2의 대각합은 더블카운팅을 쓰면 (꼭지점 전체의 이웃의 갯수의 합) = (모든 변의 갯수의 2배) 가 된다.
그런데 A^2의 대각합은 고유값의 제곱의 합이기도 하니까 결국 고유값의 제곱의 합 = 변 갯수의 2배라는 말.
그럼 첫 번째 인접행렬의 고유값이 x, 0, 0, -x라고 했는데, 2x^2 = 6이 되어야하므로 x = 루트3이라는걸 알 수 있다.
비슷한 방법을 A^3에 사용하면 고유값의 세제곱의 합이 그래프의 삼각형 갯수의 6배가 된다는 것도 알 수 있다.
A^4이나 A^5에는 적용이 가능할까? 안된다면 왜 안 될까?
2. 모든 꼭지점이 k개의 이웃을 가지는 경우를 k-정칙(k-regular) 그래프라고 한다.
이런 경우 행들의 합이 k로 일정하므로, (1, 1, 1, ... , 1)을 살펴보면 고유값 k의 고유벡터가 되는걸 쉽게 확인 가능하다.
두 번째 그래프의 경우 고유값 2에 대응하고, 세 번째 그래프의 경우 고유값 3에 대응하겠지.
연결된 그래프의 경우, 이 고유값 k의 중복도가 1이라는 것도 나중에 배우게 된다.
좀 더 일반적으로 가면 가장 큰 고유값이 행의 합 중 최대 이하라는 것도 배우는데.. 나중에 다루도록 하자.
정말 선형대수만 잘 들었어도 아무 도움이 안 되는 내용을 너무 길게 쓴 거 같다. 연습문제를 내고 마치도록 하자.
(1) 완전그래프 K_n은 n개의 점이 있고, 임의의 두 점이 연결된 그래프다. K_n의 고유값을 모두 구해보자.
(2) 완전이분그래프 K_{n,m}은 X라는 n개의 점을 가지는 집합과, Y라는 m개의 점을 가지는 집합에 대해서,
두 꼭지점이 다른 집합에 속하면 연결되어있는 그래프다. K_{n,m}의 고유값을 모두 구해보자.
(3) (선택) n개의 꼭지점을 가지는 n각형(n-cycle)의 고유값도 한번 심심하면 구해보자.
힌트 : 내가 예전에 쓴 순환행렬 관련 글
(4) (선택, 약간 더 어려움) n개의 꼭지점을 가지는 n-1개의 변을 가지는 경로(path)의 고유값도 할 짓이 없으면 구해보자.
세 줄 요약
1. 그래프의 인접행렬은 실수 성분을 가지는 대칭행렬이므로, 대각화가 잘 되고 실수 고유값을 가진다.
2. 고유값의 합은 0이고 고유값의 제곱의 합은 변의 갯수의 두 배다. (세제곱의 합은 삼각형 갯수의 여섯 배긴 한데..)
3. 이 글 아무리 읽어봐야 직접 고유값 안 구해보면 와닿지 않을 것이다. 질문은 댓글로!
개추
rank는 고윳값의 대수적 중복도의 합이지. 트집잡기 같긴 하지만 기하적 중복도도 있으니 구별하는게 좋을듯.
밑줄 친 부분 때문에 두 중복도가 같아져서 굳이 구별하지 않았음
ds임을 보이기는 꽤 어렵다에서 가슴이 웅장해집니다. rAFLE형님
일단 추천 하나 박고 가겠습니다.
RAFLE형님 질문 있습니다. 글에서 첫번째 질문에 대한 답으로 그래프의 고유값은 그래프에 대한 정보를 "어느정도"는 갖고 있다는 부분에서 혹시 인접행렬의 고유값을 가지고 그 그래프가 평면 그래프인지 연구할 수 있나요??
planarity 관련 정리 중에
https://en.m.wikipedia.org/wiki/Colin_de_Verdière_graph_invariant
이런게 있긴 한데 일반적으로는 잘 안 쓸 거 같은데?
추가로 더 질문해도 될까요?? 그래프가 Determined by spectrum 인지 아닌지는 어떻게 보일 수 있나요??
그것은 매우 어렵습니다.. 새로운 경우 하나하나가 논문이 될 정도라.. 일단 관련 survey paper를 눈팅하는걸 추천.
https://reader.elsevier.com/reader/sd/pii/S002437950300483X?token=C92E4A09D62C7C116EC977ED79E40F3AF9065E24C7594D4081A09DCD9AACBF156B5C38C3CC2AB236967E037E27E08820
오 신기하당