Steiner Net
MaxMin 문제 - 들아가는 말 로 돌아가기
Steiner Network
이런 상황을 함께 상상해보자.
- 네 마을이 있다. 예전에는 이 마을들을 잇는 길이 없었다. 그런데 세월이 지나면서 네 마을 사람들이 교류가 활발해졌다. 서로 친하게 지낼 일도 많아지고 물건을 옮겨야 할 일도 많아졌다. 마침내 네 마을의 촌장들이 모여 이 네 마을을 잇는 길을 만들기로 했다. 어떻게 만들어도 좋은데 이 길을 통해 한 도시에서 다른 도시로 갈 수 있게만 하면 된다. 어떻게 잇는 길이를 최소로 할 수 있을까?
문제를 단순하게 하기 위해 먼저 이 마을들이 정사각형이루는 점들에 자리하고 있다고 가장한다.
- (쉬타이너 문제) : 주어진 점이 k 개 있다. 어떻게 하면 이 k 개 점을 모두 잇되 길이를 가장 짧게 할 수 있을까?
쉬타이너 문제의 답은 쉬타이너 망이다
다음의 조건을 충족하는 망(network)을 쉬타이너 망이라 부르기로 하자.
- 모든 꼭지점들은 선분 들로 이루어져 있다.
- 하나의 꼭지점에서 뻗어나간 어떤 두 선분이 이루는 각은 120도 보다 작지 않다.[1]
- 두 개의 선분이 뻗어 나올 경우 이들이 이루는 각은 120도 보다 크거나 같다. 만약 세 개의 선분이 뻗어 나올 경우 이것들 사이의 각은 120도다.
- 정리 : 쉬타이너 문제를 해결하는 기하적 도형은 쉬타이너 망이다.
이제 위의 조건들이 '최소길이'를 갖는다는 것을 하나하나 밝혀보기로 하자.
- 기초정리 1 : 선분들로 이루어져 있다.
- 기초정리 2 : 하나의 꼭지점에서 뻗어나간 어떤 두 선분이 이루는 각은 120도 보다 작지 않다.
따라서 하나의 꼭지점에서는 세 개의 선분을 넘을 수는 없다. 그렇게 되면 120도를 넘게 될테니까.
- 기초정리 3 : 두개의 선분이 뻗어 나올 경우 이들이 이루는 각은 120도 보다 크거나 같다. 만약 세 개의 선분이 뻗어 나올 경우 이것들 사이의 각은 120도다.
쉬타이너 망을 어떻게 짤까?
만약 k 개의 점이 있다고 한다면 쉬타이너 망이 그 점을 최소의 길이로 잇는 도형이라는 것은 앞에서 밝혔다. 이로써 네 마을의 촌장들은 물자를 아껴서 길을 낼 수 있게 되었다. 그 모양은 옆의 그림처럼 될 것이다.
자, 여기서 멈추지 말고 생각을 더 해보자. 세월이 흘러 마을들은 더 분화해가면서 발전해갔다고 상상해보자. 이제가 마을이 넷이 아니라 k 개가 되었다. 다시 길을 놓아야 할 시점에 이르렀다. k 개의 마을에서 k 명의 촌장들이 다시 모여 회의를 열었다. 역시 하나의 마을도 고립되지 않도록 길을 만들되 최소 길이로 하자고 의견을 모았다. 우리에게는 쉬타이너 해법이 있기 때문에 '바로 그렇게' 만들면 된다는 것을 알 수 있다. 그러나 '과연 어떻게?' , 어떻게 그 망을 설계할 수 있을까? 해법이 하나만 있을까? k 개의 마을을 잇는 최적으로 방법은 몇 개가 가능할까?
MaxMin 문제 - 들아가는 말 로 돌아가기
Note
- ↑ 따라서 하나의 꼭지점에서는 세 개의 선분을 넘을 수는 없다. 그렇게 되면 120도를 넘게 될테니까.
Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia