여섯 골목을 모두 점검하고 나가려 해요. 모든 지점만 들르면 충분할까요? 아래가 길 전체인 종이 지도예요. 대문자 A·B·C는 삼각형을 이루고, 소문자 a·b·c는 각각 붙은 막다른 끝이에요. 실제 도로 측정은 아니에요.
| 구간 | AB·BC·CA·Aa·Cc | Bb |
|---|---|---|
| 길이(m) | 각각1 | 3 |
a에서 출발해 b 또는 c에서 끝내요. 양방향으로 구간 하나를 끝까지 이동하며 모든 구간을 한 번 이상 지나요. 재방문은 허용하고 순간이동은 없어요. 전체 길이 W, 보행 길이 L, 구간 e의 통과 횟수 n_e를 정할게요. 두 출구별 최소 길이와 그때 다시 지나는 구간을 모두 찾아요.
b에서 끝내면 Cc는 갔다 돌아와야 하므로 추가1m가 필요해요. 그 횟수만 채운 뒤에는 A·B의 통과 차수가 홀수예요. 출발·종료점 이외에서는 들어온 만큼 나가야 하므로 AB를 한 번 더 지나요. c에서 끝내면 Bb 왕복의 추가3m와 AC 추가1m가 필요해요. 이 하한과 같은 이동이 실제 있어요.
b: a→A→C→c→C→B→A→B→b.
c: a→A→B→b→B→C→A→C→c.
모든 길이가 양수여서 최소라면 아래 횟수여야 하고, 이 횟수의 유효 점검 이동이면 최소예요.
각 출구의 최소 수순은 지점 이름으로 세면3개씩이에요. b에서는 위 수순 외에 a→A→B→A→C→c→C→B→b와 a→A→B→C→c→C→A→B→b뿐이에요. 방문 지점만 체크했다면 BC 구간도 지났는지 확인해 봐요. 나무에서 쓰는 왕복 공식은 고리가 있는 이 지도에 그대로 적용하지 않아요.
착안: AMSI·VCAA Circuits의 보행·오일러 길 정의. 지도·길이·중복 횟수·증명은 자체 구성했어요. 원전 그림은 옮기지 않았어요.