Kala te souhaite la bienvenueKalaMaths

Graphes et matrice d'adjacence

🔴 Expert

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) Peut-il exister un graphe d'ordre 5 dont tous les sommets sont de degré 3 ? Justifier.
    b) Peut-il exister un graphe d'ordre 6 dont tous les sommets sont de degré 3 ? Si oui, combien a-t-il d'arêtes ?
    c) Démontrer que, dans tout graphe, le nombre de sommets de degré impair est pair.

    Voir le corrigéoffert

    a) Si un graphe d'ordre 5 avait tous ses sommets de degré 3, la somme des degrés serait 5×3=155 \times 3 = 15, un nombre impair. Or cette somme vaut 2×(nombre d′areˆtes)2 \times (\text{nombre } d'\text{arêtes}), donc elle est paire. Contradiction : un tel graphe n'existe pas.
    b) Pour un graphe d'ordre 6 tout entier de degré 3, la somme des degrés est 6×3=186 \times 3 = 18, nombre pair. Le nombre d'arêtes serait 18÷2=918 \div 2 = 9. Un tel graphe existe (par exemple le prisme triangulaire : deux triangles reliés par trois arêtes, chaque sommet ayant degré 3).
    c) Notons SpS_p la somme des degrés des sommets de degré pair et SiS_i celle des sommets de degré impair. La somme totale des degrés est Sp+Si=2×(nombre d′areˆtes)S_p + S_i = 2 \times (\text{nombre } d'\text{arêtes}), donc elle est paire.
    SpS_p est une somme de nombres pairs : elle est paire. Donc Si=(Sp+Si)−SpS_i = (S_p + S_i) - S_p est paire (différence de deux nombres pairs).
    Or SiS_i est une somme de nombres impairs. Une somme d'entiers impairs est paire si et seulement si le nombre de termes est pair. Donc le nombre de sommets de degré impair est pair. C'est le lemme des poignées de main.

  2. 2

    On reprend le triangle à 3 sommets 1, 2, 3 (tous reliés), de matrice d'adjacence M. Pour un entier n≥0n \ge 0, on note un=(Mn)11u_{n} = (M^{n})_{11} (nombre de chemins de longueur n de 1 à 1) et vn=(Mn)12v_{n} = (M^{n})_{12} (de 1 à 2). Par symétrie, tous les coefficients diagonaux de Mⁿ valent unu_n et tous les autres valent vnv_n.
    a) Justifier que un+1=2vnu_{n+1} = 2 v_{n} et vn+1=un+vnv_{n+1} = u_{n} + v_{n}.
    b) Sachant u0=1u_{0} = 1 et v0=0v_{0} = 0, calculer unu_n et vnv_n pour n allant de 1 à 5.
    c) Montrer que, pour tout n, un+2vn=2nu_{n} + 2 v_{n} = 2^{n}, et interpréter ce nombre.

    Rang n012345uₙ1?????vₙ0?????chaque colonne se déduit de la précédente, pas à pas
    Voir le corrigéoffert

    a) On utilise Mn+1=Mn×MM^{n+1} = M^{n} \times M et la matrice M du triangle (M11M_{11} = 0, M12M_{12} = M13M_{13} = 1, etc.).
    un+1=(Mn+1)11u_{n+1} = (M^{n+1})_{11} = Σ (Mn)1kMk1=(Mn)11×0+(Mn)12×1+(Mn)13×1=vn+vn=2vn(M^{n})_{1k} M_k1 = (M^{n})_{11}\times 0 + (M^{n})_{12}\times 1 + (M^{n})_{13}\times 1 = v_{n} + v_{n} = 2 v_{n}.
    vn+1=(Mn+1)12v_{n+1} = (M^{n+1})_{12} = Σ (Mn)1kMk2=(Mn)11×1+(Mn)12×0+(Mn)13×1=un+vn(M^{n})_{1k} M_k2 = (M^{n})_{11}\times 1 + (M^{n})_{12}\times 0 + (M^{n})_{13}\times 1 = u_{n} + v_{n}.
    b) On applique u0=1u_{0} = 1, v0=0v_{0} = 0 :
    n=1n=1 : u1=2v0=0u_{1} = 2 v_{0} = 0 ; v1=u0+v0=1v_{1} = u_{0} + v_{0} = 1.
    n=2n=2 : u2=2v1=2u_{2} = 2 v_{1} = 2 ; v2=u1+v1=0+1=1v_{2} = u_{1} + v_{1} = 0 + 1 = 1.
    n=3n=3 : u3=2v2=2u_{3} = 2 v_{2} = 2 ; v3=u2+v2=2+1=3v_{3} = u_{2} + v_{2} = 2 + 1 = 3.
    n=4n=4 : u4=2v3=6u_{4} = 2 v_{3} = 6 ; v4=u3+v3=2+3=5v_{4} = u_{3} + v_{3} = 2 + 3 = 5.
    n=5n=5 : u5=2v4=10u_{5} = 2 v_{4} = 10 ; v5=u4+v4=6+5=11v_{5} = u_{4} + v_{4} = 6 + 5 = 11.
    c) Posons wn=un+2vnw_{n} = u_{n} + 2 v_{n}. Alors wn+1=un+1+2vn+1=2vn+2(un+vn)=2un+4vn=2(un+2vn)=2wnw_{n+1} = u_{n+1} + 2 v_{n+1} = 2 v_{n} + 2(u_{n} + v_{n}) = 2 u_{n} + 4 v_{n} = 2 (u_{n} + 2 v_{n}) = 2 w_{n}.
    (wnw_n) est donc géométrique de raison 2, avec w0=u0+2v0=1w_{0} = u_{0} + 2 v_{0} = 1. Donc wn=2nw_{n} = 2^{n}.
    Interprétation : wn=un+2vnw_{n} = u_{n} + 2 v_{n} est le nombre total de chemins de longueur n partant du sommet 1 (vers 1, ou vers 2, ou vers 3, d'où le facteur 2 devant vnv_n). À chaque étape, depuis un sommet on a exactement 2 choix : le nombre total de chemins de longueur n est donc 2ⁿ, ce qui confirme le calcul.
    Vérification pour n=4n=4 : u4+2v4=6+10=16=24u_{4} + 2 v_{4} = 6 + 10 = 16 = 2^{4}. Correct.

    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

    Soit G un graphe (orienté ou non) d'ordre p, de matrice d'adjacence M, et soit k un entier ≥1\ge 1.
    a) Démontrer par récurrence sur k que le coefficient (Mk)ij(Mᵏ)_{ij} est égal au nombre de chemins de longueur k allant du sommet i au sommet j.
    b) Application : pour le triangle 1, 2, 3 (tous les sommets reliés deux à deux), calculer (M3)11(M^{3})_{11} à partir de M2M^{2}, qui vaut 2 sur la diagonale et 1 ailleurs.

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

    Soit KnK_n le graphe complet à n sommets (n≥3)(n \ge 3) : chaque sommet est relié à tous les autres. On note M sa matrice d'adjacence et I la matrice identité de taille n.
    a) Justifier que (M2)ii=n−1(M^{2})_{ii} = n - 1 et que (M2)ij=n−2(M^{2})_{ij} = n - 2 pour i≠ji \ne j.
    b) En déduire que M2=(n−2)M+(n−1)IM^{2} = (n - 2) M + (n - 1) I.
    c) En multipliant par M, exprimer M3M^{3} en fonction de M et I.
    d) Application à K6K_{6} : donner le nombre de chaînes de longueur 3 reliant deux sommets distincts, puis un sommet à lui-même.

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

    On considère le graphe biparti complet K2K_{2},₃ : les sommets X1X_{1}, X2X_{2} d'un côté, Y1Y_{1}, Y2Y_{2}, Y3Y_{3} de l'autre ; chaque XiX_i est relié à chacun des YjY_j, et il n'y a aucune arête à l'intérieur de chaque groupe.
    a) Écrire la matrice d'adjacence M (ordre X1X_{1}, X2X_{2}, Y1Y_{1}, Y2Y_{2}, Y3Y_{3}) et calculer M2M^{2}.
    b) Combien y a-t-il de chaînes de longueur 2 de Y1Y_{1} à Y2Y_{2} ? de X1X_{1} à X1X_{1} ? de X1X_{1} à Y1Y_{1} ?
    c) Montrer que M3=6MM^{3} = 6 M et interpréter le nombre 6.

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

    On considère le carré (cycle à 4 sommets) 1, 2, 3, 4 dont les arêtes sont 1−21-2, 2−32-3, 3−43-4, 4−14-1, de matrice d'adjacence M.
    a) Écrire M puis calculer M2M^{2}.
    b) Combien y a-t-il de chaînes de longueur 2 entre 1 et 3 ?
    c) Calculer M4M^{4} (en utilisant M4=(M2)2M^{4} = (M^{2})^{2}), puis donner le nombre de chaînes de longueur 4 de 1 à 3.
    d) Justifier que le nombre de chaînes de longueur impaire entre 1 et 2 peut être non nul, tandis qu'entre 1 et 3 il est toujours nul.

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

    On considère le graphe non orienté à 5 sommets A, B, C, D, E dont les arêtes sont A−BA-B, A−CA-C, B−CB-C, C−DC-D, C−EC-E et D−ED-E.
    a) Écrire M et calculer M2M^{2}.
    b) Calculer les cinq coefficients diagonaux de M3M^{3}.
    c) On admet que, pour tout sommet i, (M3)ii(M^{3})_{ii} vaut deux fois le nombre de triangles contenant i. Combien le graphe a-t-il de triangles, et lesquels ?

    Kala a une idéeJe remplis case par case !
    SommetABCDEM³ en (i,i)?????Triangles contenant i?????une colonne par sommet : le coefficient, puis le nombre detriangles qui le contiennent
    🔒 Corrigé détailléVoir ce qu'il contient →
  8. 8

    On considère le graphe « étoile » à 5 sommets : le centre A est relié à B, C, D, E, et il n'y a aucune autre arête. Sa matrice d'adjacence est M.
    a) Calculer M2M^{2} puis M3M^{3}.
    b) Montrer que M3=4MM^{3} = 4 M.
    c) En déduire M⁵, puis le nombre de chaînes de longueur 5 reliant B à A.
    d) Généraliser : pour l'étoile à n branches (un centre relié à n sommets), que vaut M3M^{3} ?

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

    On considère le graphe orienté à 4 sommets A, B, C, D dont les arcs sont A→BA\to B, A→CA\to C, B→CB\to C, C→DC\to D et D→AD\to A.
    a) Écrire la matrice d'adjacence M.
    b) Calculer M2M^{2} puis M3M^{3}.
    c) Combien y a-t-il de chemins de longueur 3 de A à A ? Le décrire.
    d) Calculer la ligne A de M+M2+M3M + M^{2} + M^{3} et interpréter le résultat en termes d'accessibilité.

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

    Un réseau aérien relie 5 aéroports A, B, C, D, E. Les vols (à sens unique) sont : A→BA\to B, A→CA\to C, B→DB\to D, C→DC\to D, C→EC\to E, D→ED\to E et E→AE\to A.
    a) Écrire la matrice d'adjacence M.
    b) Calculer M2M^{2} et M3M^{3}.
    c) Combien y a-t-il de trajets de A à E en exactement 3 vols ? Les lister.
    d) En calculant M+M2+M3M + M^{2} + M^{3}, dire si un voyageur partant de A peut atteindre n'importe quel aéroport en 3 vols au plus.

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