그래프 행렬 미지수

[출제의도] 그래프를 나타내는 행렬을 이해할 수 있는가를 묻는 문제이다. 그래프 $G$를 나타내는 행렬의 성질에서 $a = b$, $c = d$ …… ㉠ 행렬의 모든 성분의 합은 변의 개수의 $2$배와 같으므로 조건 (가)에서 $a + b + c + d + 12 = 14$ …… ㉡ ㉠, ㉡에서 $2 ( a + c ) = 2$이므로 $a + c = 1$ 그런데 $a , c$는 $0$ 또는 $1$의 값을 가지므로 $a = 1$, $c = 0$ 또는 $a = 0$, $c = 1$이다. (ⅰ) $a = 1$, $c = 0$일 때, 다음과 같이 꼭짓점과 변을 정하면 모든 변을 빠짐없이 지나는 경로 $\mathrm{BCABDCED}$가 존재한다.

(ⅱ) $a = 0$, $c = 1$일 때, 주어진 행렬이 나타내는 그래프는 조건 (나)를 만족하지 않는다.

따라서 $a = b = 1$, $c = d = 0$이므로 $8 a + 4 b + 2 c + d = 12$ [참고] 그래프에서 꼭짓점에 연결된 변의 개수가 홀수인 꼭짓점의 개수가 $0$ 또는 $2$이면 모든 변을 빠짐없이 지나는 경로가 존재한다. (ⅰ) $a = 1$, $c = 0$일 때, 각 꼭짓점에 연결된 변의 개수가 $2 , 3 , 4 , 3 , 2$이므로 (나)를 만족한다. (ⅱ) $a = 0$, $c = 1$일 때, 각 꼭짓점에 연결된 변의 개수가 $1 , 3 , 4 , 3 , 3$이므로 (나)를 만족하지 않는다.