郵便配達員問題(奇数次数の頂点が2個) 頂点数 8 のランダムな重みつきグラフの場合 Graph G : 0 4 2 5 1 0 5 5 4 0 0 1 0 2 0 1 2 0 0 0 0 5 0 3 5 1 0 0 2 4 1 4 1 0 0 2 0 1 3 0 0 2 5 4 1 0 1 3 5 0 0 1 3 1 0 3 5 1 3 4 0 3 3 0 u = 2 v = 6 Semi-Eulerian Walk from u to v : 2 -> 7 -> 3 -> 6 -> 5 -> 7 -> 6 -> 0 -> 1 -> 3 -> 0 -> 2 -> 5 -> 1 -> 7 -> 0 -> 4 -> 3 -> 5 -> 4 -> 6 Minimum Path from v to u : 6 -> 5 -> 4 -> 0 -> 2 Total Walk : 2 -> 7 -> 3 -> 6 -> 5 -> 7 -> 6 -> 0 -> 1 -> 3 -> 0 -> 2 -> 5 -> 1 -> 7 -> 0 -> 4 -> 3 -> 5 -> 4 -> 6 -> 5 -> 4 -> 0 -> 2 Length = 61