Nel problema “matita” è facile notare come la richiesta sia praticamente quella di trovare un cammino euleriano per andare dal punto A al punto B. analizzando il caso di esempio è facile notare come i cammini possibili siano diversi, ma qual’è la “regola” da seguire nella visita del grafo per esser certi di arrivare a destinazione e non rimanere bloccati?
Se hai due vertici di grado dispari devi partire da uno dei due e l'altro sarà il vertice d'arrivo.
La regola poi dovrebbe essere di evitare gli archi che sono ponti a meno che non sia possibile fare altrimenti. Un ponte è un arco che connette due parti di grafo che senza di lui sarebbero sconnesse.Ad esempio prendi i collegamenti:
1 2
2 3
3 1
1 4
4 5
5 6
6 4
...il collegamento 1 4 è un ponte perchè se lo elimini rimangono due sottografi non connessi tra loro.
Almeno questo è quello che ho trovato io finora :-)non ho ancora risolto il problema ma la strada dovrebbe essere questa.
Oppure bisogna trovare i vari cicli ed unirli: ad esempio 1 3 2 4 e 3 5 4 6 3 possono essere uniti in 1 3 5 4 6 3 2 4
Grazie mille wil93 per il link!
quindi se ho capito bene supponendo di voler stampare il “percorso” bisogna applicare nei nodi ricorsivamente la seguente funzione:
visita(n)
1)se il nodo non ha archi collegati: stampa nodo; richiama la funzione visita (stak.top “se non è vuoto”); return;
2)se il nodo ha archi collegati: aggiungere nodo (n) allo stack in top; scegliere uno dei nodi collegati (n1), cancellare l’arco (n-n1), richiamare la funzione visita(n1)
L’unica cosa che non è chiara è se c’è un ordine da seguire anche nella scelta di n1 (qualora i nodi collegati siano più di uno) oppure se è necessario scegliere uno qualsiasi degli archi…
rileggendo ho notato che il tipo di visita illustrato in questa pagina riporta al nodo di partenza, mentre nel problema della matita l’obiettivo è terminare in un nodo diverso da quello di partenza, che modifiche dovrei apportare per trovare il percorso giusto?
rileggendo ho notato che il tipo di visita illustrato in questa pagina riporta al nodo di partenza, mentre nel problema della matita l'obiettivo è terminare in un nodo diverso da quello di partenza, che modifiche dovrei apportare per trovare il percorso giusto?La visita che torna al punto di partenza si chiama eulerian circuit. La visita che termina in un nodo diverso da quello di partenza si chiama eulerian path o eulerian tour. Nella pagina linkata si parla di entrambe.gianpiero96
Tra l'altro, se in un dato grafo esiste un eulerian circuit allora non può esistere anche un eulerian path (e viceversa).
Ok perfetto grazie mille!
per quanto riguarda invece il cammino\ciclo Hamiltoniano (sempre riguardante la visita dei grafi) che consiste nel visitare tutti i nodi passando da essi una sola volta, esistono anche in questo caso regole specifiche da seguire per la visita del grafo? (un problema che sfrutta questo tipo di grafo dovrebbe essere "la tavola rotonda di Camelot" nazionali 2005)
Quindi no, non ci sono regole specifiche da seguire... semplicemente sono problemi NP quindi non si conoscono algoritmi che li risolvono (a parte i brute force con complessità esponenziale).In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete.
Nel caso di camelot, si deve sfruttare un'ipotesi garantita dal testo (ovvero: ogni cavaliere ha come amici almeno la metà di tutti i cavalieri).