그래프의 Adjacency matrix와 spectrum matrix와 complete graph의 adjacency matrix와 spectrum matrix

 



 

그래프이론에서 vertex 끼리 adjacet한지 아닌지 중요하다. adjacent 한지 아닌지를 기록하여 adjacency matrix에 나타낸다. 그리고 이 matrix의 eigen value와 eigen value multiplicity 도 구해서 그래프 구조를 구하는데 활용한다. 이번 글에서는 그래프의 adjacency matrix와 이것의 eigen value와 eigen value 의 multiplicity 기록한 spectrum matrix에 대해 알아보겠다.

 

Adjacency matrix

그래프 $G$가 있다고 하자. $G$의 vertex를 모아둔 집합을 $V(G) = \{v_1,v_2,…,v_n\}$ 이라고 하자. 총 $n$ 개의 vertex가 있다. 이제 이 vertex들끼리 adjacent 한지 아닌지를 생각할 수 있다. matrix $A$를 $n \times n $ matrix 라고 하자. $A$의 $i$번째 행 $j$번째 열의 원소 $a_{ij}$는 아래와 같이 정의된다.

$$ a_{ij} = \text{ 끝점이 $v_i$와 $v_j$로 구성된 edge의 갯수 } $$

만약에 $a_{12} = 2 $ 라는 것은 $v_1$과$v_2$ 가 adjacent 하다는 얘기이자 $v_1$에서 $v_2$로 그려지는 edge가 두개라는 얘기이다.

그래프 $G$의 adjacency matrix 는 $A(G)$라고 표기한다.$A(G)$는 symmetric 하므로 실수인 eigen value만 존재함을 주목하자. 

Spectrum matrix

그래프 $G$가 있고 $G$의 adjacency matrix $A(G)$가 있다고 하자. 이 adjacency matrix $A(G)$의 eigen value와 eigen value의 각각의 multiplicity를 모아둔 행렬을 spectrum matrix 라 한다. $G$의 spectrum matrix 는 $S(G)$라고 표시한다. 그래서 $S(G)$는 두개의 행으로 구성되어있고 열의 갯수는 $A(G)$가 가지는 eigen value에 의해 결정된다. $S(G)$의 첫행에는 $A(G)$의 eigen value가 나열되어있고 각각의 eigen value밑에는 eigen value의 multiplicity가 적혀져 있다. 

 

예시: complete graph의 adjacency matrix와 spectrum matrix

예시를 풀어보는 것이 문제를 이해하는데 도움이 된다. 모든 vertex가 adjacent 한 simple 그래프 $K_n$에 대해 생각해보자. $K_n$은 $n$개의 vertex로 구성되어있다. $K_n$의 각각의 vertex는 자기자신을 제외하고 모든 vertex와 adjacent 하다. $K_n$은 simple graph 이므로 각각의 vertex를 끝점으로 갖는 edge는 1개씩만 존재한다. 이점을 고려하면 adjacency matrix $A(K_n)$의 $i$번째 행 $j$번째 열의 원소 $a_{ij}$는 $i \neq j$ 일 때 $a_{ij} = 1$이고 $a_{ii} = 0$이다. 즉 $A(G)$의 원소는 대각선 원소를 제외하고 다른 원소는 다 1이다. 이제 $S(G)$를 구해보자. 그럴려면 아래의 식을 만족하는 $\lambda$를 찾아야 한다.

$$A(K_n) \mathbf{x} = \lambda \mathbf{x}, \mathbf{x} = (x_1,x_2,…,x_n)^T$$

그런데 $$ A(K_n) \mathbf{x} = \lambda \mathbf{x}$$의 행을 다 더하면 아래와 같은 식이 나온다.

$$(n-1) ( x_1+x_2+x_3+… + x_n) = \lambda ( x_1+x_2+x_3+… + x_n)$$

$\lambda=n-1$이고 $\mathbf{x} = (1,1,…1)$일 때 위의 식이 성립함을 알 수 있다. 따라서 eigen value $n-1$을 찾았다.

그다음에 $$A(K_n) \mathbf{x} $$의 $i$번째 행을 생각해보자. $i$번째 행은 아래와 같이 생겼다.

$$ \sum_{j\neq i} x_j = \lambda x_i$$

위의 식에다가 $x_i$를 더하면 아래와 같이 바뀐다.

$$\sum_{ 1 \leq j \leq n } x_j = (\lambda + 1) x_i$$

위의 식이 모든 $i$에 대해 성립한다. 이때 $\lambda = -1$이라면 $\sum_{1 \leq j \leq n} x_j=0$을 얻게된다. 따라서 $\lambda=-1$은 eigen value가 되고 eigen vector 는 $\sum_{1 \leq j \leq n} x_j=0$를 만족해야 한다. $\sum_{1 \leq j \leq n} x_j=0$의 dimension 은 $n-1$이므로 eigen value $-1$의 multiplicity는 $n-1$이다. 위에서 eigen value $n-1$을 구했는데 $n-1$의 multiplicity 는 자동적으로 $1$이 된다. 따라서 $S(G)$는 아래와 같다.

$$S(G) =  \begin{bmatrix} -1 & n-1 \\ n-1 & 1 \\ \end{bmatrix} $$

 

Leave a Comment