Dessiner le graphe (non orienté) à huit sommets dont les arêtes sont :
(1 ; 2), (1 ; 3), (2 ; 3), (2 ; 4), (2 ; 7), (3 ; 5), (3 ; 6), (3 ; 7), (4 ; 5), (4 ; 7), (5 ; 6), (5 ; 7), (6 ; 7), (6 ; 8), (7 ; 8).
Donner la matrice M associée à ce graphe.
Combien y a-t-il de chemins de longueur 3 permettant de se rendre du sommet 1 au sommet 8 ?
Les donner tous.
Pour déterminer le nombre de chaînes de longueur 3 reliant le sommet 1 au sommet sommet 8, on calcule à l'aide de la calculatrice.
Comme , il y a trois chemins de longueur 3 reliant le sommet 1 au sommet sommet 8.
Les trois chaînes de longueur 3 reliant le sommet 1 au sommet sommet 8 sont (1-2-7-8); (1-3-7-8) et (1-3-6-8).
Est-il possible de parcourir toutes les arêtes de ce graphe sans passer plus d'une fois par la même arête ?
Parcourir toutes les arêtes de ce graphe sans passer plus d'une fois par la même arête c'est déterminer si ce graphe admet une chaîne eulérienne.
Aucun des termes de la matrice n'est nul alors, pour chaque paire de sommets, il existe au moins une chaîne de longueur 3 reliant les deux sommets donc le graphe est connexe. Les degrés des sommets sont :
| Sommet | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Degré du sommet | 2 | 4 | 5 | 3 | 4 | 4 | 6 | 2 |
Le graphe est connexe et seuls les sommets 3 et 4 sont de degré impair, le graphe admet une chaîne eulérienne de d'extrémités 3 et 4.
Existe-il un cycle passant une fois et une seule par toutes les arêtes du graphe ?
Tous les sommets de ce graphe connexe ne sont pas de degré pair, alors il n'existe pas de cycle eulérien.
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.