Adjacency Matrix

그래프를 행렬로 바꾸는 것을 생각해보았는데 이미 있더라고요.

인접행렬 : 

점의 개수가 유한한 어떤 그래프에 대해 각 점에 넘버링을 했을 때 인접하게 연결된 점에다가 1, 아닌 점은 0을 대입시켜서 만드는 행렬. 즉, 인접행렬의 i행 j열은 점 i와 j가 연결되어 있으면 1, i와 j가 연결되어 있지 않으면 0이다.

예를 들어, 삼각형의 경우에는

\[ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \]

가 되는 거죠. 

재미있는 것은 인접행렬을 제곱하는 것인데, 그 결과가 Graph와 밀접한 관련이 있어요.

위에 예로 나온 행렬을 제곱하면

\[ \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1& 1 & 2 \end{pmatrix} \]

가 되는데, i행 j열의 값은 i에서 시작해서 j로 끝나는 길이가 2인 path의 수에요.