[그래프 이론] 인접행렬과 거듭제곱의 성질

아래 글을 먼저 보시고 오시기를 추천드립니다.
https://scian.tistory.com/174

[그래프 이론] 용어 및 기본 개념 정리

인접행렬
어떤 그래프의 두 꼭짓점이 한 변으로 연결되어 있으면 1, 변으로 연결되어 있지 않으면 0으로 하여 그래프의 두 꼭짓점 사이의 관계를 나타낸 행렬

$v_{1}, …, v_{n}$을 꼭짓점으로 갖는 그래프 $G$의 인접행렬을 $A$라 할 때,

G의 각 꼭짓점의 차수
$A^{2}$의 대각성분 ($v_{i}$의 차수: $A^{2}$의 i,i 성분)

• G의 변의 수: $\frac{tr(A^{2})}{2}$ (모든 꼭짓점 차수 합/2)

$v_{i}$에서 $v_{j}$로 가는 길이가 k인 길의 개수
$A^{k}$의 $(i,j)$ 성분

G안에 있는 삼각형의 개수
$\frac{tr(A^{3})}{6}$ ($A^3$ 대각성분 합/3!)