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

인접행렬 제곱과 그래프

문제

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

<보 기>
ㄱ. 이 그래프의 변의 개수는 88개이다. ㄴ. 생성수형도를 만들기 위해서는 44개의 변을 제거해야 한다. ㄷ. 오일러 회로를 만들기 위해서는 적어도 22개의 변을 추가해야 한다.

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

정답 보기
③

자료 내려받기

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

해설

[출제의도] 인접행렬을 그래프로 나타낼 수 있는가를 묻는 문제이다. ㄱ. 행렬 A2\mathrm{A} ^{2}의 (i,i)( i , i )성분은 한 꼭짓점에 연결된 변의 개수를 나타내므로 55의 꼭짓점을 차래대로 A,B,\mathrm{A} , B , C,D,E\mathrm{C} , D , E라고 할 때, 각 꼭짓점에 연결된 변의 개수는 4,2,4,3,34 , 2 , 4 , 3 , 3이므로 이것을 그래프로 나타내면 아래 그림과 같다.

그러므로 변의 개수는 88이다. (참) ㄴ. 아래 그림은 주어진 그래프의 생성수형도 중 하나이다. 따라서 생성수형도를 만들기 위해서는 44개의 변을 제거해야 한다. (참)

ㄷ. 오일러 회로는 모든 꼭짓점의 차수가 짝수가 되어야 하므로, 꼭짓점 D\mathrm{D}와 E\mathrm{E}를 연결하는 하나의 변을 추가하면 오일러 회로를 만들 수 있다. (거짓)

태그

#인접행렬#생성수형도#오일러 회로#보기

비슷한 문제 더 보기

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