Spectral Graph Theory | Adjacency Matrix의 거듭제곱의 의미
Question어떤 그래프 $G(V, E)$의 adjacency matrix는 $n×n$ matrix $A = [a_{i,j}]$이다.$$a_{i, j} = \begin{cases} 1, & \text{if } v_i, v_j \in E(G) \\ 0, & \text{otherwise} \end{cases}$$ 이러한 행렬이 있을 때 이 행렬의 거듭제곱의 의미는 무엇인지 설명해 보시오. 즉 $A_k$ 에서 $a^{(k)}_{i, j}= p$는 무슨 의미인지 설명하시오. Answer$a^{(k)}_{i, j}= p$ 는 정점 $v_i$에서 정점 $v_j$까지 정확히 k 길이의 경로(path)가 p개 존재한다는 의미입니다.그래프 G의 인접행렬 A를 거듭제곱했을 때, $A^k$의 $(i, j)$ 원소(즉 $..
