Graphes et matrices — Résumé de cours

1ère Année Collège — Lumaths.ma

Cours complet

Contenu du cours

Vocabulaire de base : sommets et arêtes

Un graphe $G$ est constitué d'un ensemble de sommets (les points) reliés par des arêtes (les liens). On note souvent $G = (S, A)$ où $S$ est l'ensemble des sommets et $A$ celui des arêtes. Par exemple, un réseau social où chaque personne est un sommet et chaque amitié une arête.

Ordre et degré

L'ordre d'un graphe est son nombre de sommets. Le degré d'un sommet est le nombre d'arêtes qui en partent (une boucle compte pour $2$ ). Théorème des poignées de main : la somme des degrés vaut le double du nombre d'arêtes, donc elle est toujours paire.

Graphe orienté et non orienté

Dans un graphe non orienté, une arête entre $a$ et $b$ se parcourt dans les deux sens. Dans un graphe orienté, les liens sont des arcs munis d'un sens (flèches). On distingue alors le degré entrant et le degré sortant d'un sommet.

Chaîne, cycle et longueur

Une chaîne est une suite d'arêtes consécutives reliant deux sommets ; sa longueur est le nombre d'arêtes qui la composent. Un cycle est une chaîne fermée (même sommet de départ et d'arrivée) ne réutilisant pas la même arête. Dans un graphe orienté, on parle de chemin et de circuit.

Graphe complet et graphe connexe

Un graphe est complet si tous les sommets sont reliés deux à deux : noté $K_{n}$ , il possède $\frac{n ( n - 1 )}{2}$ arêtes. Un graphe est connexe si l'on peut relier n'importe quel couple de sommets par une chaîne (le graphe est « d'un seul tenant »).

Matrice d'adjacence

La matrice d'adjacence $M$ d'un graphe d'ordre $n$ (sommets numérotés) est la matrice carrée $n \times n$ où le coefficient $m_{ij}$ vaut le nombre d'arêtes reliant le sommet $i$ au sommet $j$ . Pour un graphe non orienté, $M$ est symétrique : $M = M^{⊤}$ .

Nombre de chemins via $M^{k}$

Résultat fondamental : le coefficient situé ligne $i$ , colonne $j$ de la matrice $M^{k}$ donne le nombre de chemins de longueur exactement $k$ allant du sommet $i$ au sommet $j$ . Ainsi $M^{2}$ compte les chemins en deux étapes, $M^{3}$ ceux en trois étapes, etc.

Graphe pondéré

Un graphe pondéré associe à chaque arête un poids (distance, coût, durée, probabilité…). On peut alors chercher la chaîne de poids minimal, ce qui modélise par exemple le plus court trajet dans un réseau routier.

Chaînes de Markov : matrice de transition

Une chaîne de Markov décrit un système évoluant entre plusieurs états à chaque étape, où le futur ne dépend que de l'état présent. On la représente par un graphe pondéré probabiliste et par une matrice de transition $T$ , où $t_{ij}$ est la probabilité de passer de l'état $i$ à l'état $j$ . La somme des coefficients de chaque ligne vaut $1$ : $T$ est stochastique.

État probabiliste et évolution

L'état probabiliste à l'étape $n$ est une matrice ligne $P_{n} = (p_{1} p_{2} \dots p_{k})$ donnant la probabilité d'occuper chaque état (somme $= 1$ ). On passe d'une étape à la suivante par $P_{n + 1} = P_{n} \times T$ , d'où $P_{n} = P_{0} \times T^{n}$ .

État stable

L'état stable (ou état stationnaire) est un état probabiliste $P$ qui n'évolue plus : $P \times T = P$ . Sous de bonnes hypothèses (matrice régulière), la suite $(P_{n})$ converge vers cet état stable, indépendamment de l'état initial $P_{0}$ .

Applications

Les graphes et matrices modélisent les réseaux (transport, internet, social), les files d'attente, la fidélité client, le PageRank de Google, la météo, la génétique ou encore l'évolution de parts de marché entre concurrents.

✍️ Exemples résolus & démonstrations

Exemple 1 — Matrice d'adjacence et nombre de chemins par $M^{k}$

Énoncé. On considère un graphe orienté à $3$ sommets $A$ , $B$ , $C$ dont les arcs sont : $A \to B$ , $B \to C$ , $C \to A$ et $A \to C$ . (a) Donner la matrice d'adjacence $M$ (lignes et colonnes rangées dans l'ordre $A$ , $B$ , $C$ ). (b) Déterminer le nombre de chemins de longueur $2$ allant de $A$ à $C$ . (c) Déterminer le nombre de chemins de longueur $3$ allant de $A$ à $A$ .

Solution.

(a) Le coefficient situé ligne $i$ , colonne $j$ vaut $1$ s'il existe un arc du sommet $i$ vers le sommet $j$ , et $0$ sinon. Depuis $A$ : arcs vers $B$ et vers $C$ . Depuis $B$ : arc vers $C$ . Depuis $C$ : arc vers $A$ . D'où $M = 001100110 .$
(b) Le coefficient ligne $i$ , colonne $j$ de $M^{k}$ donne le nombre de chemins de longueur exactement $k$ du sommet $i$ vers le sommet $j$ . On calcule donc $M^{2} = M \times M$ . $M^{2} = 001100110001100110 = 110001101 .$ Le nombre de chemins de longueur $2$ de $A$ vers $C$ se lit ligne $A$ , colonne $C$ , soit $1$ . (Il s'agit du chemin $A \to B \to C$ .)
(c) On calcule $M^{3} = M^{2} \times M$ . $M^{3} = 110001101001100110 = 101110111 .$ Le nombre de chemins de longueur $3$ de $A$ vers $A$ se lit ligne $A$ , colonne $A$ , soit $1$ . (Il s'agit du chemin $A \to B \to C \to A$ .)
Vérification. Recensons à la main les chemins de longueur $3$ partant de $A$ : $A \to B \to C \to A$ , $A \to C \to A \to B$ , $A \to C \to A \to C$ . Cela donne bien $1$ retour en $A$ , et la ligne $A$ de $M^{3}$ est $(111)$ , conforme aux trois chemins listés. ✓

Exemple 2 — Chaîne de Markov : état après $n$ étapes

Énoncé. Un usager dispose chaque jour de deux applications de transport, $X$ et $Y$ . S'il utilise $X$ un jour, il réutilise $X$ le lendemain avec probabilité $0, 8$ et passe à $Y$ avec probabilité $0, 2$ . S'il utilise $Y$ , il y reste avec probabilité $0, 7$ et revient à $X$ avec probabilité $0, 3$ . Au jour $0$ , il utilise $X$ . On note $P_{n} = (x_{n} y_{n})$ la matrice ligne des probabilités d'utiliser $X$ puis $Y$ au jour $n$ . (a) Donner la matrice de transition $T$ . (b) Calculer $P_{1}$ et $P_{2}$ .

Solution.

(a) On range les états dans l'ordre $X$ , $Y$ . La ligne $i$ contient les probabilités de transition depuis l'état $i$ : depuis $X$ , on a $0, 8$ vers $X$ et $0, 2$ vers $Y$ ; depuis $Y$ , on a $0, 3$ vers $X$ et $0, 7$ vers $Y$ . $T = (0, 8 0, 3 0, 2 0, 7) .$ On vérifie que la somme de chaque ligne vaut $1$ : $0, 8 + 0, 2 = 1$ et $0, 3 + 0, 7 = 1$ . ✓
L'état initial est $P_{0} = (10)$ (certitude d'utiliser $X$ au jour $0$ ). La relation d'évolution est $P_{n + 1} = P_{n} T$ .
(b) Calcul de $P_{1} = P_{0} T$ : $P_{1} = (10) (0, 8 0, 3 0, 2 0, 7) = (0, 8 0, 2) .$
Calcul de $P_{2} = P_{1} T$ : $P_{2} = (0, 8 0, 2) (0, 8 0, 3 0, 2 0, 7) = (0, 8 \times 0, 8 + 0, 2 \times 0, 3 0, 8 \times 0, 2 + 0, 2 \times 0, 7) .$ On obtient $P_{2} = (0, 64 + 0, 06 0, 16 + 0, 14) = (0, 70 0, 30) .$
Vérification. À chaque étape, la somme des coefficients doit rester égale à $1$ : pour $P_{2}$ , on a $0, 70 + 0, 30 = 1$ . ✓ La probabilité d'utiliser $X$ décroît de $1$ vers $0, 8$ puis $0, 7$ : elle se rapproche progressivement de l'état stable, cohérent avec l'exemple suivant.

Exemple 3 — État stable d'une chaîne de Markov

Énoncé. On reprend la matrice de transition de l'exemple précédent, $T = (0, 8 0, 3 0, 2 0, 7)$ . Déterminer l'état stable $π = (a b)$ , c'est-à-dire la distribution de probabilité vérifiant $π T = π$ et $a + b = 1$ . Interpréter.

Solution.

L'état stable $π = (a b)$ est invariant : il vérifie $π T = π$ . On écrit le produit matriciel : $(a b) (0, 8 0, 3 0, 2 0, 7) = (0, 8 a + 0, 3 b 0, 2 a + 0, 7 b) .$
L'égalité $π T = π$ fournit le système ${0, 8 a + 0, 3 b 0, 2 a + 0, 7 b = a = b$ La première équation donne $0, 3 b = 0, 2 a$ , soit $0, 2 a - 0, 3 b = 0$ . (La seconde équation est équivalente : $0, 2 a - 0, 3 b = 0$ .)
On ajoute la contrainte de probabilité $a + b = 1$ , donc $a = 1 - b$ . En remplaçant : $0, 2 (1 - b) - 0, 3 b = 0 ⟺ 0, 2 - 0, 5 b = 0 ⟺ b = 0, 4.$
On en déduit $a = 1 - 0, 4 = 0, 6$ . L'état stable est donc $π = (0, 6 0, 4) .$
Vérification. On calcule $π T$ : $(0, 6 0, 4) (0, 8 0, 3 0, 2 0, 7) = (0, 48 + 0, 12 0, 12 + 0, 28) = (0, 6 0, 4) = π .$ ✓ Interprétation. À long terme, l'usager utilise l'application $X$ environ $60 %$ des jours et $Y$ environ $40 %$ des jours, indépendamment de son choix initial. Les valeurs $P_{1} = (0, 80, 2)$ et $P_{2} = (0, 700, 30)$ de l'exemple précédent convergent bien vers $(0, 60, 4)$ . ✓

🔑 Formules clés à retenir

Théorème des poignées de main : $i \sum de g (s_{i}) = 2 a$ , où $a$ est le nombre d'arêtes.
Nombre d'arêtes d'un graphe complet $K_{n}$ : $\frac{n ( n - 1 )}{2}$ .
Matrice d'adjacence non orientée : $M = M^{⊤}$ (symétrique).
Nombre de chemins de longueur $k$ de $i$ vers $j$ : coefficient $(M^{k})_{ij}$ .
Matrice stochastique : chaque ligne de $T$ vérifie $j \sum t_{ij} = 1$ .
Évolution d'un état : $P_{n + 1} = P_{n} \times T$ , donc $P_{n} = P_{0} \times T^{n}$ .
État stable : $P$ tel que $P \times T = P$ avec $i \sum p_{i} = 1$ .
Exemple de matrice de transition à 2 états : $T = (0, 8 0, 3 0, 2 0, 7)$ (chaque ligne somme à $1$ ).

⚠️

Astuces & Pièges à éviter

Les erreurs classiques — à lire avant les exercices !

Ordre du produit : dans une chaîne de Markov, l'état est une matrice ligne et le produit s'écrit $P \times T$ (état à gauche). Inverser en $T \times P$ est l'erreur la plus fréquente et n'a même pas de sens dimensionnel.
$M^{k}$ , pas $k M$ : pour compter des chemins de longueur $k$ , on prend la puissance $M^{k}$ , jamais le produit par le scalaire $k$ .
Lignes contre colonnes : la convention « la somme des lignes vaut $1$ » impose le produit $P \times T$ . Si un énoncé utilise la convention colonnes, le produit devient $T \times P$ avec $P$ en colonne : toujours vérifier la convention.
Boucle = degré $+ 2$ : une boucle (arête d'un sommet vers lui-même) ajoute $2$ au degré, et se code par un coefficient sur la diagonale de $M$ .
Symétrie : une matrice d'adjacence non symétrique trahit un graphe orienté (ou une erreur de recopie). Vérifiez toujours $M = M^{⊤}$ pour le non orienté.
Normalisation oubliée : pour l'état stable, le système $P \times T = P$ seul est indéterminé (il donne une infinité de solutions proportionnelles). L'équation $\sum p_{i} = 1$ est indispensable.
Convergence non garantie : la suite $(P_{n})$ ne converge vers l'état stable que si la matrice est régulière (une puissance de $T$ à coefficients tous strictement positifs). Une chaîne périodique peut ne pas converger.
Chemin contre chaîne : ne confondez pas « chaîne » (graphe non orienté) et « chemin » (graphe orienté), ni « cycle » et « circuit ». Le vocabulaire est attendu précisément à l'examen.

Graphes et matrices — Fiche d'exercices

1ère Année Collège — Lumaths.ma | Écris tes réponses dans les espaces prévus

Exercices interactifs

66 exercices • Lis l'énoncé, écris ta réponse, puis vérifie la correction

Ma progression 0 / 66 corrigés

Exercices Faciles

20 exercices

Degrés des sommets et théorème des poignées de mains

Facile

Énoncé

Un graphe a 5 sommets $A, B, C, D, E$ et les arêtes ${A, B}, {A, C}, {B, C}, {B, D}, {C, E}, {D, E}$ .

Calculer le degré de chaque sommet.
Vérifier $i \sum de g (i) = 2∣ E ∣$ .
Combien de sommets ont un degré impair ?

Ma réponse

Graphes et matrices

Graphes et matrices — Résumé de cours

Cours complet

Contenu du cours

Vocabulaire de base : sommets et arêtes

Ordre et degré

Graphe orienté et non orienté

Chaîne, cycle et longueur

Graphe complet et graphe connexe

Matrice d'adjacence

Nombre de chemins via Mk

Graphe pondéré

Chaînes de Markov : matrice de transition

État probabiliste et évolution

État stable

Applications

✍️ Exemples résolus & démonstrations

Exemple 1 — Matrice d'adjacence et nombre de chemins par Mk

Exemple 2 — Chaîne de Markov : état après n étapes

Exemple 3 — État stable d'une chaîne de Markov

🔑 Formules clés à retenir

Astuces & Pièges à éviter

Méthodes types

Graphes et matrices — Fiche d'exercices

Exercices interactifs

Exercices Faciles

Degrés des sommets et théorème des poignées de mains

Matrice d'adjacence et chemins de longueur 2

Graphe orienté — degrés et matrice

Algorithme de Dijkstra — initiation

Algorithme de Dijkstra — Initiation

Arbre couvrant et nombre d'arêtes

Pages web, matrice d'adjacence et chemins de longueur 2

Réseau d'amis : matrice d'adjacence et chemins de longueur 2

Chaîne de Markov — Distribution après deux étapes

Chaîne eulérienne — condition sur les degrés

Circuit hamiltonien sur un graphe complet $K_4$

Coloriage — Nombre chromatique d'un graphe simple

Connexité d'un graphe simple

Degrés et chaîne eulérienne

Degrés et chaîne eulérienne (variante)

Distribution stationnaire — Chaîne à deux états

Réseau d'amis et matrice d'adjacence

Graphe orienté : degrés entrant et sortant

Lecture d'une matrice d'adjacence

Vocabulaire fondamental des graphes

Exercices Intermédiaires

Connexité et composantes connexes

Graphes eulériens — théorème d'Euler

Graphes hamiltoniens

Graphe bipartite et 2-coloration

Nombre chromatique $\chi(G)$

Arbres : propriétés fondamentales

Parcours en largeur (BFS) et distances

Parcours en profondeur (DFS) et détection de cycle

Algorithme glouton de coloration

Graphes complets $K_n$ — propriétés combinatoires

Isomorphisme de graphes

Application : réseau de communication et fiabilité

Coloration de cartes et théorème des 4 couleurs

Algorithme de Dijkstra — réseau routier

Algorithme de Dijkstra — Réseau routier

Algorithme de Kruskal — arbre couvrant minimal

Algorithme de Prim — réseau électrique

Modèle météo : chaîne de Markov à deux états et état stable

Fidélité client : chaîne de Markov à deux états et état stable

Calcul de $A^2$ et nombre de chemins de longueur 2

Chaîne de Markov — Météo à trois états

Cycles et connexité — graphe des couleurs

Identification de cycles et chaînes dans un graphe

Circulation à sens unique : comptage de trajets

Modélisation par graphe — réseau de villes

Puissance de matrice et chemins de longueur 3

Exercices Difficiles

Plus court chemin de A à F dans un graphe à 6 sommets

Arbre couvrant minimal — algorithme de Kruskal

Graphes planaires et formule d'Euler

Dénombrement de chemins par puissances de la matrice d'adjacence

Algorithme de Prim — arbre couvrant minimal

Fermeture transitive

Nombre de chemins via $M^{k}$

Exemple 1 — Matrice d'adjacence et nombre de chemins par $M^{k}$

Exemple 2 — Chaîne de Markov : état après $n$ étapes