Teoria dei grafi - Attraversabilità
Un grafo è attraversabile se è possibile disegnare un percorso tra tutti i vertici senza ripercorrere lo stesso percorso. Sulla base di questo percorso, ci sono alcune categorie come il percorso di Eulero e il circuito di Eulero che sono descritti in questo capitolo.
Sentiero di Eulero
Il percorso di Eulero contiene ogni lato di "G" esattamente una volta e ogni vertice di "G" almeno una volta. Si dice che un grafo connesso G sia attraversabile se contiene un percorso di Eulero.
Example
Sentiero di Eulero = dcabde.
Circuito di Eulero
Nel cammino di Eulero, se il vertice iniziale è uguale al vertice finale, allora è chiamato circuito di Eulero.
Example
Euler’s Path = abcdagfeca.
Teorema del circuito di Eulero
Un grafo connesso 'G' è attraversabile se e solo se il numero di vertici con grado dispari in G è esattamente 2 o 0. Un grafo connesso G può contenere un percorso di Eulero, ma non un circuito di Eulero, se ha esattamente due vertici con un grado strano.
Note - Questo percorso di Eulero inizia con un vertice di grado dispari e termina con l'altro vertice di grado dispari.
Example
Euler’s Path- beabdca non è un circuito di Eulero, ma è un percorso di Eulero. Chiaramente ha esattamente 2 vertici di grado dispari.
Note - In un grafo connesso G, se il numero di vertici con grado dispari = 0, allora esiste il circuito di Eulero.
Grafico hamiltoniano
Si dice che un grafo connesso G sia un grafo hamiltoniano, se esiste un ciclo che contiene tutti i vertici di G.
Ogni ciclo è un circuito ma un circuito può contenere più cicli. Un tale ciclo è chiamato aHamiltonian cycle di G.
Sentiero Hamiltoniano
Un grafo connesso si dice hamiltoniano se contiene ogni vertice di G esattamente una volta. Tale percorso è chiamato aHamiltonian path.
Example
Hamiltonian Path- edbac.
Note
Il circuito di Eulero contiene ciascun bordo del grafico esattamente una volta.
In un ciclo hamiltoniano, alcuni bordi del grafico possono essere saltati.
Example
Dai un'occhiata al grafico seguente:
Per il grafico mostrato sopra -
Il sentiero di Eulero esiste - falso
Il circuito di Eulero esiste - falso
Il ciclo hamiltoniano esiste - vero
Il percorso hamiltoniano esiste - vero
G ha quattro vertici con grado dispari, quindi non è attraversabile. Saltando gli archi interni, il grafo ha un ciclo hamiltoniano passante per tutti i vertici.