[Generico] Come si possono toccare tutti i Lati di un Grafo?
Inviato: mar gen 02, 2007 5:19 pm
Ok, il Rompiballe è tornato (tranquilli questa prometto che è la seconda ed ultima domanda sull'argomento!)
Dopo aver Implementato l'Algoritmo di Kruskal, ora mi viene posto un secondo problema, per risolvere il quale so che potrò usare un po' del codice già scritto, ma quella che a me manca è proprio l'idea "concettuale" di come si faccia:
è il problema dei Catenyms, che altro non significa che, data una serie di parole, devo restituire una "catena" di queste parole in modo da usarle tutte (e una sola volta), e tale per cui l'ultima lettera della prima sia la stessa iniziale della successiva: esempio (così è chiaro la stupidata che è):
Parole date:
aloha
arachnid
dog
gopher
rat
tiger
Risultato che devo dare: (non è detto che sia l'unico, basta sia uno giusto)
aloha.arachnid.dog.gopher.rat.tiger
[E dire, se caso, se una sequenza tale non esiste, cioè è impossibile formarla...]
La mia idea era di strutturare tutto con un grafico, così che i Nodi sono le lettere, e i lati (orientati -> )sono le parole che li hanno agli estremi: il problema si riduce a: esiste un percorso che tocca TUTTI I LATI e non ripassa mai due volte dallo stesso lato?
(Credo esistano già algoritmi per questo nella teoria dei Grafi, ma fra i tanti che ho visti, il trovare un percorso che tocchi ogni lato non l'ho ancora fatto, e cercando non sono riuscito a trovare nulla...).
Qualcuno mi da una (o anche due) mano?
Thx!
Dopo aver Implementato l'Algoritmo di Kruskal, ora mi viene posto un secondo problema, per risolvere il quale so che potrò usare un po' del codice già scritto, ma quella che a me manca è proprio l'idea "concettuale" di come si faccia:
è il problema dei Catenyms, che altro non significa che, data una serie di parole, devo restituire una "catena" di queste parole in modo da usarle tutte (e una sola volta), e tale per cui l'ultima lettera della prima sia la stessa iniziale della successiva: esempio (così è chiaro la stupidata che è):
Parole date:
aloha
arachnid
dog
gopher
rat
tiger
Risultato che devo dare: (non è detto che sia l'unico, basta sia uno giusto)
aloha.arachnid.dog.gopher.rat.tiger
[E dire, se caso, se una sequenza tale non esiste, cioè è impossibile formarla...]
La mia idea era di strutturare tutto con un grafico, così che i Nodi sono le lettere, e i lati (orientati -> )sono le parole che li hanno agli estremi: il problema si riduce a: esiste un percorso che tocca TUTTI I LATI e non ripassa mai due volte dallo stesso lato?
(Credo esistano già algoritmi per questo nella teoria dei Grafi, ma fra i tanti che ho visti, il trovare un percorso che tocchi ogni lato non l'ho ancora fatto, e cercando non sono riuscito a trovare nulla...).
Qualcuno mi da una (o anche due) mano?
Thx!