Kala te souhaite la bienvenueKalaMaths

Graphes et matrice d'adjacence

🟢 Facile

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

    On considère le graphe non orienté à 5 sommets A, B, C, D, E dont les arêtes sont A−BA-B, B−CB-C, C−DC-D, D−ED-E et E−AE-A.
    a) Quelle est la longueur de la chaîne A−B−C−DA-B-C-D ?
    b) La suite de sommets A−B−C−D−E−AA-B-C-D-E-A est-elle un cycle ? Quelle est sa longueur ?

    Voir le corrigéoffert

    Rappel : la longueur d'une chaîne est le nombre d'arêtes empruntées (et non le nombre de sommets).
    a) La chaîne A−B−C−DA-B-C-D emprunte les arêtes A−BA-B, B−CB-C et C−DC-D, soit 3 arêtes. Sa longueur est donc 3 (même si elle contient 4 sommets).
    b) A−B−C−D−E−AA-B-C-D-E-A part de A et y revient sans réemprunter deux fois la même arête (on utilise A−BA-B, B−CB-C, C−DC-D, D−ED-E puis E−AE-A) : c'est bien un cycle. Il emprunte 5 arêtes, sa longueur est donc 5.

  2. 2

    Peut-il exister un graphe dont les degrés des sommets sont 1, 2, 3, 4 et 5 ? Justifier de deux façons différentes.

    Voir le corrigéoffert

    Calculons la somme des degrés : 1+2+3+4+5=151+2+3+4+5 = 15.
    Argument 1 : d'après le lemme des poignées de main, la somme des degrés vaut deux fois le nombre d'arêtes ; c'est donc un nombre pair. Or 15 est impair : un tel graphe est impossible.
    Argument 2 : les sommets de degré impair sont ceux de degré 1, 3 et 5, soit 3 sommets, ce qui est un nombre impair. Or le nombre de sommets de degré impair doit toujours être pair. C'est donc impossible.
    Conclusion : un tel graphe n'existe pas.

    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

    Un graphe non orienté possède 6 sommets dont les degrés sont 1, 2, 2, 3, 3 et 5.
    a) Combien d'arêtes possède ce graphe ?
    b) Vérifier la propriété portant sur le nombre de sommets de degré impair.

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

    Voici la matrice d'adjacence d'un graphe dont les sommets sont A, B, C, D (dans cet ordre) :
    M = (0110101111000100)\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}
    a) Le graphe est-il orienté ?
    b) Quel est le degré de B ?
    c) Combien le graphe a-t-il d'arêtes ?

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

    Écrire la matrice d'adjacence M du graphe non orienté à 4 sommets numérotés 1, 2, 3, 4 dont les arêtes sont 1−21-2, 2−32-3, 3−43-4 et 4−14-1.

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

    Un graphe non orienté a pour sommets A, B, C, D et pour arêtes A−BA-B, A−CA-C, B−CB-C et C−DC-D. Sa matrice d'adjacence M et son carré valent :
    M = (0110101011010010)\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}
    M2M^{2} = (2111121111301101)\begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix}
    Sans refaire de calcul, répondre.
    a) Combien y a-t-il de chaînes de longueur 2 allant de A à D ?
    b) Combien y a-t-il de chaînes de longueur 2 partant de C et revenant en C ?
    c) Expliquer pourquoi (M2)CD=0(M^{2})_{CD} = 0.

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

    On considère le graphe non orienté d'ordre 5 dont les sommets sont A, B, C, D, E et les arêtes A−BA-B, A−CA-C, B−CB-C, C−DC-D, D−ED-E.
    a) Donner l'ordre du graphe.
    b) Donner le degré de chaque sommet.
    c) Ce graphe est-il connexe ?

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

    Un réseau routier relie 6 villes A, B, C, D, E, F. Les routes (sans sens de circulation) sont : A−BA-B, A−CA-C, B−CB-C, B−DB-D, C−EC-E, D−ED-E et E−FE-F.
    a) Donner l'ordre du graphe et son nombre d'arêtes.
    b) Donner le degré de chaque ville et vérifier le lemme des poignées de main.
    c) Quelles villes sont les mieux desservies ? Le réseau est-il connexe ?

    VilleABCDEFDegré??????une colonne par ville : on compte les routes qui yaboutissent
    🔒 Corrigé détailléVoir ce qu'il contient →
  9. 9

    Soit le graphe non orienté « triangle » à 3 sommets 1, 2, 3 tous reliés deux à deux, de matrice d'adjacence
    M = (011101110)\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}
    a) Calculer M2M^{2}.
    b) Combien y a-t-il de chaînes de longueur 2 reliant le sommet 1 à lui-même ? Et du sommet 1 au sommet 2 ?

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

    On considère le graphe orienté à 4 sommets A, B, C, D dont les arcs sont A→BA\to B, A→DA\to D, B→CB\to C, C→AC\to A et D→CD\to C.
    a) Écrire la matrice d'adjacence M (ordre A, B, C, D).
    b) La matrice est-elle symétrique ? Qu'en déduit-on ?
    c) Donner le degré sortant et le degré entrant du sommet C.

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