En MP2I, graphes et dénombrement se rejoignent sur une méthode : compter la même chose de deux façons. Sept personnes peuvent-elles avoir chacune exactement trois amis dans leur groupe ? Non : chaque amitié relie deux personnes, donc le total des nombres d'amis vaut deux fois le nombre d'amitiés, un nombre pair, alors que $7 \times 3 = 21$ est impair.
Le vocabulaire des graphes
Définition : un graphe $G = (S, A)$ est formé d'un ensemble fini $S$ de sommets et d'un ensemble $A$ de liens entre eux. Dans un graphe non orienté, un lien est une arête, une paire $\{x, y\}$ sans sens de parcours. Dans un graphe orienté, c'est un arc, un couple $(x, y)$ qui va de $x$ vers $y$.
C'est la notation du programme d'informatique ; les livres en anglais écrivent $G = (V, E)$. Une boucle relie un sommet à lui-même : les graphes de cette page n'en ont pas. Quant aux arcs multiples, le programme ne les évoque pas.
Le degré $d(s)$ d'un sommet $s$ est le nombre d'arêtes qui le touchent. En orienté, on distingue $d_+(s)$, le nombre d'arcs qui partent de $s$, et $d_-(s)$, le nombre d'arcs qui y arrivent.
Un chemin est une suite de sommets dont deux consécutifs sont reliés ; sa longueur est son nombre d'arêtes ou d'arcs. Un graphe non orienté est connexe si deux sommets quelconques sont toujours reliés par un chemin. Un arbre est un graphe connexe acyclique, c'est-à-dire sans cycle : aucun chemin d'au moins une arête ne revient à son départ sans réemprunter une arête.
Le lemme des poignées de main
Propriété : dans un graphe non orienté sans boucle $G = (S, A)$,
$$\sum_{s \in S} d(s) = 2\,|A|$$
Par conséquent, le nombre de sommets de degré impair est pair.
Compte les couples $(s, a)$ où le sommet $s$ est une extrémité de l'arête $a$. Sommet par sommet, il y en a $d(s)$ pour chaque $s$, donc $\sum_{s \in S} d(s)$ en tout. Arête par arête, il y en a exactement 2 pour chaque arête, donc $2|A|$. Enfin, une somme paire contient forcément un nombre pair de termes impairs.
C'est le double comptage : un même ensemble, compté de deux façons, donne deux expressions égales. En orienté, chaque arc a un départ et une arrivée, et le même raisonnement donne $\sum_{s \in S} d_+(s) = \sum_{s \in S} d_-(s) = |A|$.
Ce lemme mesure aussi le coût d'un parcours. Avec des listes d'adjacence, où chaque sommet $s$ a la liste de ses $d(s)$ voisins, lire chaque liste une fois revient à traiter $2|A|$ voisins, ou $|A|$ en orienté : d'où une complexité en $O(|S| + |A|)$. Avec une matrice d'adjacence, un tableau de $|S|$ lignes et $|S|$ colonnes détaillé plus bas, on lit une ligne entière par sommet, soit $O(|S|^2)$.
Les formules de dénombrement
Avant toute formule, pose deux questions : l'ordre compte-t-il, et un même élément peut-il revenir ? Les réponses te placent dans le tableau, pour un ensemble $E$ à $n$ éléments.
| Ce que tu comptes | Ordre | Répétition | Nombre |
|---|---|---|---|
| $p$-listes d'éléments de $E$ | oui | oui | $n^p$ |
| $p$-listes d'éléments distincts, $p \leqslant n$ | oui | non | $\dfrac{n!}{(n-p)!}$ |
| permutations de $E$ (cas $p = n$) | oui | non | $n!$ |
| parties à $p$ éléments | non | non | $\dbinom{n}{p} = \dfrac{n!}{p!\,(n-p)!}$ |
| toutes les parties | non | non | $2^n$ |
Beaucoup de livres appellent arrangements les $p$-listes d'éléments distincts et les notent $A_n^p$ ; tu croiseras aussi $C_n^p$ pour $\dbinom{n}{p}$. Le programme de mathématiques écrit $\dbinom{n}{p}$, nul quand $p > n$. Pour la réunion de deux ensembles, retiens $|X \cup Y| = |X| + |Y| - |X \cap Y|$ ; la formule du crible, qui généralise à plus de deux ensembles, est hors programme.
Le programme demande sa preuve combinatoire : $\dbinom{n}{p} = \dbinom{n-1}{p-1} + \dbinom{n-1}{p}$ pour $1 \leqslant p \leqslant n$. Fixe un élément $x$ de $E$. Une partie à $p$ éléments contient $x$, et ses $p - 1$ autres éléments se choisissent parmi les $n - 1$ restants, ou bien ne contient pas $x$, et ses $p$ éléments se choisissent parmi ces mêmes $n - 1$. Les deux cas ne se recouvrent pas : on additionne.
Compter les arêtes et les graphes
Une arête est une partie à 2 éléments de $S$. Avec $n$ sommets, un graphe non orienté a donc au plus $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ arêtes, et le graphe complet, où tous les sommets sont reliés deux à deux, les a toutes. Un arc est un couple de sommets distincts : au plus $n(n-1)$ arcs.
Construire un graphe sur un ensemble fixé de $n$ sommets, c'est décider pour chacune des $\dbinom{n}{2}$ arêtes possibles si elle est présente ou non. Il y a donc $2^{\binom{n}{2}}$ graphes non orientés sur ces sommets : 8 pour 3 sommets, déjà $2^{45}$ pour 10.
Piège classique : compter des couples quand l'objet est une paire. Dans un groupe de 10 personnes où chacun serre la main de tous les autres, $10 \times 9 = 90$ compte chaque poignée de main deux fois, une fois par main. La bonne réponse est $\dbinom{10}{2} = 45$. Avant de conclure, demande-toi si « $x$ avec $y$ » et « $y$ avec $x$ » sont le même objet : si oui, tu comptes des paires.
Compter les chemins avec la matrice d'adjacence
Numérote les sommets de 1 à $n$. La matrice d'adjacence $M$ est la matrice carrée de taille $n$ dont le coefficient $m_{ij}$ vaut 1 s'il y a un arc de $i$ vers $j$, et 0 sinon. En non orienté, chaque arête compte dans les deux sens et $M$ est symétrique.
Propriété : pour tout entier $k \geqslant 1$, le coefficient $(M^k)_{ij}$ est le nombre de chemins de longueur $k$ qui vont de $i$ à $j$, un même sommet pouvant revenir plusieurs fois.
Par récurrence sur $k$. Pour $k = 1$, c'est la définition de $M$. Un chemin de longueur $k + 1$ de $i$ à $j$ est un chemin de longueur $k$ de $i$ à un sommet $l$, suivi de l'arc de $l$ vers $j$. Pour $l$ fixé, il y en a $(M^k)_{il}\, m_{lj}$ ; en sommant sur $l$, on trouve $\sum_{l=1}^{n} (M^k)_{il}\, m_{lj}$, qui est exactement $(M^{k+1})_{ij}$.
Sur les graphes, le programme d'informatique de première année attend ensuite des algorithmes : parcours en largeur et en profondeur, tri topologique, composantes connexes, plus courts chemins par les algorithmes de Dijkstra et de Floyd-Warshall. Kruskal et Kosaraju n'arrivent qu'en MPI, en deuxième année.
Exercices corrigés
Du plus direct au niveau d'un devoir surveillé. Cherche sur ta feuille avant d'ouvrir chaque correction.
Exercice 1 : Un graphe non orienté sans boucle a six sommets, de degrés 4, 3, 3, 2, 2 et 2. Combien a-t-il d'arêtes ? Existe-t-il un graphe non orienté sans boucle à cinq sommets de degrés 3, 3, 3, 2 et 2 ?
Correction :
Par le lemme des poignées de main, $2|A| = 4 + 3 + 3 + 2 + 2 + 2 = 16$, donc le graphe a 8 arêtes.
Pour le second, la somme des degrés vaudrait $3 + 3 + 3 + 2 + 2 = 13$, un nombre impair, alors qu'elle doit valoir $2|A|$. Un tel graphe n'existe pas.
Exercice 2 : Sur un quadrillage, un robot avance à chaque mouvement d'une case vers la droite ou d'une case vers le haut. Combien de trajets différents l'amènent du point $(0\,;0)$ au point $(4\,;3)$ ? Combien d'entre eux passent par le point $(2\,;1)$ ?
Correction :
Les points du quadrillage sont les sommets d'un graphe orienté, les mouvements permis ses arcs. Tout trajet compte 4 pas vers la droite et 3 vers le haut, soit 7 pas, et il est entièrement décrit par les places des 3 pas vers le haut parmi les 7. Il y a donc $\dbinom{7}{3} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ trajets.
Pour passer par $(2\,;1)$, le robot fait d'abord 3 pas dont 1 vers le haut, soit $\dbinom{3}{1} = 3$ débuts possibles, puis 4 pas dont 2 vers le haut, soit $\dbinom{4}{2} = 6$ fins possibles. Chaque début se combine avec chaque fin : $3 \times 6 = 18$ trajets.
Exercice 3 : Combien existe-t-il de graphes non orientés sans boucle sur l'ensemble de sommets $S = \{1, 2, 3, 4\}$ ? Combien d'entre eux ont exactement 3 arêtes ?
Correction :
Les arêtes possibles sont les parties à 2 éléments de $S$ : il y en a $\dbinom{4}{2} = 6$. Le piège consiste à compter les couples de sommets distincts, $4 \times 3 = 12$, alors que les couples $(1, 2)$ et $(2, 1)$ donnent la même arête.
Un graphe correspond à une partie de l'ensemble des 6 arêtes possibles : il y en a $2^6 = 64$. Ceux qui ont exactement 3 arêtes correspondent aux parties à 3 éléments : $\dbinom{6}{3} = 20$ graphes.
Exercice 4 : Un graphe orienté a pour sommets 1, 2 et 3, et pour arcs $1 \to 2$, $1 \to 3$, $2 \to 3$ et $3 \to 1$. Écris sa matrice d'adjacence $M$, calcule $M^2$ et $M^3$, puis donne le nombre de chemins de longueur 3 qui partent du sommet 1. Vérifie en les écrivant.
Correction :
$$M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$ $$M^2 = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}$$ $$M^3 = M^2 M = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}$$
Par exemple, $(M^2)_{11} = 0 \times 0 + 1 \times 0 + 1 \times 1 = 1$ : le seul chemin de longueur 2 de 1 à 1 est $1 \to 3 \to 1$.
Les chemins de longueur 3 issus de 1 se lisent sur la première ligne de $M^3$ : $1 + 1 + 1 = 3$ chemins, un vers chaque sommet. Ce sont $1 \to 2 \to 3 \to 1$, $1 \to 3 \to 1 \to 2$ et $1 \to 3 \to 1 \to 3$.
À retenir
À retenir :
- Double comptage : $\sum_{s \in S} d(s) = 2|A|$, donc un nombre pair de sommets de degré impair.
- Avant une formule de dénombrement : l'ordre compte-t-il, les répétitions sont-elles permises ?
- Une arête est une paire : au plus $\dbinom{n}{2}$ arêtes, et $2^{\binom{n}{2}}$ graphes sur $n$ sommets fixés.
- $(M^k)_{ij}$ compte les chemins de longueur $k$ de $i$ à $j$.
- Formule du crible hors programme : seulement $|X \cup Y| = |X| + |Y| - |X \cap Y|$.
Sources
- Programme d'informatique des voies MP2I et MPI, ministère de l'Enseignement supérieur, 2021, parties 3.4 et 4.5 : texte sur education.gouv.fr.
- Programme de mathématiques des voies MPSI et MP2I, même ministère, 2021, partie « Dénombrement » : texte sur education.gouv.fr.