기본 이론 3

이번 글에서는 인접행렬의 거듭제곱에 대해 다루겠습니다.

 

인접행렬, adjacency matrix는 graph를 matrix로 나타낸 것입니다.

 

어떤 matrix $A$ 가 graph $G$ 의 adjacency matrix라는 것은 일반적으로 다음을 의미합니다.

 

$G$의 임의의 두 vertices $i$ 에서 $j$ 로의 edge가 존재하면 $A_{ij}$ 의 값이 1, 그렇지 않으면 0

---

Adjacency matrix로 edge가 directed인 경우, weighted인 경우도 표현할 수 있습니다.

 

directed가 아니면 $A_{ij}=A_{ji}=1$ 임이 자명합니다. 즉, $A_{ij} \ne A_{ji}$라면 directed graph일 것입니다.

 

weighted의 표현은 간단하게 그 edge의 weight을 $A_{ij}$ 의 값으로 하면 됩니다.

 

이런 adjacency matrix가 갖는 매우 아름다운 성질이 있습니다.

 

unweighted graph $G$ 의 adjacency matrix $A$ 에 대해 $A^{X}$ 의 각 entry $\left \{ a_{ij} \right \}$ 의 의미는

 

vertex $i$ 에서 출발해 $X$ 개의 edges를 거쳐 vertex $j$ 로 도달하는 방법의 수

---

증명은 수학적 귀납법을 통해 합니다.

 

$X=1$ 일 때, adjacency matrix 의 정의에 따라 자명합니다.

 

$X=K$ 일 때 위 성질이 성립한다고 가정하겠습니다.

 

이때 $A^{K+1}=A^{K}\times A$ 입니다.

 

$A^{K}$ 의 $i^{th}$ row는 가정에 의해 vertex $i$ 에서 출발하여 각 도착점까지 $K$ 개의 edges를 지나는 방법의 수를 알려줍니다.

 

$A$ 의 $j^{th}$ column은 정의에 의해 각 출발점에서 vertex $j$ 로 한 개의 edge를 지나 도착하는 방법의 수를 알려줍니다.

 

따라서 $A^{K+1}$ 의 한 entry $a_{ij}$ 는 vertex $i$ 에서 $j$ 로 $K+1$ 개의 edges를 지나는 방법의 수를 알려줍니다.

 

따라서 수학적 귀납법을 통해, 모든 $X$ 값에 대해 위 성질이 만족된다는 사실이 밝혀졌습니다.

 

이제 $A^{X}$ 를 분할정복으로 구해주면 위 성질을 활용하는 유형의 문제들이 다수 해결됩니다!

---