확률과 통계순열과 조합수능 기출심화 문제 (4점 중반 이후, 킬러 직전)
다리 추가 오일러 회로
문제
어느 도시에 다음 그림과 같은 모양으로 개의 다리가 놓여 있다. 모든 다리를 오직 한 번 지나서 출발점으로 다시 돌아오는 방법은 없다.
모든 다리를 오직 한 번 지나서 출발점으로 다시 돌아올 수 있도록 네 지역 중에서 필요한 두 지역을 잇는 다리를 추가로 몇 개 건설하려고 한다. 각 지역을 잇는 다리를 새로 건설하는 비용이 다음 표와 같을 때, 필요한 최소 비용은 (억원)이다. 의 값을 구하시오. [4점]
| (단위：억원) | ||||
| A | B | C | D | |
| A | 0 | 8 | 10 | 12 |
| B | 8 | 0 | 8 | 9 |
| C | 10 | 8 | 0 | 14 |
| D | 12 | 9 | 14 | 0 |
정답 보기
19
자료 내려받기
아직 올라온 파일이 없습니다.
해설
네 지역 A, B, C, D을 꼭지점으로 하고, 지역을 연결하는 각 다리를 변으로 생각하여 그래프를 그리면 다음과 같다.
모든 변(다리)를 한 번씩만 지나 출발점으로 돌아오는 오일러회로가 존재하기 위해서는 각 꼭지점의 차수가 짝수가 되어야 한다. 이 때, 각 꼭지점의 차수가 모두 홀수이므로 두 꼭지점씩 짝을 지어 연결하는 두 개의 변(다리)을 추가해야 한다. 따라서 두 개의 변을 추가하는 방법은 3가지이고, 그 때 소요되는 비용은 각각 다음과 같다. AB, CD → AC, BD → AD, BC → 따라서 필요한 최소비용은 (억원)이다.