중등영재교육원 대비 수학 특강] 도로 보수공사

어떤 지역에 20개의 도시가 있고 각 도시는 다른 모든 도시와 각각 한 개씩의 도로로 연결되어 있습니다. 그런데 이 도로들은 모두 개통된 지 오래되어 패이거나 손상된 부분이 더러 있어서 보수를 할 필요가 있었고, 경쟁 입찰을 통하여 A 건설회사가 보수 공사의 시공 회사로 선정되었습니다. 한편 치열한 경쟁을 뚫고 A 건설회사에 갓 입사한 신입사원 나토목 씨는 넘치는 의욕과 자신감에 이번 보수 공사에 자신도 참여할 수 있게 해 달라고 건의하였습니다. 하지만 평소 나토목 씨의 실력을 의심하던 상사가 그에게 다음과 같은 조건을 제시하였습니다.

“이번 공사는 공사 구간이 많은 만큼 한 군데씩 공사를 진행하다보면 기간이 너무 길어져 해당 도시의 주민들이 불편할 뿐만 아니라 비용도 높아질 수 있네. 마침 곧 휴가 기간이어서 도시 간 통행량이 줄어들게 된다네. 이때를 이용하여 되도록 동시에 여러 구간의 공사를 진행하려고 하는데, 아무리 그래도 다른 도시로 우회하여 모든 도시가 연결될 수는 있어야 하네. 최대 몇 개의 도로를 폐쇄할 수 있겠나? 자네가 이 문제를 해결해낸다면 공사 현장의 관리자로 참여시켜 주겠네.”

나토목 씨에게는 자신의 능력을 발휘할 수 있는 절호의 기회가 주어진 셈입니다. 과연 그는 뭐라고 대답해야 할까요?

실생활에서 복잡해 보이는 문제를 설계할 때 그래프가 자주 활용됩니다. 여기서의 그래프란 여러 개의 정점의 집합과 정점을 잇는 선으로 나타낸 그림을 의미하며, 그래프에서 선의 길이는 아무런 의미가 없고, 선이 교차되는 부분은 점으로 생각하지 않습니다. 쾨니히스베르크의 다리 문제로 유명한 한붓그리기 등이 그래프 이론에 해당합니다.

그래프에는 시작점과 끝점이 일치하는 그래프인 회로와, 두 점 사이에 반드시 하나의 선이 존재하는 그래프인 트리가 있습니다. 회로는 점의 개수와 선의 개수가 항상 같은 반면, 트리는 점의 개수가 선의 개수보다 항상 1개 더 많습니다.

위 문제에서 각 도시를 점, 도시와 도시를 연결하는 도로를 선으로 생각하면 20개의 점과 20x19 / 2=190 (개) 선을 갖는 그래프로 표현할 수 있습니다. 모든 마을을 연결하는 도로의 최소 개수는 모든 점을 최소한의 선으로 모두 연결하는 그래프인 트리 모양일 때의 선의 개수와 같습니다. 점이 20개인 트리에서 선의 개수는 19개이므로 (개)의 선을 잘라낼 수 있습니다. 따라서 한꺼번에 폐쇄할 수 있는 도로의 최대 개수는 171개입니다.

<1> 다음과 같이 3×3 격자 모양의 그물이 있습니다. 이 그물을 두 부분으로 나눌 때, 최대 몇 개의 단위 변을 자를 수 있는지 구하시오. 단, 단위 변은 점과 점 사이의 길이가 1인 선을 의미합니다.<2> 어떤 나라에 섬 8개가 있는데, 1에서 8까지의 번호가 붙어 있습니다. 두 섬 사이의 항로가 개설된 경우는 두 섬의 숫자를 배열해서 두 자리 수를 만들었을 때, 3으로 나누어떨어지는 경우뿐입니다. 섬 1에서 섬 7로 가는 방법의 가짓수를 구하시오. 다른 섬을 경유하여 가는 방법도 포함합니다.

<3> 어떤 나라에서 도시와 도시를 연결하는 도로는 모두 일방통행이고, 어느 한 도시에서 다른 도시로 이동할 때는 2개 이하의 도로를 통해서 항상 갈 수 있도록 설계되어 있습니다. 어느 날 도로 보수를 위해 한 곳의 도로가 폐쇄되었습니다. 이 경우 한 도시에서 다른 목적 도시까지 3개 이하의 도로를 통해서 항상 갈 수 있음을 보이시오.
경향신문