공통수학1행렬과 그 연산수능 기출발전 문제 (3점 후반~4점 초반)

인접행렬 제곱 해석

문제

꼭짓점이 55개인 그래프 G\mathrm{G}의 인접행렬을 AA라 할 때, 다음은 A2A ^{2}을 나타낸 것이다. (4332234322334222223322233)\displaystyle {\begin{pmatrix} 4 & & 3 & & 3 & & 2 & & 2 \\ 3 & & 4 & & 3 & & 2 & & 2 \\ 3 & & 3 & & 4 & & 2 & & 2 \\ 2 & & 2 & & 2 & & 3 & & 3 \\ 2 & & 2 & & 2 & & 3 & & 3 \end{pmatrix}} 그래프 G\mathrm{G}에 대한 <보기>의 설명에서 옳은 것을 모두 고른 것은? [4점]

[ 보 기 ]
ㄱ. 차수가 33인 꼭짓점은 22개이다. ㄴ. 해밀턴회로를 갖는다. ㄷ. 서로 다른 두 꼭짓점을 잇는 22개의 변으로 이루어진 경로는 22개 이상이다.

①ㄱ②ㄷ③ㄱ, ㄴ④ㄴ, ㄷ⑤ㄱ, ㄴ, ㄷ

정답 보기
⑤

자료 내려받기

아직 올라온 파일이 없습니다.

해설

A2\mathrm{A} ^{2}의 대각선에 있는 수는 그래프 각 꼭짓점에 있는 차수와 같다. 꼭짓점을 순서대로 a,b,c,d,ea , b , c , d , e라 하면 각 꼭짓점의 차수는 4,4,4,3,34 , 4 , 4 , 3 , 3이므로 그래프를 그리면 다음과 같다.

ㄱ. 차수가 33인 꼭짓점은 d,ed , e로 22개 있다. ∴ 참 ㄴ. a−c−e−b−d−aa - c - e - b - d - a 등의 해밀턴 회로를 갖는다. ∴ 참 ㄷ. A2\mathrm{A} ^{2}의 모든 성분이 22 이상이므로 경로도 22개 이상이다. ∴ 참

태그

#인접행렬#해밀턴회로

비슷한 문제 더 보기

공통수학1 문제 모음공통수학1 행렬과 그 연산 문제 모음수능 문제 모음발전 문제 모음
← 전체 문제 목록으로