• Non ci sono risultati.

Si dimostri che il problema del cammino massimo in un grafo (decidere cio`e se esiste un cammino senza ripetizioni di nodi con almeno K archi) `e NP-completo

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Si dimostri che il problema del cammino massimo in un grafo (decidere cio`e se esiste un cammino senza ripetizioni di nodi con almeno K archi) `e NP-completo"

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

3.48 Esercizio. Si dimostri che il problema del cammino hamiltoniano `e NP-completo (si rivedano l’Esempio 1.87 e l’esercizio 1.88).

Soluzione. La trasformazione τ dell’esercizio 1.88 `e una trasformazione polinomiale del problema del cammino hamiltoniano (nelle sue varianti) nel problema del circuito hamilto- niano.

3.49 Esercizio. Si dimostri che il problema del cammino massimo in un grafo (decidere cio`e se esiste un cammino senza ripetizioni di nodi con almeno K archi) `e NP-completo.

Soluzione. In base all’esercizio 3.48 il problema del cammino hamiltoniano con nodi estre- mi fissati `e NP-completo. Per trasformare il problema del cammino massimo nel problema del cammino hamiltoniano basta porre K := n− 1. Infatti in tal caso il cammino deve percorrere tutti i nodi esattamente una volta.

1

Riferimenti

Scarica adesso ( PDF - 1 pagine - 16.39 KB )

Documenti correlati

Si dimostri che il problema

[r]

Cammino Minimo Massimo Flusso

• Inizialmente vengono ordinati gli archi e definita una particolare soluzione duale iniziale y 0 che non è ammissibile ma è facile da scrivere. • A ogni iterazione gli archi

Democrazia in cammino

In alcuni casi i “giovani” stati sem- brano aver trovato il loro percorso democratico in tempi relativamente brevi (come ad esempio Senegal, Ghana, Botswana); in altri, dopo disordini

In cammino con i pellegrini

[r]

In Cammino per il Clima

Il pellegrinaggio In Cammino per il Clima vuole essere il veicolo, a partire dalle comunità locali, per esprimere un messaggio pacifico di preoccupazione verso gli

In un grafo non orientato due nodi sono adiacenti se esiste un arco che li unisce

Grafo particolare è quello "euleriano", dal matematico Eulero, che nel 1736 lo utilizzò per risolvere il problema dei ponti di Königsberg: un cammino o percorso è detto di

esiste un cammino hamiltoniano senza nodi estremi fissati. Si ripeta l’esercizio per gli altri casi di cammino hamiltoniano (i nodi estremi fissati vengono decisi dalla trasformazione).

Viceversa se al grafo iniziale si aggiunge un nodo connesso con tutti gli altri nodi (figura 4) nel primo grafo esiste un cammino hamiltoniano senza estremi fissati se e solo se

2.10 Esercizio. Si dimostri che contraendo un grafo partizionato secondo una coloratura minima (numero cromatico) si ottiene un grafo completo.

Se valesse anche nel senso opposto esisterebbe un algoritmo estremamente semplice (e polinomiale) per colorare in modo minimo un grafo (si colora arbitrariamente e si vede se il