확률과 통계순열과 조합수능 기출발전 문제 (3점 후반~4점 초반)
지도 색칠과 회로
문제
어떤 지도에서는 경계가 서로 닿아 있는 지역을 서로 다른 색으로 칠하여 경계를 구별하고 있다. 지도를 색칠하는 데 필요한 최소 색의 수를 구하기 위하여 그래프 색칠하기를 이용하려고 한다. 최소 색의 수와 그래프에 대한 <보기>의 설명에서 항상 옳은 것을 모두 고른 것은? [4점]
| <보 기> | ||
| ㄱ. 최소 색의 수가 이면 그래프는 수형도이다. ㄴ. 최소 색의 수가 이면 그래프는 한 개 이상의 회로를 갖는다. ㄷ. 최소 색의 수가 이면 그래프의 각 꼭지점은 어떤 회로가 지난다. | ||
①ㄱ②ㄴ③ㄱ, ㄷ④ㄴ, ㄷ⑤ㄱ, ㄴ, ㄷ
정답 보기
②
자료 내려받기
아직 올라온 파일이 없습니다.
해설
ㄱ. (반례) 아래 그래프는 최소 색의 수가 2이지만 수형도가 아니다. (거짓)
ㄴ. 회로를 하나도 갖지 않는 그래프는 최소 색의 수가 2인 경우가 있으므로 최소 색의 수가 3인 가정에 모순이다. 따라서 한 개 이상의 회로를 갖는다. (참) ㄷ. (반례) 아래 그래프는 최소 색의 수가 4 이지만 회로가 지나지 않는 점이 존재한다. (거짓)
이상에서 옳은 것은 ㄴ이다.