🎍 Pack Maths Expertes · Terminale

Graphes & Matrices

Vocabulaire des graphes · Connexite · Coloration · Matrices d'adjacence · Operations matricielles · Determinant · Systemes lineaires · 40 exercices et correction.

📚 4 chapitres
✏️ 40 exercices
📄 Imprimable A4
🎯 Niveau BAC Expertes

🕸 Graphes — Vocabulaire et proprietes

Definitions

  • Graphe G=(V,E) : sommets V, aretes E
  • Degre d(v) = nombre d'aretes incidentes
  • Graphe simple = sans boucle ni multi-aretes
  • Chemin = suite de sommets relies sans repetition
  • Cycle = chemin ferme
\( \sum_{v} d(v) = 2|E| \) — Lemme des poignees de mains
Graphe complet Kn : \( \dfrac{n(n-1)}{2} \) aretes

Connexite & Arbres

  • Connexe : chemin entre toute paire de sommets
  • Arbre = graphe connexe sans cycle
  • Arbre a n sommets : exactement n-1 aretes
  • Eulérien : tous les degrés pairs (cycle eulérien)
  • Hamiltonien : passe par chaque sommet une fois

Coloration

  • k-coloration : adjacents de couleurs differentes
  • Nombre chromatique chi(G) = minimum
  • Biparti iff chi(G) ≤ 2 iff pas de cycle impair
  • chi(Kn) = n

