Maths Expertes en Terminale

L'essentiel pour réussir

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.
graphe

  1. Donner l'ordre de $Gr$.
  2. Dresser un tableau donnant les degrés des sommets de $Gr$.
  3. En déduire le nombre d'arêtes de $Gr$.
  4. $Gr$ est-il complet?.
  5. $Gr$ est-il connexe?
  6. $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.
  7. Déterminer $M$, matrice d'adjacence de ce graphe $Gr$. Les sommets seront pris dans l'ordre alphabétique.
  8. Déterminer le nombre de chaînes de longueur 4 reliant B à D.
    Donner les toutes.
  9. Combien y a-t-il de chaînes de longueur 4 issues de A?
Solution...
Corrigé
  1. Le graphe $Gr$ et d'ordre 8.

  2. Voici un tableau donnant les degrés des sommets de $Gr$.
    sommets

  3. La somme des degrés vaut 22. Le graphe a donc 11 arêtes.

  4. $Gr$ n'est pas complet car, par exemple, les sommets A et C ne sont pas reliés par une arête.

  5. $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.

  6. graphe
  7. 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!)

  8. 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)$

  9. 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$
    graphe
    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.
    chaînes
    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

  10. 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
Réduire...

Copyright 2013 - maths-bac.com - Toute reproduction interdite - Tous droits réservés.