Exercice de maths sur graphe connexe ou complet de terminale avec sommets, arêtes, circuit, chemin, villes, degrés, pair, impair.
Exercice N°465 :
Stéphanie a représenté par le graphe ci-dessous toutes les villes dans lesquelles se trouvent les agences qu’elle doit visiter chaque mois. Dans ce graphe, les arêtes sont les axes routiers et les sommets sont les villes.
1) Déterminer si le graphe est connexe.
2) Déterminer si le graphe est complet.
Stéphanie voudrait effectuer un circuit qui passe une et une seule fois par chaque ville dans laquelle se trouve une agence de location dé vélos.
3-4) Déterminer si ce circuit existe dans les deux cas suivants :
3) La ville d’arrivée est la même que la ville de départ.
4) La ville d’arrivée n’est pas la même que la ville de départ.
Bon courage,
Sylvain Jeuland
Mots-clés de l’exercice : graphe, connexe, complet, terminale.
Exercice précédent : Matrices – Fonction, système, équation, inverse – Terminale
1) Dans ce graphe, on peut atteindre n’importe quel sommet à partir d’un quelconque sommet en passant par des arêtes. Il existe un chemin entre chaque couple de sommet donc le graphe est connexe.
2) Le graphe n’est pas complet car il existe au moins deux sommets qui n’ont pas d’arêtes les reliant. Par exemple, les sommets A et C n’ont pas d’arête commune.
3) Dire que l’on passe par toutes les arêtes avec la ville d’arrivée qui est la même que la ville de départ, revient à parcourir un cycle eulérien.
Un cycle eulérien du graphe est une chaîne eulérienne du graphe qui est un cycle, c’est-à-dire une chaîne eulérienne dont les extrémités sont confondues.
Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Or les degrés de H et de I valent 3 et sont impairs. Donc ce graphe n’admet pas de cycle eulérien, donc on ne peut pas faire le parcours de Stéphanie en partant de la même ville.
4) Une chaîne eulérienne est une chaîne qui contient une fois et une seule fois chaque arête du graphe.
Avec une chaîne eulérienne, pas besoin de cycle donc on peut partir d’un sommet et arriver à un autre.
Un graphe connexe admet une chaîne eulérienne distincte d’un cycle si et seulement si le nombre de sommets de degré impair est égal à 2.
Dans ce cas, si H et I sont les deux sommets du graphe de degré impair, alors le graphe admet une chaîne eulérienne d’extrémités H et I.
Stéphanie peut faire son parcours en partant de H et en arrivant à I (ou vice-versa).