최소연결 문제

수업에 적용한 학습 프로그램

자료 번호 8 탐구 주제 최소연결 문제

학습 목표 최소 비용의 길을 만드는 문제를 해결할 수 있다.

관련 영역 자료와 가능성, 규칙성, 도형 학습 교구 여러 가지 무게그래프

목표문제 : 어떤 도시 A, B, C, D, E를 모두 연결하는 길을 만들려고 합니 다. 이 때, 각 도시를 연결하는 비용은 아래의 그림과 같습니다. 어떻게 하 면 최소의 비용으로 각 도시를 연결하는 길을 만들 수 있을까요?

탐구문제 1 : 어떤 도시 A, B, C, D를 모두 연결하는 길을 만들려고 합니 다. 이 때, 각 도시를 연결하는 비용은 아래의 그림과 같습니다. 어떻게 하면 최소의 비용으로 각 도시를 모두 연결하는 길을 만들 수 있을까요?

연습문제 1 : 어떤 도시 A, B, C, D를 모두 연결하는 도로망과 그 때의 건설비용을 나타내고 있습니다. 이 때, 실선으로 연결된 길이 최소 비용의 도로망인지 아닌지 생각해보고, 그렇게 생각한 이유를 적어보세요.

연습문제 2 : Kruskal 알고리즘을 이용해서, 다음 그래프의 최소연결망을 찾으세요.

약속하기

각 도시와 도시 사이를 연결하는 길의 비용이 나타난 그래프에서 각 도시 사 이의 길의 비용을 원소로 하여 구성한 표를 무게표라고 부릅니다.

A B C D A - 10 10 4 B 10 - 7 8 C 10 7 - 6 D 4 8 6

-연습문제 3 : 아래의 무게그래프를 무게표로 바꾸어 보세요.

탐구문제 2 : 어떤 도시 A, B, C, D를 모두 연결하는 길을 만들려고 합니다.

이 때, 각 도시를 연결하는 비용은 아래의 그림과 같습니다. 어떻게 하면 최소 의 비용으로 각 도시를 모두 연결하는 길을 만들 수 있을까요?

A B C D A - 10 10 4 B 10 - 7 8 C 10 7 - 6 D 4 8 6

-연습문제 4 : Prim의 알고리즘을 이용하여 다음의 도시 A, B, C, D, E, F의 최소연결망을 찾으시오.

수학화 활동 사례 분석

자료 번호 8 탐구 주제 최소연결 문제

학습 목표 최소 비용의 길을 만드는 문제를 해결할 수 있다.

문제해결도구 여러 가지 무게그래프

수학적 문제

․몇 개의 지역을 어떻게 최소 비용으로 연결할 수 있을까?

․그래프에서 최소 비용의 길을 찾는 알고리즘은 무엇일까?

․무게표로 최소연결 문제를 어떻게 해결할 수 있을까?

배경지식 무게그래프, 최소 비용의 길, Kruskal 알고리즘, 무게표(무게행렬), Prim의 알고리즘

목표문제 어떤 도시 A, B, C, D, E를 모두 연결하는 길을 만들려고 합니다.

이 때, 각 도시를 연결하는 비용은 아래의 그림과 같습니다. 어떻게 하면 최소 의 비용으로 각 도시를 연결하는 길을 만들 수 있을까요?

최소연결 문제는 비용, 시간 또는 거리 등을 고려하여 최적화되도록 모든 지역 의 연결망을 만드는 문제이다. 각 지역을 꼭짓점으로, 지역끼리의 연결 관계를 변 으로 두면 무게그래프로 나타낼 수 있는데, 결국 최소연결 문제는 무게그래프의 꼭짓점들을 연결하면서 최소 비용이 드는 길을 찾는 문제이다.

지난 시간에 무게그래프에 대해서 학습했기 때문에 이번 학습주제에 대한 이해는 빨랐다. 그러나 위의 목표문제를 해결하는 데 혼란스러워 했으며, 답을 찾은 학생

탐구문제 1 어떤 도시 A, B, C, D를 모두 연결하는 길을 만들려고 합니다.

이 때, 각 도시를 연결하는 비용은 아래의 그림과 같습니다. 어떻게 하면 최소 의 비용으로 각 도시를 모두 연결하는 길을 만들 수 있을까요?

가. 탐구문제의 이해

모든 변의 무게(거리, 비용 등)가 0이상인 무게그래프에서 최소연결을 구하는 Kruskal 알고리즘은 다음과 같은 과정을 거친다(최근배 외, 2010).

