확률과 통계순열과 조합수능 기출발전 문제 (3점 후반~4점 초반)

그래프 색칠 수

문제

꼭짓점 A\mathrm{A}, B\mathrm{B}, C\mathrm{C}, D\mathrm{D}, X\mathrm{X}, Y\mathrm{Y}, Z\mathrm{Z}로 이루어진 다음 그래프에 최소 개수의 변을 추가하여 꼭짓점을 적절하게 색칠하는 데 필요한 최소 색의 수가 44인 그래프 HH를 만들 때, 가능한 그래프 HH의 개수는? [3점]

①1212②1414③1616④1818⑤2020

정답 보기
④

자료 내려받기

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

해설

최소 색의 수가 44개가 되려면 완전그래프가 되면 된다. 따라서 X,Y,ZX , Y , Z가 두 개 연결되고, A,B,C,DA , B , C , D에서 두 개가 연결되어야 한다. 3C2×4C2=3×6=18{} _{3} C _{2} \times _{4} C _{2} = 3 \times 6 = 18

태그

#그래프 색칠#완전그래프

비슷한 문제 더 보기

확률과 통계 문제 모음확률과 통계 순열과 조합 문제 모음수능 문제 모음발전 문제 모음
← 전체 문제 목록으로