On considère le graphe Γ ci-dessous :
Donner l'ordre du graphe puis le degré de chacun des sommets.
Il y a 8 sommets donc le graphe Γ est d'ordre 8.
Les degrés des sommets sont :
| Sommets | A | B | C | D | E | F | G | H |
| Degré | 3 | 4 | 2 | 3 | 4 | 2 | 4 | 4 |
On range les sommets par ordre alphabétique. Donner la matrice d'adjacence M associée au graphe.
La matrice d'adjacence du graphe Γ est :
Une des trois matrices R, S ou T est la matrice .
; ; .
Sans calculer la matrice , indiquer quelle est la matrice en justifiant votre choix.
Le graphe n'est pas orienté et la matrice R n'est pas symétrique par conséquent, la matrice R ne convient pas.
On a or il existe au moins une chaîne de longueur 3 qui relie les sommets A et C par exemple A-G-B-C donc la matrice T ne convient pas.
La matrice S est la seule des trois matrices proposées susceptible d'être égale à .
Donner, en justifiant, le nombre de chaînes de longueur 3 reliant G à C. Les citer toutes.
Les sommets étant classés dans l'odre alphabétique, le terme de de la matrice donne le nombre de chaînes de longueur 3 reliant le sommet G au sommet C.
Il existe quatre chaînes de longueur 3 qui relient les sommets G et C : G-A-B-C ; G-E-D-C ; G-H-B-C ; G-H-D-C.
Déterminer en justifiant si ce graphe est :
complet ;
Les sommets A et C ne sont pas adjacents donc le graphe n'est pas complet.
connexe.
Les termes de la matrice qui ne sont pas sur la diagonale sont différents de 0. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne de longueur 3 les reliant. Le graphe est connexe.
Le graphe Γ modélise le plan d'un parc public. Les arêtes du graphe représentent les allées du parc et les sommets du graphe sont les intersections.
En début de journée, le responsable du service d'entretien fait le tour du parc pour inspecter l'état des allées.
Est-il possible d'optimiser le parcours pour que le responsable passe par toutes les allées sans emprunter plusieurs fois la même allée ? Justifier la réponse. Si oui proposer un parcours.
Effectuer un parcours qui passe une seule fois par chaque allée c'est chercher si il existe une chaîne eulérienne.
Le graphe est connexe et il n'y a que deux sommets A et D de degré impair, il existe donc des chaînes eulérienne d'extrémités A et D.
Un parcours qui passe une seule fois par chaque allée est possible par exemple A - F - E - G - A - B - G - H - D - C - B - H - E - D.
Pour rationaliser le nettoyage des allées, on souhaite établir un circuit commençant et finissant par le garage situé en G et qui passe par toutes les allées une et une seule fois.
Quel est le nombre minimal d'allées qu'il faudrait tracer pour obtenir un tel circuit ?
Pour qu'un graphe connexe admette un cycle eulérien, il suffit que tous ses sommets soient de degré pair.
Il suffit de rajouter une allée entre les intersections A et D pour qu'un tel circuit soit possible.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.