Éducation Nationale Française · Terminale Technologie
Thèmes d'étude
I
La méthode de Monte-Carlo
I.1
Estimer une probabilité par simulation
L'aire d'une forme biscornue, le comportement d'un marcheur qui fait un pas à gauche ou à droite au hasard : aucune formule simple ne répond à de telles questions. Certains nombres ne se calculent donc pas mais s'estiment, en répétant un grand nombre de fois une expérience aléatoire et en comptant. C'est ce qu'on appelle une méthode de Monte-Carlo. Ce qu'il faut comprendre est ce que vaut une telle réponse : elle n'est pas fausse, elle est imprécise, et l'imprécision décroît avec le nombre d'essais, comme \(\frac{1}{\sqrt{n}}\).
Définition — Estimer par simulation
Estimer une probabilité par simulation, c'est répéter l'expérience n fois, compter les essais où l'événement s'est produit, et donner la fréquence — ce compte divisé par n — comme estimation. La fréquence est un nombre que l'algorithme calcule ; la probabilité est un nombre qu'il ignore. Rien ne les rend égales : deux exécutions de la même simulation peuvent donner deux fréquences, et l'une d'elles peut tomber exactement sur la probabilité sans que ce soit autre chose que de la chance. Ce qui est vrai, c'est que la fréquence s'approche de la probabilité à mesure que n grandit — s'approche au sens où une grande erreur devient improbable, non au sens où chaque exécution ferait mieux que la précédente — et tout l'art est de savoir de combien, pour combien d'essais. Les essais doivent être indépendants et tirés de la même façon à chaque fois, faute de quoi rien de ce qui suit ne tient. Méthode — Dire ce que vaut une fréquence simulée
- Écrire la simulation : dire ce qu'est un essai et ce qui compte comme succès, le répéter
nfois avec une boucle bornée, et compter les succès. - Vérifier que les essais sont indépendants et tirés de la même façon, faute de quoi le compte ne veut rien dire.
- Diviser par
nà la fin, hors de la boucle, et donner la fréquence comme estimation. - Dire ce qui est estimé, et n'écrire jamais que la fréquence est la probabilité.
- Dire la précision : l'erreur décroît comme \(\frac{1}{\sqrt{n}}\), donc annoncer le nombre d'essais avec la réponse.
Exemple
L'algorithme ci-dessous compte, sur huit lancers d'un dé, ceux qui donnent au moins \(5\), puis donne la fréquence. Les nombres lus sont, dans l'ordre, \(3\), \(6\), \(1\), \(5\), \(2\), \(6\), \(4\), \(5\). L'exécuter à la main et donner les deux valeurs qu'il affiche. c ← 0
Pour k allant de 1 à 8
Lire d
Si d ≥ 5 alors
c ← c + 1
Fin Si
Fin Pour
Afficher c
f ← c ÷ 8
Afficher f| Instruction | \(k\) | \(d\) | \(d \geqslant 5\) | \(c\) | Affichage |
| départ | \(0\) | ||||
| tour 1 | \(1\) | \(3\) | faux | \(0\) | |
| tour 2 | \(2\) | \(6\) | vrai | \(1\) | |
| tour 3 | \(3\) | \(1\) | faux | \(1\) | |
| tour 4 | \(4\) | \(5\) | vrai | \(2\) | |
| tour 5 | \(5\) | \(2\) | faux | \(2\) | |
| tour 6 | \(6\) | \(6\) | vrai | \(3\) | |
| tour 7 | \(7\) | \(4\) | faux | \(3\) | |
| tour 8 | \(8\) | \(5\) | vrai | \(4\) | |
| Afficher \(c\) | \(8\) | \(5\) | \(4\) | \(4\) | |
| \(f \leftarrow c \div 8\), Afficher \(f\) | \(8\) | \(5\) | \(4\) | \(0{,}5\) |
4 puis 0{,}5 : quatre succès sur huit essais, soit une fréquence de \(\frac{1}{2}\). La division est faite après la boucle et non dedans, ce qui est la troisième étape de la Méthode — une fréquence calculée à chaque tour serait une fréquence sur les essais faits jusque-là, un autre nombre. La probabilité d'obtenir au moins \(5\) avec un dé équilibré vaut \(\frac{2}{6}\), soit environ \(0{,}33\) : l'estimation la manque de \(\frac{1}{6}\), soit la moitié de la probabilité elle-même. L'algorithme n'a rien de fautif — huit essais sont simplement beaucoup trop peu, et c'est là tout l'intérêt de l'exemple. Lu dans l'autre sens, il dit quelque chose qu'un élève doit retenir : une fréquence mesurée sur huit essais est compatible avec quantité de probabilités, et y lire une probabilité serait lire un nombre qui n'y est pas. Exemple
Un marcheur part de \(0\) et se déplace d'un pas vers la droite ou vers la gauche à chaque tour, les deux étant également probables et chaque pas indépendant des précédents. L'algorithme ci-dessous donne sa position après huit pas. Les nombres lus sont, dans l'ordre, \(1\), \(-1\), \(1\), \(1\), \(-1\), \(-1\), \(-1\), \(1\). L'exécuter à la main et donner ce qu'il affiche. p ← 0
Pour k allant de 1 à 8
Lire s
p ← p + s
Fin Pour
Afficher p| Instruction | \(k\) | \(s\) | \(p\) | Affichage |
| départ | \(0\) | |||
| tour 1 | \(1\) | \(1\) | \(1\) | |
| tour 2 | \(2\) | \(-1\) | \(0\) | |
| tour 3 | \(3\) | \(1\) | \(1\) | |
| tour 4 | \(4\) | \(1\) | \(2\) | |
| tour 5 | \(5\) | \(-1\) | \(1\) | |
| tour 6 | \(6\) | \(-1\) | \(0\) | |
| tour 7 | \(7\) | \(-1\) | \(-1\) | |
| tour 8 | \(8\) | \(1\) | \(0\) | |
| Afficher \(p\) | \(8\) | \(1\) | \(0\) | \(0\) |
0 : le marcheur est revenu d'où il est parti, ayant fait quatre pas de chaque côté. C'est une marche et elle ne prouve rien des marches en général — un autre tirage pourrait finir ailleurs. Ce que dit une simulation est ce qui arrive en moyenne sur beaucoup de marches, et la réponse mérite d'être sue : le marcheur ne dérive pas, puisque les deux directions sont également probables, mais il ne reste pas non plus sur place. Sa distance typique au départ après n pas croît comme \(\sqrt{n}\) — environ trois positions après dix pas, environ dix après cent. Estimer ce nombre est exactement ce à quoi sert une méthode de Monte-Carlo : répéter la marche un grand nombre de fois et prendre la moyenne des distances, ce qui estime une distance un peu inférieure à \(\sqrt{n}\) ; prendre la moyenne des carrés puis la racine estime \(\sqrt{n}\) lui-même, puisque la moyenne des carrés se fixe sur \(n\). Deux moyennes, deux nombres, et dire lequel on estime fait partie de la réponse. Compétences à pratiquer
- Évaluer ce que vaut une fréquence simulée
- Traduire et exécuter une simulation
I.2
Estimer une aire
Définition — Estimer une aire
Le même comptage estime une aire. Une forme est enfermée dans un carré dont l'aire est connue ; des points y sont tirés uniformément — chaque part du carré aussi probable qu'une autre de même aire, ce qui est ce qui fait marcher l'ensemble — et l'on compte ceux qui tombent dans la forme. La fréquence de ces points estime le rapport des deux aires, donc l'aire de la forme s'estime par cette fréquence multipliée par l'aire du carré. Appliqué au quart de disque de rayon \(1\) dans le carré unité, cela estime \(\frac{\pi}{4}\), et donc \(\pi\) — un nombre qu'aucun calcul fini ne donne exactement, et qu'un comptage de fléchettes approche. Exemple
Six points sont tirés dans le carré de côté \(1\), leurs deux coordonnées comptées en dixièmes pour que tout reste entier ; un point est dans le quart de disque quand la somme des carrés de ses coordonnées ne dépasse pas \(100\). Les nombres lus sont, dans l'ordre, \(2\), \(3\), \(8\), \(9\), \(5\), \(4\), \(9\), \(2\), \(1\), \(9\), \(6\), \(7\). Exécuter l'algorithme à la main et donner ce qu'il affiche. c ← 0
Pour k allant de 1 à 6
Lire x
Lire y
Si x × x + y × y ≤ 100 alors
c ← c + 1
Fin Si
Fin Pour
Afficher c| Instruction | \(k\) | \(x\) | \(y\) | \(x^2 + y^2\) | \(\leqslant 100\) | \(c\) | Affichage |
| départ | \(0\) | ||||||
| tour 1 | \(1\) | \(2\) | \(3\) | \(13\) | vrai | \(1\) | |
| tour 2 | \(2\) | \(8\) | \(9\) | \(145\) | faux | \(1\) | |
| tour 3 | \(3\) | \(5\) | \(4\) | \(41\) | vrai | \(2\) | |
| tour 4 | \(4\) | \(9\) | \(2\) | \(85\) | vrai | \(3\) | |
| tour 5 | \(5\) | \(1\) | \(9\) | \(82\) | vrai | \(4\) | |
| tour 6 | \(6\) | \(6\) | \(7\) | \(85\) | vrai | \(5\) | |
| Afficher \(c\) | \(6\) | \(6\) | \(7\) | \(85\) | \(5\) | \(5\) |
5 : cinq des six points sont dans le quart de disque, donc la fréquence vaut \(\frac{5}{6}\) et l'estimation de \(\pi\) vaut \(4 \times \frac{5}{6}\), soit environ \(3{,}33\). Un point sur six était dehors, et s'il y en avait eu deux l'estimation aurait valu \(2{,}67\) : avec six fléchettes, un point change la réponse de plus d'une demi-unité. Le test compare des entiers parce que les coordonnées sont comptées en dixièmes — un centième d'unité au carré est l'unité de \(x^2 + y^2\), et \(100\) est le carré de dix dixièmes. Écrire le test ainsi évite toute décimale, ce qui est la même astuce qu'écrire k \(\times\) k \(\leqslant\) n plutôt que comparer k à une racine carrée. C'est aussi une simplification : tirer sur une grille de dixièmes n'est pas tirer uniformément dans le carré, si bien que cette trace estime une proportion de points de grille et non exactement \(\frac{\pi}{4}\). Une vraie simulation tire des coordonnées décimales ; la grille est là pour que le tableau se remplisse à la main. Exemple
Huit points sont tirés au hasard dans le carré de sommets \((0\,;\,0)\) et \((1\,;\,1)\), leurs deux coordonnées comptées en dixièmes pour que tout reste entier : chaque coordonnée est un entier de \(0\) à \(10\), tous aussi probables, tirés indépendamment. Un point de coordonnées \(\dfrac{x}{10}\) et \(\dfrac{y}{10}\) est sous la parabole d'équation \(Y = X^2\) lorsque \(\dfrac{y}{10} \leqslant \left(\dfrac{x}{10}\right)^2\), c'est-à-dire lorsque \(10 \times y \leqslant x \times x\). L'algorithme ci-dessous lit \(x\), puis \(y\), pour chaque point. Les nombres lus sont, dans l'ordre, \(7\), \(3\), \(2\), \(5\), \(9\), \(6\), \(4\), \(4\), \(5\), \(1\), \(3\), \(8\), \(8\), \(9\), \(6\), \(4\). L'exécuter à la main et donner les deux valeurs qu'il affiche. c ← 0
Pour k allant de 1 à 8
Lire x
Lire y
Si 10 × y ≤ x × x alors
c ← c + 1
Fin Si
Fin Pour
Afficher c
f ← c ÷ 8
Afficher f| Instruction | \(k\) | \(x\) | \(y\) | \(10y\) | \(x^2\) | \(10y \leqslant x^2\) | \(c\) | Affichage |
| départ | \(0\) | |||||||
| tour 1 | \(1\) | \(7\) | \(3\) | \(30\) | \(49\) | vrai | \(1\) | |
| tour 2 | \(2\) | \(2\) | \(5\) | \(50\) | \(4\) | faux | \(1\) | |
| tour 3 | \(3\) | \(9\) | \(6\) | \(60\) | \(81\) | vrai | \(2\) | |
| tour 4 | \(4\) | \(4\) | \(4\) | \(40\) | \(16\) | faux | \(2\) | |
| tour 5 | \(5\) | \(5\) | \(1\) | \(10\) | \(25\) | vrai | \(3\) | |
| tour 6 | \(6\) | \(3\) | \(8\) | \(80\) | \(9\) | faux | \(3\) | |
| tour 7 | \(7\) | \(8\) | \(9\) | \(90\) | \(64\) | faux | \(3\) | |
| tour 8 | \(8\) | \(6\) | \(4\) | \(40\) | \(36\) | faux | \(3\) | |
| Afficher \(c\) | \(8\) | \(6\) | \(4\) | \(3\) | \(3\) | |||
| \(f \leftarrow c \div 8\), Afficher \(f\) | \(8\) | \(6\) | \(4\) | \(3\) | \(0{,}375\) |
3 puis 0{,}375. Le carré a pour aire \(1\), donc la fréquence est elle-même l'estimation de l'aire sous la parabole — la région comprise entre la courbe, l'axe des abscisses et la droite \(X = 1\). L'aire exacte vaut \(\dfrac{1}{3}\), environ \(0{,}333\), une valeur admise ici. Huit points ne distinguent pas \(0{,}375\) de \(0{,}333\) : un point de plus ou de moins sous la courbe déplace l'estimation de \(\dfrac{1}{8} = 0{,}125\). Le test compare des entiers parce que les coordonnées sont comptées en dixièmes, ce qui évite tout nombre décimal. C'est aussi une simplification : \(45\) des \(121\) points de la grille des dixièmes, de \(0\) à \(1\) dans chaque direction, sont sous la parabole, soit environ \(0{,}372\), donc tirer sur cette grille estime \(0{,}372\) et non \(\dfrac{1}{3}\). Une vraie simulation tire chaque coordonnée comme un nombre décimal entre \(0\) et \(1\), chaque partie de l'intervalle aussi probable que toute autre partie de même longueur, ce qui s'écrit en Python random.random() : import random
def area_under_parabola(n):
c = 0
for k in range(n):
x = random.random()
y = random.random()
if y <= x * x:
c = c + 1
return c / narea_under_parabola(10000) peut donner un nombre différent d'une exécution à l'autre, le plus souvent entre \(0{,}32\) et \(0{,}345\). Compétences à pratiquer
- Estimer une aire par simulation
I.3
Estimer une probabilité conditionnelle
Définition — Estimer une probabilité conditionnelle
Pour estimer par simulation la probabilité d'un événement \(B\) sachant qu'un événement \(A\) de probabilité non nulle s'est produit, on laisse de côté les essais où \(A\) ne s'est pas produit ; les essais sont indépendants et réalisés dans les mêmes conditions. Un algorithme compte, dans une variable \(a\), les essais où \(A\) s'est produit, et, dans une variable \(b\), ceux d'entre eux où \(B\) s'est produit aussi ; la fréquence de \(B\) parmi les essais où \(A\) s'est produit est \(b \div a\). La division se fait par \(a\), et non par le nombre \(n\) d'essais : \(b \div n\) estime la probabilité que \(A\) et \(B\) se produisent tous les deux, un autre nombre. Écrire \(b \div a = \dfrac{b \div n}{a \div n}\) fait apparaître la fréquence de \(A\) et \(B\) divisée par la fréquence de \(A\), la forme de la probabilité conditionnelle \(P_A(B) = \dfrac{P(A \cap B)}{P(A)}\) qu'elle estime. Elle ne peut être calculée que si \(A\) s'est produit au moins une fois, et sa précision est celle des \(a\) essais gardés, pas des \(n\) essais faits : un événement \(A\) qui se produit rarement gaspille la plupart des essais. Exemple
On lance deux dés équilibrés, indépendamment. L'algorithme ci-dessous estime, sur huit lancers, la probabilité que le premier dé donne \(6\) sachant que la somme des deux dés vaut au moins \(10\). À chaque tour, il lit le premier dé, puis le second. Les nombres lus sont, dans l'ordre, \(6\), \(5\), \(3\), \(2\), \(4\), \(6\), \(6\), \(6\), \(1\), \(5\), \(6\), \(4\), \(2\), \(2\), \(5\), \(3\). L'exécuter à la main et donner les deux valeurs qu'il affiche. a ← 0
b ← 0
Pour k allant de 1 à 8
Lire d
Lire e
Si d + e ≥ 10 alors
a ← a + 1
Si d = 6 alors
b ← b + 1
Fin Si
Fin Si
Fin Pour
Afficher a
f ← b ÷ a
Afficher f| Instruction | \(k\) | \(d\) | \(e\) | \(d + e \geqslant 10\) | \(a\) | \(b\) | Affichage |
| départ | \(0\) | \(0\) | |||||
| tour 1 | \(1\) | \(6\) | \(5\) | vrai | \(1\) | \(1\) | |
| tour 2 | \(2\) | \(3\) | \(2\) | faux | \(1\) | \(1\) | |
| tour 3 | \(3\) | \(4\) | \(6\) | vrai | \(2\) | \(1\) | |
| tour 4 | \(4\) | \(6\) | \(6\) | vrai | \(3\) | \(2\) | |
| tour 5 | \(5\) | \(1\) | \(5\) | faux | \(3\) | \(2\) | |
| tour 6 | \(6\) | \(6\) | \(4\) | vrai | \(4\) | \(3\) | |
| tour 7 | \(7\) | \(2\) | \(2\) | faux | \(4\) | \(3\) | |
| tour 8 | \(8\) | \(5\) | \(3\) | faux | \(4\) | \(3\) | |
| Afficher \(a\) | \(8\) | \(5\) | \(3\) | \(4\) | \(3\) | \(4\) | |
| \(f \leftarrow b \div a\), Afficher \(f\) | \(8\) | \(5\) | \(3\) | \(4\) | \(3\) | \(0{,}75\) |
4 puis 0{,}75 : la somme a atteint \(10\) sur quatre lancers, et sur trois d'entre eux le premier dé a donné \(6\). Le test intérieur n'est fait que lorsque le test extérieur est vrai, donc \(b\) ne peut jamais dépasser \(a\). La division se fait par \(a = 4\), les lancers où la condition était remplie, et non par \(8\) : \(3 \div 8 = 0{,}375\) estimerait la probabilité que la somme vaille au moins \(10\) et que le premier dé donne \(6\). La probabilité exacte vaut \(\dfrac{1}{2}\) : six des \(36\) lancers équiprobables donnent une somme d'au moins \(10\), et trois de ces six commencent par un \(6\). Savoir que la somme est grande rend un \(6\) sur le premier dé trois fois plus probable que sans condition, \(\dfrac{1}{6}\). Avec quatre lancers utiles, \(0{,}75\) est loin de \(0{,}5\), et la précision est celle de quatre essais, pas de huit. L'expérience complète, en Python, lance les dés elle-même : import random
def conditional_frequency(n):
a = 0
b = 0
for k in range(n):
d = random.randint(1, 6)
e = random.randint(1, 6)
if d + e >= 10:
a = a + 1
if d == 6:
b = b + 1
return b / aconditional_frequency(10000) peut donner un nombre différent d'une exécution à l'autre, le plus souvent entre \(0{,}47\) et \(0{,}53\) ; seuls environ \(1667\) des \(10000\) lancers sont gardés, un sur six. Si aucun lancer n'atteint \(10\), \(a\) reste à \(0\) et la division par \(0\) arrête le programme sur une erreur ; pour n égal à \(10\), cela arrive environ une exécution sur six, puisque \(\left(\dfrac{5}{6}\right)^{10} \approx 0{,}16\). Compétences à pratiquer
- Estimer une probabilité conditionnelle par simulation
I.4
Précision et nombre d'essais
Définition — Précision et nombre d'essais
Pour des essais indépendants tirés de la même façon, l'erreur typique d'une estimation par simulation décroît comme \(\frac{1}{\sqrt{n}}\) — typique, parce qu'une exécution donnée peut être plus ou moins chanceuse que cela, et qu'aucune ne porte de garantie. Pour diviser par \(10\) cette erreur typique, il faut multiplier le nombre d'essais par \(100\). Cent essais donnent environ une décimale juste, dix mille en donnent deux, un million en donnent trois. C'est la loi qui gouverne toute méthode de Monte-Carlo, et c'est ce qui les rend à la fois utiles et modestes : elles répondent à des questions auxquelles rien d'autre ne répond, et elles y répondent lentement. Cela explique aussi pourquoi une simulation n'est jamais une façon de calculer un nombre connu — personne n'estime \(\pi\) ainsi pour en obtenir les décimales — mais une façon d'en estimer un qu'on ne connaît pas autrement. Compétences à pratiquer
- Choisir le nombre d'essais
I.5
Simuler une variable aléatoire
Définition — Simuler une variable aléatoire
Une variable aléatoire \(X\) qui prend un nombre fini de valeurs est donnée par sa loi : ses valeurs et leurs probabilités, dont la somme vaut \(1\). Simuler \(X\), c'est produire l'une de ses valeurs, chacune avec sa probabilité. Quand les probabilités sont des dixièmes entiers, un seul entier \(r\) tiré entre \(1\) et \(10\), chacun aussi probable que les autres, suffit : la première valeur prend autant de ces entiers que sa probabilité compte de dixièmes, la deuxième valeur prend les suivants, et ainsi de suite. En Python, le tirage est random.randint(1, 10). Répéter la simulation \(n\) fois, de façon indépendante, donne un échantillon de taille \(n\) de \(X\), et la moyenne de ses valeurs est la moyenne de l'échantillon. Exemple
La variable aléatoire \(X\) prend la valeur \(-2\) avec la probabilité \(0{,}3\), la valeur \(1\) avec la probabilité \(0{,}5\) et la valeur \(4\) avec la probabilité \(0{,}2\). L'algorithme ci-dessous simule un échantillon de taille \(10\) de \(X\) : à chaque tour, il lit un entier tiré entre \(1\) et \(10\). Les nombres lus sont, dans l'ordre, \(7\), \(2\), \(9\), \(5\), \(10\), \(1\), \(6\), \(4\), \(8\), \(6\). L'exécuter à la main et donner les deux valeurs qu'il affiche. s ← 0
Pour k allant de 1 à 10
Lire r
Si r ≤ 3 alors
x ← -2
Sinon Si r ≤ 8 alors
x ← 1
Sinon
x ← 4
Fin Si
s ← s + x
Fin Pour
Afficher s
m ← s ÷ 10
Afficher m| Instruction | \(k\) | \(r\) | \(x\) | \(s\) | Affichage |
| départ | \(0\) | ||||
| tour 1 | \(1\) | \(7\) | \(1\) | \(1\) | |
| tour 2 | \(2\) | \(2\) | \(-2\) | \(-1\) | |
| tour 3 | \(3\) | \(9\) | \(4\) | \(3\) | |
| tour 4 | \(4\) | \(5\) | \(1\) | \(4\) | |
| tour 5 | \(5\) | \(10\) | \(4\) | \(8\) | |
| tour 6 | \(6\) | \(1\) | \(-2\) | \(6\) | |
| tour 7 | \(7\) | \(6\) | \(1\) | \(7\) | |
| tour 8 | \(8\) | \(4\) | \(1\) | \(8\) | |
| tour 9 | \(9\) | \(8\) | \(1\) | \(9\) | |
| tour 10 | \(10\) | \(6\) | \(1\) | \(10\) | |
| Afficher \(s\) | \(10\) | \(6\) | \(1\) | \(10\) | \(10\) |
| \(m \leftarrow s \div 10\), Afficher \(m\) | \(10\) | \(6\) | \(1\) | \(10\) | \(1{,}0\) |
10 puis 1{,}0. Les trois tranches d'entiers suivent la loi : de \(1\) à \(3\), on obtient \(-2\), trois entiers sur dix pour une probabilité de \(0{,}3\) ; de \(4\) à \(8\), on obtient \(1\), cinq entiers pour \(0{,}5\) ; \(9\) et \(10\) donnent \(4\), deux entiers pour \(0{,}2\). Dans cet échantillon, \(-2\) est sorti deux fois, \(1\) six fois et \(4\) deux fois : des fréquences de \(0{,}2\), \(0{,}6\) et \(0{,}2\), proches de la loi sans lui être égales. La moyenne de l'échantillon vaut \(1{,}0\). Ce n'est pas l'espérance de \(X\) — un autre échantillon pourrait donner une autre moyenne. Compétences à pratiquer
- Estimer une espérance par simulation
II
Les graphes
II.1
Le vocabulaire des graphes
Un réseau ferroviaire est formé de onze lignes entre sept gares : Lille–Amiens, Lille–Reims, Lille–Caen, Amiens–Reims, Amiens–Caen, Amiens–Tours, Reims–Dijon, Reims–Metz, Caen–Tours, Tours–Dijon et Dijon–Metz. Il y a au plus une ligne entre deux gares, et aucune ligne d'une gare à elle-même.
- Dessiner le réseau : chaque gare est un point, repéré par son initiale, et chaque ligne est un segment reliant deux points.
- Combien le réseau compte-t-il de gares et de lignes ? Combien de lignes partent d'Amiens ? Vérifier que les nombres de lignes partant de chaque gare ont pour somme le double du nombre de lignes, et expliquer pourquoi.
- Un voyageur va de Caen à Metz. Quel est le plus petit nombre de lignes à emprunter ? Donner les trajets possibles.
- Combien de trajets empruntant exactement trois lignes vont de Lille à Amiens ? Une gare peut être traversée, et une ligne empruntée, plusieurs fois.
- Avec L pour Lille, A pour Amiens, R pour Reims, C pour Caen, T pour Tours, D pour Dijon et M pour Metz :
- Le réseau compte \(7\) gares et \(11\) lignes. Quatre lignes partent d'Amiens (vers Lille, Reims, Caen et Tours). Les nombres de lignes partant des gares sont \(3\) (Lille), \(4\) (Amiens), \(4\) (Reims), \(3\) (Caen), \(3\) (Tours), \(3\) (Dijon) et \(2\) (Metz), et \(3 + 4 + 4 + 3 + 3 + 3 + 2 = 22 = 2 \times 11\). Chaque ligne a deux extrémités : elle est comptée une fois à chacune de ses deux gares.
- Aucune ligne ne relie Caen à Metz, et aucune gare n'est reliée aux deux (Caen est reliée à Lille, Amiens et Tours ; Metz à Reims et Dijon) : deux lignes ne suffisent pas. Trois lignes suffisent, de trois façons : Caen–Lille–Reims–Metz, Caen–Amiens–Reims–Metz et Caen–Tours–Dijon–Metz. Le plus petit nombre de lignes est \(3\).
- Un trajet de trois lignes de Lille à Amiens est une succession Lille, premier arrêt, second arrêt, Amiens, dans laquelle deux gares consécutives sont reliées par une ligne. Le premier arrêt est Amiens, Reims ou Caen ; le second est relié au premier et à Amiens.
- Premier arrêt Amiens : le second arrêt est n'importe quelle gare reliée à Amiens (Lille, Reims, Caen ou Tours) : \(4\) trajets, comme Lille–Amiens–Lille–Amiens, qui passe deux fois par Lille et emprunte trois fois la ligne Lille–Amiens.
- Premier arrêt Reims : le second arrêt doit être relié à Reims et à Amiens : seulement Lille, \(1\) trajet.
- Premier arrêt Caen : le second arrêt doit être relié à Caen et à Amiens : Lille ou Tours, \(2\) trajets.
Définition — Graphe non orienté, graphe orienté
Un graphe non orienté d'ordre \(n\) est un ensemble de \(n\) points, les sommets, dont certains sont reliés par des lignes, les arêtes. Un graphe orienté d'ordre \(n\) est un ensemble de \(n\) points reliés par des flèches, les arcs : un arc va d'un sommet vers un autre. Un sommet peut être relié à lui-même par une arête (ou un arc), appelée boucle, et deux sommets peuvent être reliés par plusieurs arêtes (ou arcs).Deux sommets reliés par une arête (ou un arc) sont adjacents ; un sommet auquel aucune arête (ou aucun arc) n'est attachée, pas même une boucle, est isolé.
Exemple
Le graphe non orienté de gauche est d'ordre \(4\) et a \(5\) arêtes : \(AB\), \(AC\), \(BC\), \(CD\) et une boucle en \(D\). Le graphe orienté de droite est d'ordre \(3\) et a \(5\) arcs : \(1 \to 2\), \(1 \to 3\), \(2 \to 3\), \(3 \to 1\) et une boucle en \(3\).  |  |
Définition — Degré d'un sommet
Le degré d'un sommet est le nombre d'arêtes (ou d'arcs) qui y sont attachées, une boucle comptant deux fois. Dans un graphe orienté, le degré entrant d'un sommet est le nombre d'arcs qui y arrivent et son degré sortant le nombre d'arcs qui en partent ; le degré est leur somme. Exemple
Dans le graphe non orienté de l'exemple précédent, \(\deg(A) = 2\), \(\deg(B) = 2\), \(\deg(C) = 3\) et \(\deg(D) = 3\) : l'arête \(CD\) et la boucle, qui compte deux fois. La somme des degrés vaut \(2 + 2 + 3 + 3 = 10\), le double du nombre d'arêtes.Dans le graphe orienté, le sommet \(1\) a pour degré sortant \(2\) (les arcs \(1 \to 2\) et \(1 \to 3\)) et pour degré entrant \(1\) (l'arc \(3 \to 1\)), donc son degré est \(3\) ; le sommet \(3\) a pour degré entrant \(3\) (les arcs \(1 \to 3\), \(2 \to 3\) et la boucle) et pour degré sortant \(2\) (l'arc \(3 \to 1\) et la boucle).
Proposition — Somme des degrés
Dans tout graphe, la somme des degrés des sommets est le double du nombre d'arêtes (ou d'arcs) : $$\sum_{v} \deg(v) = 2 \times (\text{nombre d'arêtes ou d'arcs}).$$ Cette propriété est aussi appelée lemme des poignées de main. Par conséquent, le nombre de sommets de degré impair est pair. Définition — Graphe complet
Un graphe complet est un graphe non orienté, sans boucle ni arête multiple, dans lequel deux sommets distincts quelconques sont adjacents. Le graphe complet d'ordre \(n\) est noté \(K_n\) ; chacun de ses sommets est de degré \(n - 1\), donc il a \(\dfrac{n(n-1)}{2}\) arêtes. Un graphe sans boucle ni arête (ou arc) multiple, comme \(K_n\), est dit simple. Exemple
Le graphe complet \(K_4\) a \(4\) sommets, tous de degré \(3\), et \(\dfrac{4 \times 3}{2} = 6\) arêtes. 
Compétences à pratiquer
- Modéliser une situation par un graphe
- Déterminer des degrés
II.2
Chaînes et connexité
Définition — Chaîne, longueur, chaîne fermée, cycle
Dans un graphe non orienté, une chaîne de longueur \(n\) est une succession de \(n\) arêtes parcourues l'une après l'autre, le parcours de chaque arête s'achevant au sommet où la suivante est empruntée ; elle visite \(n + 1\) sommets, qui peuvent se répéter, et lorsque plusieurs arêtes relient deux sommets consécutifs, la chaîne dit laquelle elle emprunte. Dans un graphe orienté, un chemin de longueur \(n\) est une succession de \(n\) arcs, chaque arc partant du sommet où le précédent arrive.Une chaîne (un chemin) est fermée lorsque l'extrémité de sa dernière arête est l'origine de la première. Une chaîne fermée dont les arêtes sont toutes distinctes est un cycle ; un chemin fermé dont les arcs sont tous distincts est un circuit.
Exemple
Dans le graphe non orienté du premier exemple (\(AB\), \(AC\), \(BC\), \(CD\), une boucle en \(D\)) : \(A \to B \to C \to D\) est une chaîne de longueur \(3\) ; \(A \to B \to C \to A\) est un cycle de longueur \(3\) ; \(A \to B \to A\) est une chaîne fermée de longueur \(2\) mais pas un cycle, puisqu'elle emprunte deux fois l'arête \(AB\) ; \(D \to D\) (la boucle) est un cycle de longueur \(1\).Dans le graphe orienté (\(1 \to 2\), \(1 \to 3\), \(2 \to 3\), \(3 \to 1\), une boucle en \(3\)) : \(1 \to 2 \to 3 \to 1\) est un circuit de longueur \(3\), et \(1 \to 3 \to 1\) un circuit de longueur \(2\) ; il n'y a pas de chemin de \(2\) vers \(1\) de longueur \(1\), puisque le seul arc entre eux va de \(1\) vers \(2\).
Définition — Graphe connexe
Un graphe non orienté est connexe lorsque deux sommets quelconques sont reliés par une chaîne. Exemple
Le graphe ci-dessous n'est pas connexe : il n'y a aucune chaîne de \(A\) à \(D\). Il est formé de deux morceaux connexes, appelés composantes connexes, \(\{A ; B ; C\}\) et \(\{D ; E ; F\}\) ; ajouter l'arête \(CD\) le rendrait connexe. 
Compétences à pratiquer
- Identifier des chaînes et des cycles
- Identifier les propriétés d'un graphe
II.3
Graphes pondérés
Définition — Graphe pondéré
Un graphe est pondéré lorsque chaque arête (ou arc) porte un nombre, son poids : une distance, un coût, une durée. Le poids d'une chaîne (d'un chemin) est la somme des poids de ses arêtes (de ses arcs). Exemple
Les poids ci-dessous sont des longueurs de routes en kilomètres. La chaîne \(M \to N \to P \to Q\) a pour poids \(12 + 8 + 10 = 30\) ; les chaînes de \(M\) à \(Q\) qui ne visitent aucune ville deux fois sont \(M \to N \to Q\) (\(32\)), \(M \to N \to P \to Q\) (\(30\)), \(M \to P \to Q\) (\(35\)) et \(M \to P \to N \to Q\) (\(53\)), donc le trajet le plus court de \(M\) à \(Q\) est de \(30\) km (une chaîne qui repasse par une ville déjà visitée est plus longue, tous les poids étant strictement positifs). 
Compétences à pratiquer
- Lire un graphe pondéré
II.4
Graphes eulériens
Définition — Chaîne eulérienne, cycle eulérien
Dans un graphe non orienté, une chaîne eulérienne est une chaîne qui emprunte chaque arête du graphe exactement une fois ; un cycle eulérien est une chaîne eulérienne fermée. Un graphe qui possède un cycle eulérien est dit eulérien : on peut le dessiner d'un seul trait, sans lever le crayon ni repasser sur une ligne, en revenant au point de départ. Théorème — Euler
Soit \(G\) un graphe non orienté connexe. - \(G\) possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
- \(G\) possède une chaîne eulérienne non fermée si et seulement si exactement deux de ses sommets sont de degré impair ; la chaîne part alors de l'un d'eux et arrive à l'autre.
Exemple — Les ponts de Königsberg
Au dix-huitième siècle, la ville de Königsberg comptait quatre quartiers — une île \(A\), la rive nord \(B\), la rive sud \(C\) et la rive est \(D\) — reliés par sept ponts : deux entre \(A\) et \(B\), deux entre \(A\) et \(C\), et un entre \(A\) et \(D\), entre \(B\) et \(D\), entre \(C\) et \(D\). Une promenade peut-elle traverser chaque pont exactement une fois ? 
Compétences à pratiquer
- Reconnaître des graphes eulériens
III
Pour aller plus loin
Compétences à pratiquer
- Problèmes
- Quiz
Aller à la section