MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

Six stops 0,1,2,3,4,50,1,2,3,4,5 are linked by weighted roads: 01:401{:}4, 02:702{:}7, 12:312{:}3, 13:613{:}6, 23:223{:}2, 24:524{:}5, 34:434{:}4, 35:835{:}8, 45:345{:}3, 14:914{:}9, 25:1025{:}10 (no other roads exist). A courier must start at stop 00, visit every other stop exactly once, and finish at stop 55. What is the minimum possible total distance?