A에서 출발해 갈라진 길을 모두 돌아보려 해요. 중앙 O에는 A, B, C로 가는 세 길만 붙어 있고, 다른 길은 없어요. 아래 길이는 실제 도로를 잰 값이 아닌 자체 모형의 수치예요. 모든 길은 양방향으로 다닐 수 있고 여러 번 지나도 돼요.
| 길 | O–A | O–B | O–C |
|---|---|---|---|
| 길이 | 3 | 4 | 5 |
세 끝점을 모두 방문한 뒤 A로 돌아오면 최소 이동 길이는 24입니다. 그런데 다른 곳에서 끝내도 된다면 15까지 줄일 수 있을까요? A에서 출발한다는 조건을 유지하는지 먼저 확인해 볼까요?
A→O→B→O→C로 다니면 길이는 3+4+4+5=16입니다. 15를 얻는 B→O→A→O→C는 B에서 출발했어요. 길이 계산이 맞아도 출발점을 몰래 바꾼 답이에요. 어느 이동이 정말 최소인지 알려면 더 짧게 다닐 수 없다는 근거도 필요해요.
일반 모형을 정할게요. 꼭짓점과 길이 유한하고 전체가 연결돼 있으며, 돌아 도는 순환길이 없는 무방향 연결망이에요. 이를 나무그래프라고 해요. 각 길의 길이는 양수예요. 출발점 s와 끝점 t는 꼭짓점이고, 길 하나를 끝까지 따라 다음 꼭짓점으로 이동해요. 모든 꼭짓점을 방문하되 꼭짓점이나 길을 다시 지나도 돼요. W는 모든 길의 길이를 한 번씩 더한 값이에요.
나무에서는 두 점 사이에 되풀이하지 않는 경로가 하나뿐이에요. 길 하나를 지우면 두 묶음으로 갈라지는데, 그렇지 않다면 그 길 양끝을 잇는 다른 경로가 남아 순환을 만들기 때문이에요. 모든 꼭짓점을 방문하려면 각 길도 한 번 이상 지나야 해요.
지운 길의 양쪽에 s와 t가 각각 있다면 그 길을 지나는 횟수는 홀수이고, 적어도 한 번이에요. s와 t가 같은 쪽에 있다면 다른 쪽을 방문한 뒤 다시 돌아와야 하므로 짝수이며 적어도 두 번이에요. 앞 경우의 길들만 모으면 유일한 s–t 경로가 돼요. 그 경로의 길이를 d(s,t)라 해 볼까요?
모든 길을 두 번씩 다니는 길이 2W에서 s–t 경로만 한 번씩 덜 다닐 수 있다는 하한이에요. 실제로 이 값을 얻을 수도 있어요. s–t 경로를 차례로 진행하면서 옆으로 붙은 가지들은 먼저 갔다가 돌아와요. 가지 안에서 다시 갈라지는 길도 같은 방식으로 왕복해요. 전체가 유한하므로 모든 가지를 끝낸 뒤 t에 도착해요.
이 이동은 s–t 경로의 길을 한 번씩, 나머지 길을 두 번씩 지나요. 앞서 얻은 하한과 같으므로 최소예요. 반대로 최소 이동에서는 반드시 이 횟수를 지켜야 해요. 각 길이가 양수여서 한 길이라도 하한보다 더 지나면 전체 길이가 엄격히 늘기 때문이에요. 최소 횟수 조건은 필요할 뿐 아니라 충분해요.
이제 끝점을 고르는 조건을 바꿔 볼까요?
출발점이 s로 정해졌다면 s에서 가장 먼 꼭짓점들만 최적 끝점이에요. 그런 점이 여러 개면 모두 같은 최소값을 줘요. 양끝을 모두 고를 수 있을 때에만 전체 연결망에서 가장 먼 두 점을 택해요. 이것은 출발점이 고정된 경우의 최대 거리와 다를 수 있어요.
첫 모형에서 W=12입니다. A로 돌아오면 24, A에서 출발해 다른 곳에서 끝내면 24−8=16입니다. A에서 가장 먼 점은 C입니다. 양끝을 자유롭게 고르면 가장 먼 B와 C 사이 거리 9를 빼서 15가 돼요. 세 조건의 답을 같은 ‘최단거리’라는 이름으로 합칠 수 없어요.
꼭짓점 하나뿐인 연결망에서는 길이 없고 세 경우 모두 0입니다. 순환길이 있거나 음수 길이를 주는 경우에는 방금 나무의 분리 논증을 그대로 적용하지 않아요. 실제 통행 시간의 변화, 일방통행, 방문 시간표도 현재 모형의 조건이 아니에요.
교사는 이동 순서를 한 가지 적은 답에 하한을 따로 증명하게 해요. 제공 교재의 필요충분조건을 최소 이동의 통과 횟수에 적용하며, 그래프 정의와 전체 경로 분류까지 제공 교재에 실려 있다고 주장하지 않아요.
착안: TUM의 우편 경로 문제 정의와 Oscar Levin의 나무그래프·유일경로 성질. 원문의 방향 알고리즘이나 그림을 옮기지 않고 무방향 양수 나무에서 출발·종료 조건의 비교와 자체 수치·하한·달성 증명을 구성했어요.