중국인 우편배달부 문제 계산기

모든 간선(길)을 적어도 한 번 지나 출발점으로 돌아오는 가장 짧은 경로를 찾는 문제입니다. 우체부가 담당 구역의 모든 길을 지나야 하는 상황에서 이름이 붙었고, 제설차 경로·검침 경로·도로 점검 경로가 같은 문제입니다.

외판원은 모든 「지점」을 한 번씩 들르는 문제이고, 우편배달부는 모든 「길」을 지나는 문제입니다. 그리고 결정적으로 우편배달부는 다항시간에 풀립니다. 최단경로를 구해 두고 홀수 차수 정점의 최소 매칭만 찾으면 되기 때문입니다.

모든 간선을 정확히 한 번씩 지나 제자리로 오는 오일러 회로는 모든 정점의 차수가 짝수일 때만 있기 때문입니다. 어떤 정점에 들어갔으면 나와야 하므로 붙은 간선이 짝을 이루어야 합니다. 그래서 홀수인 정점만 골라 간선을 덧그려 짝수로 만드는 것이 이 문제의 전부입니다.

그런 일은 일어나지 않습니다. 모든 차수의 합이 간선 수의 두 배라 짝수이므로, 홀수인 정점이 홀수 개일 수 없습니다. 그래서 짝짓기가 언제나 가능하고 이 문제는 항상 답이 있습니다(그래프가 한 덩어리이기만 하면).

간선 길이의 합이 그대로 답입니다. 덧그릴 것이 없고 오일러 회로가 이미 있습니다. 이 경계를 먼저 확인하는 것이 좋습니다.

두 홀수 정점을 짝지어 그 사이를 이을 때 가장 싸게 잇는 방법이 최단경로이기 때문입니다. 그래서 모든 정점 쌍의 최단거리를 플로이드–워셜로 구해 두고 그 위에서 매칭만 찾으면 됩니다. 직통 간선이 있어도 우회가 짧으면 우회를 씁니다.

이 계산기는 12개까지 다룹니다. 짝짓는 방법이 (2k−1)!!가지라 12개면 10,395가지를 전수로 셉니다. 그보다 많으면 블로섬 알고리즘 같은 다항시간 매칭이 필요합니다. 실제 우편 구역에서 홀수 교차로가 그보다 많은 일은 드뭅니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.