Pieges

  • AB ≠ BA pour les matrices
  • Arbre ne signifie pas graphe quelconque sans cycle

    • 📊 Matrices

    Operations

    • (AB)ij = ∑k AikBkj
    • AB ≠ BA en general
    • Identite I : AI = IA = A
    det \(\begin{pmatrix}a & b \\ c & d\end{pmatrix} = ad - bc\)
    A-1 = \(\dfrac{1}{\det A}\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}\) si det A ≠ 0

    Matrice d'adjacence

    • Aij=1 si arete i→j, 0 sinon
    • (An)ij = nb chemins de longueur n de i a j
    • Connexite : (I+A)n-1 tout positif

    Resoudre AX=B

  • Si det(A) ≠ 0 : X = A-1B
  • Methode de Gauss : operations sur les lignes

    • Exemple : K3 (triangle)

    A=[[0,1,1],[1,0,1],[1,1,0]]
    A²=[[2,1,1],[1,2,1],[1,1,2]] : (A²)12=1 chemin de lg 2 entre 1 et 2

    Graphes & Matrices GRAPHES Somme deg = 2|E| Lemme poignees de mains Arbre : n-1 aretes, connexe sans cycle Eulerien : tous deg pairs cycle eulerien iff connexe + pairs MATRICES det(2x2) = ad-bc inverse si det non nul AB ≠ BA non commutatif ! (An)ij = nb chemins lg n matrice d'adjacence COLORATION chi(G) = nb chromatique Biparti iff chi <= 2 SYSTEMES LIN. AX=B : X=A-1B Gauss-Jordan, Cramer DIJKSTRA Plus court chemin Graphes values MathsOtop - Pack Maths Expertes - Graphes et Matrices

    4 series · 10 exercices · BAC Expertes

    Exercice 1Facile
    Un graphe G a 5 sommets et 8 aretes. Quelle est la somme des degres ?
    ~2 lignes
    Exercice 2Facile
    Parmi ces sequences, lesquelles sont realisables : a) (3,3,3,3)   b) (1,2,3,4,5)   c) (2,2,3,3) ?
    ~5 lignes
    Exercice 3Facile
    Un graphe a 6 sommets de degre 3 chacun. Combien d'aretes ?
    ~3 lignes
    Exercice 4Intermediaire
    Montrer que dans tout graphe simple, il existe deux sommets de meme degre.
    ~5 lignes · pigeonhole
    Exercice 5Intermediaire
    Graphe : aretes AB, AC, BC, CD, DE. A-t-il un chemin eulerien ? Un cycle eulerien ?
    ~5 lignes · degres
    Exercice 6Intermediaire
    Calculer le nombre chromatique du cycle C5 (pentagone) et proposer une coloration optimale.
    ~5 lignes
    Exercice 7Intermediaire
    Montrer qu'un arbre a n sommets a exactement n-1 aretes par recurrence.
    ~6 lignes
    Exercice 8Difficile
    Montrer que K3,3 n'est pas planaire (formule d'Euler V-E+F=2, chaque face a au moins 4 cotes).
    ~7 lignes
    Exercice 9Difficile
    Demontrer le lemme des poignees de mains.
    ~5 lignes
    Exercice 10Expert
    Demontrer qu'un graphe est 2-colorable (biparti) ssi il ne contient aucun cycle de longueur impaire.
    ~8 lignes · double implication
    Exercice 1Facile
    Calculer A+B et 3A-B pour A=[[1,2],[3,4]], B=[[5,-1],[0,2]].
    ~4 lignes
    Exercice 2Facile
    Calculer AB et BA pour A=[[1,1],[0,1]], B=[[1,0],[1,1]]. Verifier AB ≠ BA.
    ~5 lignes
    Exercice 3Facile
    Calculer det(A) pour A=[[3,2],[1,4]] et A=[[0,5],[-1,3]].
    ~3 lignes
    Exercice 4Intermediaire
    Calculer l'inverse de A=[[2,3],[1,2]]. Verifier AA⁻¹=I.
    ~5 lignes
    Exercice 5Intermediaire
    Resoudre \(\begin{cases}2x+3y=7\x+2y=4\end{cases}\) par la methode des matrices.
    ~5 lignes
    Exercice 6Intermediaire
    Calculer A², A³ pour A=[[1,1],[0,1]]. Conjecturer Aⁿ et demontrer par recurrence.
    ~7 lignes
    Exercice 7Intermediaire
    Montrer que det(AB) = det(A) x det(B) pour des matrices 2x2.
    ~6 lignes
    Exercice 8Difficile
    Suite : u_{n+1}=2u_n+v_n, v_{n+1}=u_n+v_n, u0=1, v0=0. Ecrire sous forme matricielle et calculer u10, v10.
    ~7 lignes
    Exercice 9Difficile
    Trouver toutes les matrices 2x2 telles que A² = I. Combien y en a-t-il ?
    ~7 lignes
    Exercice 10Expert
    A = [[cos t, -sin t],[sin t, cos t]]. Montrer par recurrence que An = [[cos(nt), -sin(nt)],[sin(nt), cos(nt)]].
    ~8 lignes
    Exercice 1Facile
    Construire la matrice d'adjacence du chemin P3 (1-2-3) et du cycle C4.
    ~4 lignes
    Exercice 2Facile
    Graphe : aretes {1,2} et {2,3}. Calculer A et A². Combien de chemins longueur 2 entre 1 et 3 ?
    ~5 lignes
    Exercice 3Intermediaire
    Pour la matrice d'adjacence de C4, calculer A² et A³. Interpreter les coefficients.
    ~6 lignes
    Exercice 4Intermediaire
    Chaine de Markov : P(A→A)=0.7, P(A→B)=0.3, P(B→A)=0.4, P(B→B)=0.6. Etat apres 2 etapes depuis A.
    ~6 lignes
    Exercice 5Intermediaire
    Trouver la distribution stationnaire pi de la chaine de Markov precedente.
    ~5 lignes
    Exercice 6Intermediaire
    Pour K3 (triangle), calculer A + A² + A³. Que represente la somme des coefficients ?
    ~6 lignes
    Exercice 7Difficile
    Verifier que (I+A)^(n-1) a tous ses coefficients positifs pour un graphe connexe a n=3 sommets.
    ~6 lignes
    Exercice 8Difficile
    Fibonacci matriciel : F_{n+2}=F_{n+1}+F_n. Poser vecteur (F_{n+1},F_n) = A^n (1,1)^T. Trouver A, calculer A² et A³.
    ~7 lignes
    Exercice 9Expert
    Algorithme de Dijkstra : graphe A-F avec AB=3, AC=5, BD=2, BE=4, CD=1, CF=6, DF=3, EF=2. Plus court chemin A vers F.
    ~8 lignes
    Exercice 10Expert
    Valeurs propres de A=[[3,1],[1,3]] : resoudre det(A-lambdaI)=0. En deduire An.
    ~8 lignes · diagonalisation
    Exercice 1 BACBAC Expertes
    (6 pts) Reseau 5 villes A,B,C,D,E. Routes : AB, AC, BC, BD, CD, CE, DE.
    1. Matrice d'adjacence. (2 pts) 2. Chemins longueur 2 de A a D. (2 pts) 3. Graphe eulerien ? Hamiltonien ? (2 pts)
    ~10 lignes
    Exercice 2 BACBAC Expertes
    (5 pts) Resoudre par matrices :
    \(\begin{cases}3x-y+2z=1\x+2y-z=3\2x+y+z=4\end{cases}\)
    1. Ecrire AX=B. (1 pt) 2. Calculer det(A). (2 pts) 3. Resoudre. (2 pts)
    ~10 lignes
    Exercice 3 BACBAC Expertes
    (5 pts) Coloration emploi du temps : 5 matieres, incompatibilites (M1,M2),(M1,M3),(M2,M4),(M3,M4),(M4,M5).
    1. Modele graphe. (1 pt) 2. Nombre chromatique. (2 pts) 3. Planning sur chi(G) jours. (2 pts)
    ~9 lignes
    Exercice 4 BACBAC Expertes
    (4 pts) Lapins et renards : l_{n+1}=1.3l_n-0.2r_n, r_{n+1}=0.1l_n+0.8r_n, l0=100, r0=20.
    1. Forme matricielle. (1 pt) 2. Calculer (l1,r1) et (l2,r2). (2 pts) 3. Stabilite. (1 pt)
    ~8 lignes
    Exercice 5 BACBAC Expertes
    (4 pts) Dijkstra : A vers F. Aretes : AB=3, AC=5, BD=2, BE=4, CD=1, CF=6, DF=3, EF=2.
    ~9 lignes
    Exercice 6Expert
    (4 pts) A=[[0,1],[1,0]]. Calculer An. Interpreter (An)12 pour n pair et impair.
    ~7 lignes
    Exercice 7Expert
    (5 pts) Diagonalisation : A=[[4,1],[2,3]].
    1. Valeurs propres. 2. Vecteurs propres. 3. An par A=PDP⁻¹.
    ~10 lignes
    Exercice 8Expert
    (5 pts) Chaine de Markov 3 etats. T=[[0.5,0.3,0.2],[0.4,0.4,0.2],[0.1,0.3,0.6]]. Distribution stationnaire pi telle que piT=pi.
    ~9 lignes
    Exercice 9Expert
    (3 pts) Tournoi 5 equipes (chacune bat deux autres). Modeliser par un graphe oriente et classer par score de chemins.
    ~8 lignes
    Exercice 10 SyntheseExpert
    (7 pts) Suite de Fibonacci par matrices.
    1. Montrer F_n = (phi^n - psi^n)/sqrt(5) avec phi=(1+sqrt5)/2. 2. Calculer F_10 avec la formule. 3. Generaliser a toute suite lineaire d'ordre 2.
    ~12 lignes
    ~7 lignes
    Exercice 7★★★★
    (3 pts) Démontrer que le graphe de Petersen (10 sommets, 15 arêtes, 3-régulier) a un nombre chromatique χ = 3.
    ~7 lignes
    Exercice 8★★★★
    (5 pts) Chaîne de Markov à 3 états. Matrice de transition T = [[0.5,0.3,0.2],[0.4,0.4,0.2],[0.1,0.3,0.6]]. Trouver la distribution stationnaire π telle que πT = π et π₁+π₂+π₃=1.
    ~9 lignes · système linéaire
    Exercice 9★★★★
    (6 pts) Diagonalisation : A = [[4,1],[2,3]].
    1. Calculer les valeurs propres (det(A-λI)=0). (2 pts)
    2. Trouver les vecteurs propres. (2 pts)
    3. Écrire A = PDP⁻¹ et en déduire Aⁿ. (2 pts)
    ~11 lignes
    Exercice 10 — Synthèse★★★★
    (7 pts) Tournoi de 5 équipes : chaque paire joue une fois, A bat B,C ; B bat C,D ; C bat D,E ; D bat E,A ; E bat A,B.
    1. Modéliser par un graphe orienté et sa matrice. (2 pts)
    2. Calculer A+A² (chemins de longueur 1 ou 2). (2 pts)
    3. Classer les équipes par score. (1 pt)
    4. Ce tournoi a-t-il un vainqueur incontestable ? (2 pts)
    ~11 lignes

    Correction complète

    Ex 1 · Somme des degrés, 5 sommets 8 arêtes
    1Lemme des poignées de mains : somme = 2|E| = 2×8 = 16
    Somme des degrés = 16
    Ex 3 · Graphe 6 sommets, degré 3 partout
    1Somme des degrés = 6×3 = 18 = 2|E| → |E| = 9
    9 arêtes
    Ex 7 · Arbre : n sommets → n-1 arêtes
    Initn=1 : arbre = sommet isolé, 0 arête = 1-1 ✓
    Hér.Si tout arbre à n sommets a n-1 arêtes : prendre arbre à n+1 sommets. Il a une feuille v (degré 1). Supprimer v → arbre à n sommets avec n-1 arêtes. Rajouter v et son arête → n+1 sommets, n arêtes ✓
    Arbre à n sommets ↔ n-1 arêtes
    Ex 4 · Inverse de A = [[2,3],[1,2]]
    1det(A) = 2×2 - 3×1 = 1
    2A⁻¹ = (1/1)×[[2,-3],[-1,2]] = [[2,-3],[-1,2]]
    3Vérif : AA⁻¹ = [[2,3],[1,2]]×[[2,-3],[-1,2]] = [[4-3,-6+6],[2-2,-3+4]] = [[1,0],[0,1]] ✓
    A⁻¹ = [[2,-3],[-1,2]]
    Ex 6 · Aⁿ pour A = [[1,1],[0,1]]
    1A²=[[1,2],[0,1]], A³=[[1,3],[0,1]] → conjecture : Aⁿ=[[1,n],[0,1]]
    2Récurrence : Aⁿ⁺¹=Aⁿ·A=[[1,n],[0,1]]·[[1,1],[0,1]]=[[1,n+1],[0,1]] ✓
    Aⁿ = [[1,n],[0,1]]
    Ex 10 · Valeurs propres de A = [[cos θ, -sin θ],[sin θ, cos θ]]
    1A² = [[cos²θ-sin²θ,-2sinθcosθ],[2sinθcosθ,cos²θ-sin²θ]] = [[cos2θ,-sin2θ],[sin2θ,cos2θ]] (rotation 2θ)
    2Par récurrence : Aⁿ = [[cosnθ,-sinnθ],[sinnθ,cosnθ]] (rotation nθ)
    Aⁿ = matrice de rotation d'angle nθ
    Ex 2 · Matrice d'adjacence, graphe 1-2-3
    1A = [[0,1,0],[1,0,1],[0,1,0]]
    2A² = [[1,0,1],[0,2,0],[1,0,1]] : (A²)₁₃=1 → 1 chemin de longueur 2 entre 1 et 3 (via 2)
    (A²)₁₃ = 1 : chemin 1→2→3
    Ex 5 · Distribution stationnaire : P(A→A)=0,7, P(B→B)=0,6
    1πT = π : 0,7π₁+0,4π₂=π₁ et 0,3π₁+0,6π₂=π₂
    2-0,3π₁+0,4π₂=0 → π₁=4π₂/3. Avec π₁+π₂=1 : 4/3π₂+π₂=1 → π₂=3/7, π₁=4/7
    π = (4/7 ; 3/7) ≈ (0,571 ; 0,429)
    Ex 4 BAC · Lapins et renards
    1Forme matricielle : [[l_{n+1}],[r_{n+1}]] = [[1.3,-0.2],[0.1,0.8]] × [[lₙ],[rₙ]]
    2l₁=1,3×100-0,2×20=130-4=126 · r₁=0,1×100+0,8×20=10+16=26
    3l₂=1,3×126-0,2×26=163,8-5,2=158,6 · r₂=0,1×126+0,8×26=12,6+20,8=33,4
    (l₁,r₁)=(126,26) · (l₂,r₂)≈(158,6;33,4) · Population croît
    Ex 5 BAC · Dijkstra A→F
    1Distances initiales : A=0, B=∞, C=∞, D=∞, E=∞, F=∞
    2Depuis A : B=3, C=5. Choisir B(3) → D=3+2=5, E=3+4=7
    3Depuis C(5) : D=min(5,5+1)=5 → égalité. F=5+6=11
    4Depuis D(5) : F=min(11,5+3)=8
    5Depuis E(7) : F=min(8,7+2)=8 → égalité. Plus court chemin : A→B→D→F = 8
    Plus court chemin A→F = 8 (via B→D→F)
    Carte 1 / 10
    Cliquer pour retourner
    ✅ Su : 0
    🔄 À revoir : 0
    Question
    Chargement...
    Réponse
    👆 Cliquer pour retourner