Kala te souhaite la bienvenueKalaMaths

Graphes et matrice d'adjacence

🟡 Moyen

Les énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres corrigés détaillés sont réservés aux abonnés.

S'abonner
Débloquer ce chapitre – 2,99 €

Cet achat est réservé à un adulte.

  1. 1

    a) Un graphe est dit k-régulier lorsque tous ses sommets ont le même degré k. Combien d'arêtes possède un graphe 3-régulier à 8 sommets ?
    b) Existe-t-il un graphe 3-régulier à 7 sommets ? Justifier.

    Voir le corrigéoffert

    a) Dans un graphe 3-régulier à 8 sommets, chaque sommet a degré 3. La somme des degrés vaut 8×3=248 \times 3 = 24. D'après le lemme des poignées de main, cette somme égale deux fois le nombre d'arêtes.
    Nombre d'arêtes =24÷2=12= 24 \div 2 = 12.
    b) Pour un graphe 3-régulier à 7 sommets, la somme des degrés serait 7×3=217 \times 3 = 21, un nombre impair. Or la somme des degrés doit être paire (elle vaut 2 × nombre d'arêtes). C'est impossible : un tel graphe n'existe pas.
    Autre justification : les 7 sommets seraient tous de degré impair (3), ce qui ferait 7 sommets de degré impair, un nombre impair, alors qu'il doit être pair.

  2. 2

    On considère un graphe à 4 sommets A, B, C, D dont les seules arêtes sont A−BA-B et C−DC-D.
    a) Écrire la matrice d'adjacence M.
    b) Le graphe est-il connexe ? Justifier en s'appuyant sur les chaînes.

    Voir le corrigéoffert

    a) A est relié uniquement à B, et C uniquement à D. Aucune arête ne relie {A, B} à {C, D}.
    M = (0100100000010010)\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}
    b) Le graphe n'est pas connexe. Un graphe est connexe si deux sommets quelconques peuvent toujours être reliés par une chaîne. Or il n'existe aucune chaîne reliant A à C : depuis A on ne peut atteindre que B(via A−B)B (\text{via } A-B), et jamais C ni D.
    Le graphe est formé de deux composantes connexes distinctes : {A, B} et {C, D}. On le voit aussi sur la matrice, dont les coefficients reliant les deux blocs sont tous nuls.

    8 corrigés détaillés pas à pas restent à débloquer

    Chacun reprend l'énoncé, montre le calcul étape par étape et dit où se trouve le piège.

    Le pack de révision, gratuit

    L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.

    Si tu as moins de 15 ans, demande à un parent de remplir ce formulaire avec son adresse.

  3. 3

    On considère le graphe complet à 4 sommets 1, 2, 3, 4 (chaque sommet est relié à tous les autres), de matrice d'adjacence M dont tous les coefficients hors diagonale valent 1 et la diagonale est nulle.
    a) Combien y a-t-il de chaînes de longueur 2 reliant deux sommets distincts, par exemple 1 et 2 ?
    b) Combien y a-t-il de chaînes de longueur 2 reliant un sommet à lui-même, par exemple 1 à 1 ?

    🔒 Corrigé détailléVoir ce qu'il contient →
  4. 4

    On considère le graphe non orienté à 4 sommets A, B, C, D dont les arêtes sont A−BA-B, B−CB-C, C−DC-D et B−DB-D.
    a) Écrire la matrice d'adjacence M (ordre A, B, C, D).
    b) Calculer M2M^{2}.
    c) Combien y a-t-il de chaînes de longueur 2 partant de B et revenant à B ? Combien de chaînes de longueur 2 relient A à D ?

    🔒 Corrigé détailléVoir ce qu'il contient →
  5. 5

    On considère le graphe « étoile » à 5 sommets : le sommet A est relié à B, C, D et E, et il n'y a aucune autre arête.
    a) Écrire la matrice d'adjacence M (ordre A, B, C, D, E).
    b) Calculer M2M^{2}.
    c) Combien y a-t-il de chaînes de longueur 2 entre B et C ? entre A et A ? entre A et B ? Interpréter le dernier résultat.

    🔒 Corrigé détailléVoir ce qu'il contient →
  6. 6

    On considère le graphe orienté à 3 sommets 1, 2, 3 dont les arcs sont 1→21\to 2, 1→31\to 3, 2→32\to 3 et 3→13\to 1.
    a) Écrire la matrice d'adjacence M.
    b) Calculer M2M^{2}.
    c) Combien y a-t-il de chemins de longueur 2 allant de 1 à 1 ? de 1 à 3 ? Les lister.
    d) Pourquoi (M2)12=0(M^{2})_{12} = 0 ?

    🔒 Corrigé détailléVoir ce qu'il contient →
  7. 7

    On considère le graphe non orienté « en ligne » à 5 sommets 1, 2, 3, 4, 5 dont les arêtes sont 1−21-2, 2−32-3, 3−43-4 et 4−54-5.
    a) Écrire la matrice d'adjacence M.
    b) Calculer M2M^{2}.
    c) Combien y a-t-il de chaînes de longueur 2 de 1 à 3 ? de 1 à 5 ? Justifier le second résultat sans calcul.

    🔒 Corrigé détailléVoir ce qu'il contient →
  8. 8

    Un réseau d'amitiés relie 5 personnes A, B, C, D, E. Les amitiés (réciproques) sont : A−BA-B, A−CA-C, B−CB-C, B−DB-D, C−DC-D et D−ED-E.
    a) Écrire la matrice d'adjacence M et donner le nombre d'amis de chacun.
    b) Calculer M2M^{2}.
    c) Combien A et D ont-ils d'amis communs ? Et A et E ?

    PersonneABCDENombre d'amis?????on compte les amitiés qui aboutissent à chaque personne
    🔒 Corrigé détailléVoir ce qu'il contient →
  9. 9

    On considère le graphe non orienté à 4 sommets A, B, C, D dont les arêtes sont A−BA-B, B−CB-C et C−DC-D.
    a) Écrire M puis calculer M2M^{2}.
    b) Calculer M3=M2×MM^{3} = M^{2} \times M.
    c) Combien y a-t-il de chaînes de longueur 3 de A à D ? de A à B ? Les lister.

    🔒 Corrigé détailléVoir ce qu'il contient →
  10. 10

    Un réseau informatique relie 5 machines 1, 2, 3, 4, 5 par les câbles 1−21-2, 1−31-3, 2−32-3 et 4−54-5.
    a) Écrire la matrice d'adjacence M.
    b) Calculer M2M^{2} et M3M^{3}.
    c) La machine 1 peut-elle communiquer avec la machine 4 ? Que peut-on dire du réseau ?

    🔒 Corrigé détailléVoir ce qu'il contient →

Comment ça s'est passé ?

Retrouve tout dans Mon suivi.

Le pack de révision, gratuit

L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.

Si tu as moins de 15 ans, demande à un parent de remplir ce formulaire avec son adresse.

Partager avec ma classe

Les énoncés de cette page sont gratuits et s'ouvrent sans compte : l'adresse peut être donnée telle quelle, au tableau ou dans l'espace numérique de travail.