Problem chińskiego listonosza - graf nie-eulerowski?

vcppp_p · Post autor: **vcppp_p** » 31 sty 2012, o 20:00

Witam,
mam do rozwiązania problem chińskiego listonosza, tyle że w zadaniu graf nie jest (pół)eulerowski, więc nie wiem jak to ruszyć ... mógłby mi ktoś wyjaśnić?

Graf taki:

grzesiek27 · Post autor: **grzesiek27** » 26 maja 2012, o 23:04

Zrób z niego multigraf, dublując krawędzie o wagach 5, 1, 3, 6. Dzięki temu każdy wierzchołek grafu będzie miał parzysty stopień, graf będzie eulerowski, a zadanie będzie rozwiązane

aussie · Post autor: **aussie** » 27 maja 2012, o 01:54

A jak by wyglądało znalezienie długości optymalnej trasy komiwojażera (długość najkrótszego cyklu Hamiltona) dla powyższego grafu?