Chaîne eulérienne (extrait BAC 2014) (réf 1674) Chapitre 5 graphes et chaînes de Markov, Option maths expertes, Séquence 4 compléments: chaînes et cycles eulériens

Déterminer en justifiant si le graphe $\mathcal{G}$ est complet.

Rappel cours

Graphe complet
On appelle graphe complet un graphe dont tous les sommets sont adjacents entre eux.

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
Déterminer en justifiant si le graphe $\mathcal{G}$ est connexe.

Rappel cours

Graphe connexe
Un graphe connexe est un graphe non orienté dans lequel il existe un chemin entre chaque paire de sommets.

Aide

Il faut trouver une chaîne passant par tous les sommets

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
Donner le degré de chacun des sommets du graphe $\mathcal{G}$.

Aide

Rappel: Le degré d'un sommet est le nombre d'arêtes arrivant (ou partant) de ce sommet.

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
Déterminer en justifiant si le graphe $\mathcal{G}$ admet un cycle eulérien ou une chaîne eulérienne.

Rappel cours

Chaîne eulérienne
Une chaîne eulérienne est une chaîne sur le graphe utilisant toutes les arêtes une et une seule fois.
existence d'une chaîne eulérienne
Un graphe connexe admet une chaîne eulérienne si et seulement si ses sommets sont tous de degré pair sauf deux d'entre eux.
Cycle eulérienne
Un cycle eulérienne est une chaîne fermée sur le graphe utilisant toutes es arêtes une et une seule fois.
existence d'un cycle eulérien
Un graphe connexe admet un cycle eulérien si et seulement si ses sommets sont tous de degré pair.

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements

Vous devez être abonné pour accéder à ce contenu...

Infos abonnements

Ressource précédente: chaînes et cycles eulériens (réf 1673) Ressource suivante: Chaîne et cycle eulérien (extrait bac 2013) (réf 1675)