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é | 2 | 3 | 4 | 3 | 4 | 2 | 4 | 4 |
Déterminer en justifiant si ce graphe est :
complet ;
Les sommets A et E ne sont pas adjacents donc le graphe n'est pas complet.
connexe.
La chaîne A-B-C-E-G-F-H-D contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe au moins une chaîne de longueur inférieure ou égale à 7 ayant pour extrémités ces deux sommets.
Pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe 𝒢 est connexe.
Déterminer en justifiant si le graphe 𝒢 admet un cycle eulérien ou une chaîne eulérienne.
Le graphe est connexe et il n'y a que deux sommets B et D de degré impair, il existe donc une chaîne eulérienne d'extrémités B et D.
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 :
On donne . Donner, en justifiant, le nombre de chemins de longueur 3 reliant E à H.
Les termes de la matrice donnent le nombre de chaînes de longueur 3 entre deux sommets.
Le terme situé à l'intersection de cinquième ligne et de la dernière colonne de la matrice est égal à 4.
Il y a 4 chaînes de longueur 3 d'origine E et d'extrémité H.
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.