Théorie des graphes - Traversabilité

Un graphe est traversable si vous pouvez tracer un chemin entre tous les sommets sans retracer le même chemin. Sur la base de ce chemin, il existe des catégories comme le chemin d'Euler et le circuit d'Euler qui sont décrites dans ce chapitre.

Chemin d'Euler

Un chemin d'Euler contient chaque arête de «G» exactement une fois et chaque sommet de «G» au moins une fois. Un graphe connexe G est dit traversable s'il contient un chemin d'Euler.

Example

Chemin d'Euler = dcabde.

Circuit d'Euler

Dans un chemin d'Euler, si le sommet de départ est le même que son sommet de fin, alors il est appelé circuit d'Euler.

Example

Euler’s Path = abcdagfeca.

Théorème de circuit d'Euler

Un graphe connexe 'G' est traversable si et seulement si le nombre de sommets de degré impair dans G est exactement 2 ou 0. Un graphe connexe G peut contenir un chemin d'Euler, mais pas un circuit d'Euler, s'il a exactement deux sommets avec un degré étrange.

Note - Ce chemin d'Euler commence par un sommet de degré impair et se termine par l'autre sommet de degré impair.

Example

Euler’s Path- beabdca n'est pas un circuit d'Euler, mais c'est un chemin d'Euler. Clairement, il a exactement 2 sommets de degré impair.

Note - Dans un graphe connexe G, si le nombre de sommets de degré impair = 0, alors le circuit d'Euler existe.

Graphique hamiltonien

Un graphe connexe G est dit un graphe hamiltonien, s'il existe un cycle qui contient tous les sommets de G.

Chaque cycle est un circuit mais un circuit peut contenir plusieurs cycles. Un tel cycle s'appelle unHamiltonian cycle de G.

Chemin hamiltonien

Un graphe connexe est dit hamiltonien s'il contient chaque sommet de G exactement une fois. Un tel chemin s'appelle unHamiltonian path.

Example

Hamiltonian Path- edbac.

Note

  • Le circuit d'Euler contient chaque arête du graphe exactement une fois.

  • Dans un cycle hamiltonien, certaines arêtes du graphique peuvent être ignorées.

Example

Jetez un œil au graphique suivant -

Pour le graphique ci-dessus -

  • Le chemin d'Euler existe - faux

  • Le circuit d'Euler existe - faux

  • Le cycle hamiltonien existe - vrai

  • Le chemin hamiltonien existe - vrai

G a quatre sommets de degré impair, il n'est donc pas traversable. En sautant les arêtes internes, le graphe a un cycle hamiltonien passant par tous les sommets.