[Grafi] G diretto e aciclico algo per cammino Hamiltoniano
Sia G un grafo aciclico e diretto, descrivere un algoritmo che in O(n+m) determina se G contiene un cammino Hamiltoniano.
Cammino Hamiltoniano: è un cammino orientato che passa per ogni nodo esattamente una volta.
La mia idea è la seguente:
effettua una DFS sul grafo e inizializzo due array indg e outdg che contengono rispettivamente il grado entrante ed uscente per ogni nodo. Durante la DFS aggiorno i due array, e alla fine li controllo parallellamente tenendo conto che deve esistere un solo nodo u con indg=0 e outdg = 1, il quale sarebbe l'unico nodo senza archi entranti, e un solo nodo v con indg[v] = 1 e outdg[v] = 0, che sarebbe l'ultimo nodo del cammino.
Tutti gli altri devono avere indg[z]=1 e outdg[z] = 1 , dato che sono nodi intermedi e non possono essere presenti cicli per ipotesi.
Lo pseudocodice che propongo è il seguente:
I tre array suppongo siano variabili globali. La comlessità di check_hamiltoniano è O(n), la DFS_H() è O(m), quindi
l'algo DFS_Hamilt avrà una complessità pari a O(3n + m ) = O(n + m).
Avete da propormi qualche altra soluzione? Ho sbagliato qualcosa? Funziona sempre questo meccanismo?
Ciao e buon weekend
Cammino Hamiltoniano: è un cammino orientato che passa per ogni nodo esattamente una volta.
La mia idea è la seguente:
effettua una DFS sul grafo e inizializzo due array indg e outdg che contengono rispettivamente il grado entrante ed uscente per ogni nodo. Durante la DFS aggiorno i due array, e alla fine li controllo parallellamente tenendo conto che deve esistere un solo nodo u con indg=0 e outdg = 1, il quale sarebbe l'unico nodo senza archi entranti, e un solo nodo v con indg[v] = 1 e outdg[v] = 0, che sarebbe l'ultimo nodo del cammino.
Tutti gli altri devono avere indg[z]=1 e outdg[z] = 1 , dato che sono nodi intermedi e non possono essere presenti cicli per ipotesi.
Lo pseudocodice che propongo è il seguente:
algo DFS_Hamilt(G: grafo) -> boolean
for ogni nodo u in V do
Vis = 0
indg = 0
outdg = 0
for ogni nodo u in V do
if Vis == 0 then
DFS_H(u)
return check_hamiltoniano()
algo DFS_H(n: nodo) -> boolean
Vis = 1
for ogni nodo v in V do
indg[v] = ind[v] + 1
outdg = outdg + 1
if Vis[v] == 0 theb
DFS_H(v)
algo check_hamiltoniano() -> boolean
primo = false
secondo = false
for ogni nodo u in V do
if indg == 0 and outdg == 1 then
if(primo) return false
primo = true
else if indg == 1 and outdg == 0 then
if(secondo) return false
secondo = true
else if indgu + outdg > 2 then
return false
return primo and secondo
I tre array suppongo siano variabili globali. La comlessità di check_hamiltoniano è O(n), la DFS_H() è O(m), quindi
l'algo DFS_Hamilt avrà una complessità pari a O(3n + m ) = O(n + m).
Avete da propormi qualche altra soluzione? Ho sbagliato qualcosa? Funziona sempre questo meccanismo?
Ciao e buon weekend
Risposte
Non sono d'accordo con la tua strategia (non ho più di tanto pensato a come risolverlo però). Stiamo parlando di un grafo diretto per cui, anche se aciclico, possono esistere più percorsi che collegano due nodi. Considera per esempio il grafo con tre nodi e i tre archi \((1, 2), (2, 3), (1, 3)\). Il grafo è diretto, aciclico e possiede un cammino hamiltoniano \((1, 2, 3),\) ma non rispetta le condizioni del tuo algoritmo.
Giusto grazie. Adesso ci penso un altro pò.
Considera comunque che a seconda di come è implementato il grafo il numero di archi entranti e uscenti potrebbe essere già disponibile o richiedere una complessità diversa. Un'affermazione sicuramente vera che hai fatto è che deve esistere un solo nodo senza archi entranti e un solo nodo senza archi uscenti. Ma a quel punto si tratta principalmente di calcolare il cammino più lungo tra questi due nodi. Se un cammino hamiltoniano esiste, allora dovrà essere uguale a questo cammino più lungo.
Forse ho trovato una strategia molto più semplice e funzionante.
L'idea:
ogni volta che visito un nodo di un cammino, incremento un contatore, mentre ogni volta che retrocedo dal cammino lo decremento. Se il contatore sarà uguale al numero di nodi del grafo |V|, allora significa che quel cammino è Hamiltoniano perchè tocca tutti i nodi una sola volta.
Altrimenti se il contatore sarà diverso da |V| allora non esiste un cammino Hamiltoniano.
Anche questo ha una complessità pari a O(n+m).
E' funzionante?
Ciao e buona domenica
L'idea:
ogni volta che visito un nodo di un cammino, incremento un contatore, mentre ogni volta che retrocedo dal cammino lo decremento. Se il contatore sarà uguale al numero di nodi del grafo |V|, allora significa che quel cammino è Hamiltoniano perchè tocca tutti i nodi una sola volta.
Altrimenti se il contatore sarà diverso da |V| allora non esiste un cammino Hamiltoniano.
VIS <- array di interi
count <- 0 // contatore
algo DFS_Hamilt(G: grafo) -> boolean
for ogni nodo u in V do
vis = 0
for ogni nodo u in V do
if vis == 0 then
DFS_H(u)
return count == |V| ? true : false
algo DFS_H(u : nodo)
vis = 1
count = count +1
for ogni nodo v in adj(u) do
if vis[v] == 0 then
DFS_H(v)
if( count == |V| ) return
count = count - 1
Anche questo ha una complessità pari a O(n+m).
E' funzionante?
Ciao e buona domenica
Non funziona così. Perchè se un nodo già è stato visitato prima del possibile cammino Hamiltoniano, dopo non risulta più visitabile. 
Sì, è quello che stavo notando. Credo abbia anche problemi nel caso in cui il primo nodo visitato non sia la sorgente.
Io stavo pensando invece a due possibile strategie:
1. Modificare un algoritmo per trovare l'ordinamento topologico di un grafo. In ogni grafo diretto e aciclico esiste un ordinamento topologico e se esiste un cammino hamiltoniano questo ordinamento deve corrispondere al cammino.
2. Assegnare un peso ad ogni arco uguale a uno ed eliminare quindi tutti i nodi che hanno un solo arco entrante ed uscente (modificando il grafo in modo che venga creato un arco dal nodo che lo precede al nodo che lo segue con un peso uguale alla somma dei pesi dei due archi). Alla fine sarà presente un grafo con solo nodi con numero di archi entranti e uscenti diversi da zero. A questo punto dovrebbe essere possibile ammettere o meno la presenza di un cammino hamiltoniano in modo abbastanza semplice.
1. Modificare un algoritmo per trovare l'ordinamento topologico di un grafo. In ogni grafo diretto e aciclico esiste un ordinamento topologico e se esiste un cammino hamiltoniano questo ordinamento deve corrispondere al cammino.
2. Assegnare un peso ad ogni arco uguale a uno ed eliminare quindi tutti i nodi che hanno un solo arco entrante ed uscente (modificando il grafo in modo che venga creato un arco dal nodo che lo precede al nodo che lo segue con un peso uguale alla somma dei pesi dei due archi). Alla fine sarà presente un grafo con solo nodi con numero di archi entranti e uscenti diversi da zero. A questo punto dovrebbe essere possibile ammettere o meno la presenza di un cammino hamiltoniano in modo abbastanza semplice.
Ok, penso di essere arrivato ad un algoritmo abbastanza semplice. Un piccolo suggerimento:
Grazie per avermi concesso del tempo.
La prima strategia penso di esser riuscito a capirla.
Comincio a visitare il nodo con grado entrante pari a 0 (se esiste altrimenti esco con un false), elimino i suoi archi uscenti dal grafo e trovo il prossimo nodo con grado entrante 0. Se ne esistono due con grado entrante uguale a 0, allora di sicuro non esiste un cammino hamiltoniano, dato che il cammino si separa e uno dei due nodi non verrà visitato. Altrimenti continuo fino a trovare l'unico ordinamento topologico possibile che coincide al cammino hamiltoniano e nella lista avro tanti nodi quanti sono i nodi di G.
La seconda strategia non la capisco.
La prima strategia penso di esser riuscito a capirla.
Comincio a visitare il nodo con grado entrante pari a 0 (se esiste altrimenti esco con un false), elimino i suoi archi uscenti dal grafo e trovo il prossimo nodo con grado entrante 0. Se ne esistono due con grado entrante uguale a 0, allora di sicuro non esiste un cammino hamiltoniano, dato che il cammino si separa e uno dei due nodi non verrà visitato. Altrimenti continuo fino a trovare l'unico ordinamento topologico possibile che coincide al cammino hamiltoniano e nella lista avro tanti nodi quanti sono i nodi di G.
ORD_TOP_HAMILT(G: grafo) -> boolean
indeg : array dei gradi entranti inizializzato a 0
for ogni nodo u in V do
for ogni nodo w in adj(u) do
indeg[w] = indeg[w] + 1
S : stack dei nodi con grado entrante pari a 0
for ogni nodo v in V do
if indeg[v] == 0 then
S.push(v)
if (S.isEmpty()) return false
L : lista vuota
while !S.isEmpty() do
flag = false
v = s.pop()
for ogni adiacente w di v do
indeg[w] = indeg[w] - 1
if ( indeg[w] == 0 and flag == false) then
flag = true
s.push(w)
else return false
return L.size() == |V|
La seconda strategia non la capisco.
L'algoritmo a cui avevo in mente è a grandi linee quello. Ci sono però alcuni commenti che posso fare:
1. Non hai effettivamente bisogno di memorizzare il cammino hamiltoniano (ti lascio il compito di capire come fare).
2. Invece di !S.isEmpty() potresti usare S.size() == 1. Se hai infatti una dimensione diversa non può esistere un cammino hamiltoniano e puoi tranquillamente uscire dal ciclo. In effetti non ha neanche molto senso usare una struttura dati tipo stack (basta una singola variabile che può essere nulla oppure uguale ad un nodo).
1. Non hai effettivamente bisogno di memorizzare il cammino hamiltoniano (ti lascio il compito di capire come fare).
2. Invece di !S.isEmpty() potresti usare S.size() == 1. Se hai infatti una dimensione diversa non può esistere un cammino hamiltoniano e puoi tranquillamente uscire dal ciclo. In effetti non ha neanche molto senso usare una struttura dati tipo stack (basta una singola variabile che può essere nulla oppure uguale ad un nodo).
L'altro algoritmo è più facile da spiegare a parole che in codice. L'idea è quella di contrarre nel tuo grafo tutti i cammini di nodi con un solo nodo entrante ed uscente per formare archi di peso uguale alla lunghezza di quel cammino. Ad un certo punto potresti incontrare degli archi già presenti ma con pesi diversi. Se l'arco esistente ha peso 1, può essere eliminato lasciando il solo arco con peso maggiore, in caso contrario non può esistere un cammino hamiltoniano. Se oltre a contrarre questi cammini elimini dal grafo tutti i nodi con un solo un arco entrante o uscente, allora puoi osservare che se esiste un cammino hamiltoniano rimarrà alla fine un solo nodo.
Grazie mille.
1- Si in effetti se ne esco vivo dal while, mi basta un return true.
2- Il while cicla affichè un nodo ha un adiacente, altrimenti esce. Quindi devo poter contare i nodi visitati per la verifica finale ?
La seconda strategia tra poco la provo su carta e penna.
1- Si in effetti se ne esco vivo dal while, mi basta un return true.
2- Il while cicla affichè un nodo ha un adiacente, altrimenti esce. Quindi devo poter contare i nodi visitati per la verifica finale ?
ORD_TOP_HAMILT(G: grafo) -> boolean
indeg : array dei gradi entranti inizializzato a 0
for ogni nodo u in V do
for ogni nodo w in adj(u) do
indeg[w] = indeg[w] + 1
N: nodo con nessun arco entrante inizializzato a null
for ogni nodo v in V do
if indeg[v] == 0 then
if N == null then
S.push(v)
else // se esistono due nodi senza archi entranti ritorno false
return false
if (N== null) return false // se non esiste un nodo senza archi entranti ritorno false
count = 1 // contatori dei nodi
while N!= null do
flag = false
for ogni adiacente w di v do
indeg[w] = indeg[w] - 1
if ( indeg[w] == 0 and flag == false) then
flag = true
N = w
count = count +1
else return false
endfor
N = null
endwhile
return count == |V|
La seconda strategia tra poco la provo su carta e penna.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo