Éducation Nationale Française · Terminale Maths Expertes

Graphes et matrices d'adjacence

⌚ ~106 min ▢ 11 blocs ✓ 61 exercices PDFCours complet PDFFiche d'exercices PDFCorrections PDFÉvaluation PDFCorrigé de l'évaluation ➣ Prérequis : Calcul matriciel, Suites et récurrence

I Vocabulaire des graphes

Un graphe est un dessin fait de points et de lignes qui en relient certains : des gares et des lignes de chemin de fer, des pages web et des liens, des personnes et leurs connaissances. Ce chapitre fixe le vocabulaire des graphes, puis code un graphe par une matrice et montre que les puissances de cette matrice comptent les chaînes ou les chemins de longueur donnée entre deux sommets.

Signaler une erreur

Découverte

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.

Correction

Avec L pour Lille, A pour Amiens, R pour Reims, C pour Caen, T pour Tours, D pour Dijon et M pour Metz : Ce dessin est un graphe : les gares sont ses sommets et les lignes ses arêtes.
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.
En tout, $4 + 1 + 2 = 7$ trajets. Le comptage à la main devient long quand la longueur ou le réseau grandit.

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

Dans le graphe de gauche, $A$ et $B$ sont adjacents, $A$ et $D$ ne le sont pas ; aucun sommet n'est isolé. Dans le graphe de droite, $2$ est adjacent à $1$ et à $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.

Preuve

Chaque arête a deux extrémités, et elle est comptée une fois dans le degré de chacune de ses extrémités (une boucle a ses deux extrémités au même sommet, où elle compte deux fois) : additionner les degrés de tous les sommets compte chaque arête exactement deux fois.
La somme des degrés est donc paire. Les sommets de degré pair y contribuent pour un nombre pair, donc les sommets de degré impair y contribuent aussi pour un nombre pair ; une somme de nombres impairs n'est paire que s'ils sont en nombre 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.

Le graphe complet $K_5$ a $\dfrac{5 \times 4}{2} = 10$ arêtes, et $K_{10}$ en a $45$.

Compétences à pratiquer

Modéliser une situation par un graphe
Déterminer des degrés

II 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

III 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é

IV Matrice d'adjacence

Découverte

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, avec au plus une ligne entre deux gares et aucune ligne d'une gare à elle-même.

Les gares sont rangées dans l'ordre L, A, R, C, T, D, M.

Construire le tableau $7 \times 7$ dont le coefficient situé à la ligne $i$ et à la colonne $j$ est le nombre de lignes reliant la $i$-ème gare à la $j$-ème, et écrire la matrice $M$ correspondante.
Pourquoi le tableau est-il symétrique par rapport à sa diagonale principale ? Que valent ses coefficients diagonaux ?
Calculer $M^2$ à la calculatrice. Lire le coefficient de la ligne $1$ et de la colonne $5$, et lister les trajets de deux lignes de Lille à Tours. Que représentent les coefficients diagonaux de $M^2$ ?
Calculer $M^3$ à la calculatrice. Combien de trajets de trois lignes vont de Lille à Amiens ? De Caen à Metz ? Que semble compter chaque coefficient de $M^3$ ?

Correction

Chaque coefficient vaut $1$ lorsqu'une ligne relie les deux gares et $0$ sinon : $$M = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 \end{pmatrix}.$$
Une ligne de la $i$-ème gare à la $j$-ème est aussi une ligne de la $j$-ème à la $i$-ème : les coefficients $(i ; j)$ et $(j ; i)$ sont égaux, et le tableau est symétrique. Les coefficients diagonaux valent $0$, puisqu'aucune ligne ne relie une gare à elle-même.
À la calculatrice, $$M^2 = \begin{pmatrix} 3 & 2 & 1 & 1 & 2 & 1 & 1 \\ 2 & 4 & 1 & 2 & 1 & 2 & 1 \\ 1 & 1 & 4 & 2 & 2 & 1 & 1 \\ 1 & 2 & 2 & 3 & 1 & 1 & 0 \\ 2 & 1 & 2 & 1 & 3 & 0 & 1 \\ 1 & 2 & 1 & 1 & 0 & 3 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 2 \end{pmatrix}.$$ Le coefficient de la ligne $1$ et de la colonne $5$ vaut $2$ : les trajets de deux lignes de Lille à Tours sont Lille–Amiens–Tours et Lille–Caen–Tours. En effet, ce coefficient est $m_{11}m_{15} + m_{12}m_{25} + \dots + m_{17}m_{75}$, et le produit $m_{1k}m_{k5}$ vaut $1$ exactement lorsqu'une ligne relie Lille à la $k$-ème gare et qu'une ligne relie cette gare à Tours. Le coefficient diagonal $(i ; i)$ de $M^2$ est $\sum_{k} m_{ik}m_{ki} = \sum_k m_{ik}$, puisque $m_{ki} = m_{ik}$ (question 2) et $m_{ik}^2 = m_{ik}$ pour des coefficients égaux à $0$ ou $1$ : c'est le nombre de lignes partant de la $i$-ème gare, c'est-à-dire le nombre de trajets de deux lignes qui quittent la gare par une ligne et y reviennent par la même ($3$, $4$, $4$, $3$, $3$, $3$, $2$).
À la calculatrice, $$M^3 = \begin{pmatrix} 4 & 7 & 7 & 7 & 4 & 4 & 2 \\ 7 & 6 & 9 & 7 & 8 & 3 & 3 \\ 7 & 9 & 4 & 4 & 4 & 7 & 5 \\ 7 & 7 & 4 & 4 & 6 & 3 & 3 \\ 4 & 8 & 4 & 6 & 2 & 6 & 2 \\ 4 & 3 & 7 & 3 & 6 & 2 & 4 \\ 2 & 3 & 5 & 3 & 2 & 4 & 2 \end{pmatrix}.$$ Le coefficient de la ligne $1$ et de la colonne $2$ vaut $7$ : sept trajets de trois lignes de Lille à Amiens, le nombre trouvé à la main dans le problème d'ouverture du premier paragraphe. Le coefficient de la ligne $4$ et de la colonne $7$ vaut $3$ : trois trajets de trois lignes de Caen à Metz, les trois trajets les plus courts. Chaque coefficient $(i ; j)$ de $M^3$ semble compter les trajets de trois lignes de la $i$-ème gare à la $j$-ème, gares et lignes éventuellement répétées : c'est le théorème de cette section, et il vaut pour toute longueur.

Définition — Matrice d'adjacence

Soit $G$ un graphe, orienté ou non, d'ordre $p$, dont les sommets sont numérotés $s_1, s_2, \dots, s_p$. La matrice d'adjacence de $G$ est la matrice carrée $M = (m_{ij})$ d'ordre $p$ dans laquelle $m_{ij}$ est le nombre d'arêtes (d'arcs, dans un graphe orienté) de $s_i$ vers $s_j$. Une boucle en $s_i$ compte pour $1$ dans $m_{ii}$.
Pour un graphe non orienté, une arête de $s_i$ vers $s_j$ est aussi une arête de $s_j$ vers $s_i$, donc $m_{ij} = m_{ji}$ : la matrice est symétrique par rapport à sa diagonale principale. Pour un graphe orienté, elle n'est pas symétrique en général. La matrice dépend de l'ordre choisi pour les sommets.

Exemple

Le graphe orienté d'arcs $1 \to 2$, $1 \to 3$, $2 \to 3$, $3 \to 1$ et d'une boucle en $3$ a, avec les sommets dans l'ordre $1$, $2$, $3$, la matrice d'adjacence $$M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix}.$$

La ligne du sommet $1$ se lit : aucun arc vers $1$, un arc vers $2$, un arc vers $3$. La boucle en $3$ donne $m_{33} = 1$. La somme d'une ligne est le degré sortant de son sommet ($2$, $1$, $2$) et la somme d'une colonne le degré entrant ($1$, $1$, $3$). La matrice n'est pas symétrique : $m_{12} = 1$ mais $m_{21} = 0$.

Méthode — Écrire et lire une matrice d'adjacence

Fixer un ordre des sommets et le garder pour les lignes et les colonnes.
Sur la ligne $i$, écrire pour chaque sommet $s_j$ le nombre d'arêtes (ou d'arcs) allant de $s_i$ vers $s_j$ ; une boucle en $s_i$ va sur la diagonale, comme $1$.
Contrôler : pour un graphe non orienté la matrice est symétrique ; pour un graphe orienté, la somme de la ligne $i$ est le degré sortant de $s_i$ et la somme de la colonne $j$ le degré entrant de $s_j$.
Pour lire une matrice, dessiner un sommet par ligne, puis un arc pour chaque coefficient non nul, autant que le coefficient l'indique ; pour la matrice symétrique d'un graphe non orienté, n'utiliser que les coefficients situés sur la diagonale et au-dessus, chacun donnant ses arêtes une seule fois.

Compétences à pratiquer

Écrire une matrice d'adjacence

V Nombre de chemins de longueur donnée

Théorème — Nombre de chemins de longueur $n$

Soit $M$ la matrice d'adjacence d'un graphe de sommets $s_1, \dots, s_p$. Pour tout entier $n \geq 1$, le coefficient $(i ; j)$ de $M^n$ est le nombre de chaînes de longueur $n$ de $s_i$ à $s_j$ (de chemins, dans un graphe orienté), sommets et arêtes pouvant se répéter.

Preuve

