확률과 통계순열과 조합수능 기출킬러 문제 (22·30번 수준)

격자 그래프 회로 분할

문제

그림과 같이 aa부터 pp까지 1616개의 꼭짓점을 가지고 있는 평면그래프가 있다. 이 그래프의 꼭짓점 전체의 집합 {a,b,c,d,⋯ ,p}\left\{ a , b , c , d , \cdots , p \right\}를 분할할 때, 분할에 있는 모든 부분집합의 각 꼭짓점들이 그래프에서 회로를 이루도록 분할하는 방법의 수는? (단, 전체집합은 분할의 방법에서 제외한다.) [4점]

①1616②1414③1212④1010⑤88

정답 보기
③

자료 내려받기

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

해설

주어진 조건을 만족하도록 각 경우의 회로를 연결된 꼭짓점의 순서대로 나열하면 다음과 같다. ① a−b−f−e,c−d−h−g,a - b - f - e , c - d - h - g , i−j−n−m,k−l−p−oi - j - n - m , k - l - p - o 와 같이 꼭짓점의 개수가 44개인 회로 44개로 분할하는 방법의 수는 11개이다. ② a−b−f−e,c−d−h−g,a - b - f - e , c - d - h - g , i−j−k−l−p−o−n−mi - j - k - l - p - o - n - m 와 같이 꼭짓점의 개수가 44개인 회로 22개와 꼭짓점의 개수가 88개인 11개의 회로로 분할하는 방법의 수는 44가지이다. ③ a−b−f−ea - b - f - e, c−d−h−l−p−o−n−m−i−j−k−gc - d - h - l - p - o - n - m - i - j - k - g 와 같이 꼭짓점의 개수는 44개인 회로 11개와 꼭짓점의 개수가 1212개인 11개의 회로로 분할하는 방법의 수는 44가지이다. ④ a−b−f−j−n−m−i−ea - b - f - j - n - m - i - e, c−d−h−l−p−o−k−gc - d - h - l - p - o - k - g 와 같이 꼭짓점의 개수가 각각 88개인 22개의 회로로 분할하는 방법의 수는 22가지이다. ⑤ a−b−c−d−h−l−p−o−n−m−i−ea - b - c - d - h - l - p - o - n - m - i - e, f−g−k−jf - g - k - j 와 같이 분할하는 경우의 수는 11가지이다. 이상에서 구하는 방법의 수는 1+4+4+2+1=121 + 4 + 4 + 2 + 1 = 12

태그

#회로#분할

비슷한 문제 더 보기

확률과 통계 문제 모음확률과 통계 순열과 조합 문제 모음수능 문제 모음고난도 킬러 문제 모음
← 전체 문제 목록으로