확률과 통계순열과 조합수능 기출기본 문제 (3점 중반)

그래프 색칠과 강의 배정

문제

다섯 명의 강사 $\mathrm{A} , B , C , D , E$ 가 각각 $1$ 시간 분량의 강의를 할 예정이다. 아래 표처럼 강사들도 다른 강사의 강의를 듣고 싶어 한다.

강사	듣고 싶은 강의
$\mathrm{A}$	$\mathrm{B}$ 의 강의, $\mathrm{C}$ 의 강의
$\mathrm{B}$	$\mathrm{C}$ 의 강의, $\mathrm{D}$ 의 강의
$\mathrm{C}$	$\mathrm{A}$ 의 강의
$\mathrm{D}$	$\mathrm{C}$ 의 강의
$\mathrm{E}$	$\mathrm{C}$ 의 강의, $\mathrm{D}$ 의 강의

강사들이 듣고 싶어 하는 강의를 모두 들을 수 있도록 오후 $2$ 시부터 강의 시간을 배정할 때, 모든 강의가 끝나게 되는 가장 빠른 시각은? (단, 강의는 휴식 없이 계속된다.) [3점] ①오후 $4$ 시②오후 $5$ 시③오후 $6$ 시④오후 $7$ 시⑤오후 $8$ 시

정답 보기

②

자료 내려받기

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

해설

[출제의도] 최소색칠문제를 이해하고 있는가를 묻는 문제이다. 강사 $\mathrm{A} , B , C , D , E$ 를 꼭짓점으로 하고 한 강사가 다른 강사의 강의를 듣고 싶은 경우, 두 강사 사이를 변으로 연결한 그래프는 아래와 같다.

이때, 이 그래프의 색채수가 강의를 위해 필요한 최소한의 시간수이다. 이 그래프를 적절하게 색칠하는데 필요한 최소의 색의 개수는 $3$ 이므로 $3$ 시간만 있으면 강사들이 듣고 싶은 강의를 모두 들을 수 있도록 시간배정이 가능하다. 따라서 오후 $2$ 시부터 강의가 시작되므로 오후 $5$ 시면 모든 강의를 끝마칠 수 있다.

← 전체 문제 목록으로

그래프 색칠과 강의 배정

문제

자료 내려받기

해설

태그

비슷한 문제 더 보기