그래프 행렬 경로 수

[출제의도] 행렬과 그래프의 관계 이해하기 그래프의 연결 상태를 나타낸 행렬을 $P$라 하자. $\displaystyle P = {\begin{pmatrix} 0 & \square {} & \square {} & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & \square {} \\ 0 & \square {} & 0 & 0 \end{pmatrix}}$ 에 대하여 $a _{ij} = a _{ji}$$\left( i , j = 1 , 2 , 3 , 4 \right)$이므로 $\displaystyle P = {\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}}$ 이다. $\displaystyle P ^{2} = {\begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 3 & 1 & 0 \\ 1 & 1 & 2 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}}$ 이므로 꼭짓점 $B$에서 변을 두 번 거쳐 꼭짓점 $B$로 되돌아오는 방법의 수는 $P ^{2}$의 $\left( 2 , 2 \right)$성분과 같으므로 $3$이다.