On démontre par récurrence sur l'entier $n \geq 1$ la propriété $P(n)$ : « pour tous sommets $s_i$ et $s_j$, le coefficient $(i ; j)$ de $M^n$ est le nombre de chaînes (de chemins) de longueur $n$ de $s_i$ à $s_j$ ».
Initialisation. Par définition de la matrice d'adjacence, le coefficient $(i ; j)$ de $M^1 = M$ est le nombre d'arêtes (d'arcs) de $s_i$ vers $s_j$, c'est-à-dire exactement le nombre de chaînes de longueur $1$ de $s_i$ à $s_j$ : $P(1)$ est vraie.
Hérédité. Soit $n \geq 1$ un entier tel que $P(n)$ soit vraie. Une chaîne de longueur $n+1$ de $s_i$ à $s_j$ est une chaîne de longueur $n$ de $s_i$ à un sommet $s_k$, suivie d'une arête de $s_k$ vers $s_j$. Pour un sommet $s_k$ fixé, d'après $P(n)$, il y a $(M^n)_{ik}$ chaînes de longueur $n$ de $s_i$ à $s_k$, et il y a $m_{kj}$ arêtes de $s_k$ vers $s_j$, donc le nombre de telles chaînes est le produit $(M^n)_{ik} \times m_{kj}$. En sommant sur tous les sommets $s_k$ : $$\begin{aligned}[t] \text{nombre de chaînes de longueur } n+1 \text{ de } s_i \text{ à } s_j &= \sum_{k=1}^{p} (M^n)_{ik}\, m_{kj} && \text{(comptage par sommet intermédiaire)} \\ &= (M^n M)_{ij} && \text{(définition du produit matriciel)} \\ &= (M^{n+1})_{ij}, \end{aligned}$$ donc $P(n+1)$ est vraie.
Conclusion. $P(1)$ est vraie, et $P(n)$ entraîne $P(n+1)$ pour tout entier $n \geq 1$ : par récurrence, $P(n)$ est vraie pour tout entier $n \geq 1$.

Exemple

Pour le graphe orienté de l'exemple précédent, avec $M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix}$, $$M^2 = \begin{pmatrix} 1 & 0 & 2 \\ 1 & 0 & 1 \\ 1 & 1 & 2 \end{pmatrix} \qquad\text{et}\qquad M^3 = \begin{pmatrix} 2 & 1 & 3 \\ 1 & 1 & 2 \\ 2 & 1 & 4 \end{pmatrix}.$$ Le coefficient $(1 ; 3)$ de $M^2$ vaut $2$ : les chemins de longueur $2$ de $1$ vers $3$ sont $1 \to 2 \to 3$ et $1 \to 3 \to 3$ (la boucle). Le coefficient $(1 ; 3)$ de $M^3$ vaut $3$ : $1 \to 2 \to 3 \to 3$, $1 \to 3 \to 1 \to 3$ et $1 \to 3 \to 3 \to 3$. Le coefficient $(3 ; 3)$ de $M^3$ vaut $4$ : les chemins fermés de longueur $3$ en $3$ sont $3 \to 1 \to 2 \to 3$, $3 \to 1 \to 3 \to 3$, $3 \to 3 \to 1 \to 3$ et $3 \to 3 \to 3 \to 3$ ; les trois premiers sont des circuits (arcs tous distincts), le dernier n'en est pas un, puisqu'il emprunte trois fois la boucle.

Méthode — Compter les chemins à la calculatrice

Saisir la matrice d'adjacence $M$ dans le mode matrice de la calculatrice, les sommets dans un ordre fixé.
Calculer $M^n$ et lire le coefficient $(i ; j)$ : c'est le nombre de chaînes (de chemins) de longueur $n$ de $s_i$ à $s_j$.
Pour les chaînes de longueur de $1$ à $n$ (au plus $n$ arêtes empruntées), calculer $M + M^2 + \dots + M^n$ et lire son coefficient $(i ; j)$.
Contrôler un petit coefficient en listant les chaînes à la main.

Compétences à pratiquer

Compter des chemins

VI Chaînes et cycles 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.

Ce théorème est admis.

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 ?

Le graphe a pour degrés $\deg(A) = 5$, $\deg(B) = 3$, $\deg(C) = 3$ et $\deg(D) = 3$ : quatre sommets de degré impair. D'après le théorème d'Euler, il n'y a ni cycle eulérien ni chaîne eulérienne : aucune promenade ne traverse chaque pont exactement une fois, comme Euler l'a montré en 1736. Si l'on retire l'un des deux ponts entre $A$ et $B$, les degrés deviennent $4$, $2$, $3$, $3$ : exactement deux sommets impairs, et une chaîne eulérienne de $C$ à $D$ existe, par exemple $C \to A \to B \to D \to A \to C \to D$.

Compétences à pratiquer

Reconnaître des graphes eulériens

VII Pour aller plus loin

Compétences à pratiquer

Raisonner et résoudre des problèmes
Problèmes
Type bac
Quiz

Contrôle du chapitre

4 exercices, sur 20 points. Durée indicative : 1 h 30.

À traiter sur papier, puis à photographier : la correction est automatique, par IA.

Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.

Aucun exercice composé.