정답
\( \det(L)=0 \) 이며, 꼭짓점 \(x_1\)에서 \(x_4\)로 가는 길이가 4인 walk의 개수는 \(4\)개이다.
출제 의도
이 문제는 주어진 incidence matrix로부터 그래프의 구조를 파악하고, 차수 행렬과 인접행렬을 이용해 라플라시안 행렬을 구성할 수 있는지를 평가한다. 또한 라플라시안 행렬의 행렬식 성질과, 인접행렬의 거듭제곱을 통해 특정 길이의 walk의 개수를 계산하는 능력을 확인하는 것이 핵심이다.
풀이 과정
주어진 incidence matrix \(B\)에서 각 행의 합은 해당 꼭짓점의 차수이므로, 이를 통해 차수를 구한다. 또한 각 열은 하나의 edge가 연결하는 두 꼭짓점을 나타내므로, 인접행렬을 복원할 수 있다.
각 꼭짓점의 차수는
$$ d_1=1,\quad d_2=3,\quad d_3=2,\quad d_4=2 $$
따라서 차수 행렬 \(D\)와 인접행렬 \(A\)는 다음과 같다.
$$ D= \begin{pmatrix} 1&0&0&0\\ 0&3&0&0\\ 0&0&2&0\\ 0&0&0&2 \end{pmatrix}, \quad A= \begin{pmatrix} 0&1&0&0\\ 1&0&1&1\\ 0&1&0&1\\ 0&1&1&0 \end{pmatrix} $$
라플라시안 행렬 \(L=D-A\)는
$$ L= \begin{pmatrix} 1&-1&0&0\\ -1&3&-1&-1\\ 0&-1&2&-1\\ 0&-1&-1&2 \end{pmatrix} $$
그래프 \(G\)는 연결 그래프이므로, 라플라시안 행렬의 행렬식은 항상 0이다. 따라서
$$ \det(L)=0 $$
다음으로 길이가 4인 walk의 개수는 인접행렬의 4제곱을 이용하여 계산한다. 즉, \(x_1\)에서 \(x_4\)로 가는 길이가 4인 walk의 개수는 \((A^4)_{14}\)이다.
인접행렬을 거듭제곱하여 계산하면
$$ (A^4)_{14}=4 $$
따라서 꼭짓점 \(x_1\)에서 \(x_4\)로 가는 길이가 4인 walk의 개수는 4개이다.