1) 먼저, 최소무게의 변을 선택한다.

2) 선택된 변의 각 꼭짓점에서 연결할 수 있는 변들의 무게를 보고, 그 중에서 최 소무게인 변을 선택한다.

3) 전 단계에서 선택된 변들의 각 꼭짓점에서 연결할 수 있는 변들의 무게를 보 고, 그 중에서 최소무게인 변을 찾는다. 주의할 점은 전 단계에서 선택된 변들 과 새로 선택된 변에는 순환길¹¹⁾이 없어야 한다.

4) 이와 같은 활동을 반복하여, 모든 꼭짓점을 연결한다.

나. 학생들의 반응 분석

[그림 Ⅳ-40]은 1모둠의 문제해결 아이디어이다. 1모둠은 출발점을 A로 정하 고 가능한 길들을 모두 찾은 후에 그 중에 최소무게인 것을 선택하였다. 이 그 래프는 간단한 형태이기 때문에 문제해결이 쉽게 가능하겠지만, 더 복잡한 형 태의 그래프에서는 좋은 해결 방법이 아니다. 또한, 무게그래프에서는 변의 무 게가 중요하고 변들이 이루는 각의 크기는 의미가 없는데, 각도가 큰 쪽으로 가 11) 닫힌 길. 어느 한 꼭짓점에서 출발하여 다시 그 꼭짓점으로 돌아오는 형태의 길.

야 무게가 최소가 된다고 잘못 생각하고 있었다. 이와 같은 생각은 ‘연습문제 1’

을 해결하면서 잘못되었다는 사실을 알게 되었다.

[그림 Ⅳ-40] 1모둠의 문제해결 아이디어(자료번호8-탐구문제1)

2모둠의 문제해결 아이디어는 [그림 Ⅳ-41]과 같다. 먼저 ‘가장 큰 수를 가진 선분을 제외하고 이을 수 있는 가장 작은 수로 연결한다.’라고 하였다. 그리고

‘만약에 가장 작은 수로만 이을 수 없으면, 그 중 가장 큰 수를 제외하고 제외된 수보다 큰 수를 선택하여 연결한다.’라고 하였다. 2모둠의 아이디어도 보완할 부 분이 많지만, 가장 작은 수로만 연결했을 때 성립하지 않는 경우에 대한 대안을 제시하고 있다는 점이 의미가 있다.

[그림 Ⅳ-41] 2모둠의 문제해결 아이디어(자료번호8-탐구문제1)

3모둠은 ‘작은 수를 따라 연결한다.’라고 해결 방법을 제시하고 있다. 따라서 작은 수를 따라 연결할 때 순환길이 생겨 최소 비용의 길이 완성되지 않는 경우 가 있다는 사실까지는 생각하지 못하였다.

[그림 Ⅳ-42] 3모둠의 문제해결 아이디어(자료번호8-탐구문제1)

탐구문제 2 어떤 도시 A, B, C, D를 모두 연결하는 길을 만들려고 합니다. 이

A B C D A - 10 10 4 B 10 - 7 8 C 10 7 - 6

D 4 8 6

-<표 Ⅳ-4> Prim의 알고리즘에 따른 무게표(자료번호8-탐구문제2)

나. 학생들의 반응 분석

좀 더 단순한 그래프를 그려보거나 숫자에 번호를 매기는 등 다양한 시도를 했지만 모든 모둠이 마땅한 문제해결 아이디어를 생각해내지 못했다. 1모둠은 대각선으로 접으면 대칭이 된다는 점을 활용해보려고 했지만 큰 성과는 없었 다. 또한, 변의 수가 꼭짓점의 수보다 하나 적어야 한다는 아이디어를 떠올렸다.

하지만 순환길이 나오지 않게 하기 위한 타당한 아이디어는 떠올리지 못했다.

다음은 1모둠의 활동을 관찰한 에피소드이다.

S1: 대각선으로 선을 그으면 대칭이 되고 있어.

S2: 응. 그건 알겠어.

S1: 점이 총 4개니깐 3개(꼭짓점의 수–1)만큼 작은 수들을 고르면 되지 않을까?

S2: 음…. 그런데 순환길이 나올 수도 있잖아?

S1: 그럼 순환길이 되는지 일일이 찾아야하나?

S2: 어떻게?

S1: …

[그림 Ⅳ-43] 1모둠의 문제해결 아이디어(자료번호8-탐구문제2)