Costo minimo passeggiata chiusa in un grafico

Question

C'è un algoritmo efficiente che fornisce il costo minimo passeggiata chiusa in un grafo non orientato, che le visite tutti i vertici?

Questo problema ha un nome? Ho cercato di ridurre questo a problemi simili (in particolare il problema del commesso viaggiatore) per vedere se era NP-hard, ma senza successo.

Ecco un esempio:

Poi una possibile passeggiata chiuso è:. A, B, C, D, C, B, A, con un costo di 6

Grazie!

Answer 1

L'utilizzo di questo risposta , trovando il costo minimo passeggiata chiuso (o semplicemente il suo costo) di un arbitrario 4 regolare grafico a planare, con pesi 1, si può decidere se si ha un percorso di Hamilton, ma questo problema è NP -completare. Quindi il problema originale è NP-hard.

Answer 2

Il problema è equivalente a TSP. Calcolare tutte le distanze più brevi a coppie tra i vertici del grafo $ G $. Dai grafo completo $ K_n $ che è ponderato con i brevi-distanze del grafico originale $ G $. Il tour dei TSP corrisponde completi grafico a breve min-costo di cammino chiuso.

Più precisamente, un breve giro $ \ pi $ a $ K_n $ decodifica una passeggiata chiusa in $ G $: basta sostituire ogni fronte $ (u, v) $ a $ \ pi $ per il percorso più breve da $ u $ a $ v $. Chiaramente, i costi sono conservati. Si supponga che ci sarebbe stata una breve passeggiata chiuso in $ G $. Seleziona selezionare i vertici in ordine di apparizione prima. Questa permutazione implica un giro in $ K_n $ (forse anche più corta della passeggiata chiuso in $ G $), quindi abbiamo una contraddizione.

Vedere la figura per il vostro esempio.