확률과 통계순열과 조합수능 기출기본 문제 (3점 중반)
해밀턴 회로 반례
문제
다음 명제의 반례가 되는 그래프는? [3점]
| 꼭짓점을 적절하게 색칠하는 데 필요한 최소색의 수가 이면 그 그래프는 해밀턴 회로를 갖는다. | ||
| ① | ② | ||
| ③ | ④ | ||
| ⑤ | |||
정답 보기
③
자료 내려받기
아직 올라온 파일이 없습니다.
해설
꼭짓점을 적절하게 색칠하는 데 필요한 최소 색의 수가 인 그래프는②, ③, ④번이다. 그런데 ③번의 그래프는 해밀턴 회로가 존재하지 않는다.
다음 명제의 반례가 되는 그래프는? [3점]
| 꼭짓점을 적절하게 색칠하는 데 필요한 최소색의 수가 이면 그 그래프는 해밀턴 회로를 갖는다. | ||
| ① | ② | ||
| ③ | ④ | ||
| ⑤ | |||
아직 올라온 파일이 없습니다.
꼭짓점을 적절하게 색칠하는 데 필요한 최소 색의 수가 인 그래프는②, ③, ④번이다. 그런데 ③번의 그래프는 해밀턴 회로가 존재하지 않는다.