Graphes et matrices
A SAVOIR: le cours sur les graphes et les matrices
Exercice 5
On considère le graphe $Gr$ représenté ci-dessous.
- Donner l'ordre de $Gr$.
- Dresser un tableau donnant les degrés des sommets de $Gr$.
- En déduire le nombre d'arêtes de $Gr$.
- $Gr$ est-il complet?.
- $Gr$ est-il connexe?
-
$Gr$ admet-il un cycle eulérien? Si oui, donner en un.
$Gr$ admet-il une chaîne eulérienne? Si oui, donner en une. - Déterminer $M$, matrice d'adjacence de ce graphe $Gr$. Les sommets seront pris dans l'ordre alphabétique.
- Déterminer le nombre de chaînes de longueur 4 reliant B à D.
Les donner toutes. - Combien y a-t-il de chaînes de longueur 4 issues de A?
Corrigé
- Le graphe $Gr$ et d'ordre 8.
- Voici un tableau donnant les degrés des sommets de $Gr$.
- La somme des degrés vaut 22. Le graphe a donc 11 arêtes.
- $Gr$ n'est pas complet car, par exemple, les sommets A et C ne sont pas reliés par une arête.
- $Gr$ est connexe car, comme il existe une chaîne qui passe par tous les sommets (par exemple la chaîne A-B-D-C-E-F-C-G-H ), deux sommets quelconques mais distincts sont forcément reliés par une chaîne.
- Ce graphe est connexe, mais le nombre de ses sommets de degré impair n'est pas nul. Donc il n'admet pas de cycle eulérien.
Par contre, il a exactement 2 sommets de degré impair: D et H.
Donc il admet une chaîne eulérienne d'extrémités D et H.
Construisons une telle chaîne progressivement.
On part de: D-F-H On y greffe le cycle H-A-B-C-G-H
On obtient: D-F-H-A-B-C-G-H On y greffe le cycle F-C-D-E-F
On obtient: D-F-C-D-E-F-H-A-B-C-G-H
Ceci est une chaîne eulérienne (on notera qu'elle a bien 11 arêtes!) - La matrice d'adjacence qui suit est bien symétrique car le graphe est non orienté.
$M=(\table 0,1,0,0,0,0,0,1; 1,0,1,0,0,0,0,0; 0,1,0,1,0,1,1,0; 0,0,1,0,1,1,0,0; 0,0,0,1,0,1,0,0; 0,0,1,1,1,0,0,1; 0,0,1,0,0,0,0,1; 1,0,0,0,0,1,1,0)$ - Il suffit de calculer $M^4$
On obtient: $M^4=(\table 7,2,7,4,3,9,6,2; 2,8,4,9,3,10,7,6; 7,4,27,13,16,13,4,17; 4,9,13,18,10,19,10,10; 3,3,16,10,11,10,3,10; 9,10,13,19,10,28,16,6; 6,7,4,10,3,16,11,2; 2,6,17,10,10,6,2,16)$
On lit le coefficient situé à la 2ème ligne et la 4ème colonne. Il vaut 9.
Donc 9 chaînes de longueur 4 relient B à D.
Pour les déterminer, on considère le graphe $Gr$
Et on dessine deux arbres que l'on relie. Le premier (à gauche) donne les chaînes de longeur 2 issues de B. Le second (à droite) donne les chaînes de longeur 2 arrivant en D.
Voici donc les 9 chaînes cherchées.
B-A-B-C-D
B-A-H-F-D
B-C-B-C-D
B-C-D-C-D
B-C-D-E-D
B-C-D-F-D
B-C-F-C-D
B-C-F-E-D
B-C-G-C-D - Le nombre de chaînes de longueur 4 issues de A est égal à la somme des coefficients de la première ligne de $M^4$.
Comme $7+2+7+4+3+9+6+2=40$, le nombre de chaînes de longueur 4 issues de A est de 40