Terminale maths expertes

Graphes : degrés, chemins et parcours — 20 exercices corrigés

Ces 20 exercices portent sur les graphes finis, les matrices d'adjacence et les parcours. Toutes les données nécessaires sont fournies : aucune figure n'est indispensable. Sauf indication contraire, les graphes sont simples, non orientés et sans boucle. La longueur d'une marche est son nombre d'arêtes ; un chemin simple ne répète aucun sommet.

L'essentiel à retenir

Dans un graphe non orienté, la somme des degrés vaut deux fois le nombre d'arêtes. Un graphe connexe possède un circuit eulérien si tous ses degrés sont pairs, et un parcours eulérien ouvert si exactement deux sommets sont de degré impair. Pour une matrice d'adjacence $M$ , le coefficient $(M^n)_{ij}$ compte les marches de longueur $n$ de $i$ vers $j$ . Dans un graphe orienté, on distingue degrés entrant et sortant. Les critères eulériens s'appliquent en tenant compte de l'orientation et de la connexité appropriée.

Exercice 1 — Lire une matrice d'adjacence

Dans l'ordre $A,B,C,D,E$ , la matrice d'adjacence est donnée par le tableau suivant.

	A	B	C	D	E
A	0	1	1	0	0
B	1	0	1	1	0
C	1	1	0	0	0
D	0	1	0	0	1
E	0	0	0	1	0

Déterminer les degrés et le nombre d'arêtes.

Le graphe est-il connexe ? Déterminer la distance de $A$ à $E$ et justifier sa minimalité.

Graphe avec les arêtes AB, AC, BC, BD, DE — Les données exactes sont indiquées dans l’énoncé ; la position des sommets n’indique pas une distance.

Corrigé détaillé

1. Les sommes des lignes donnent

d(A)=2

d(B)=3

d(C)=2

d(D)=2

d(E)=1

. Leur somme vaut

10

; le graphe possède donc

10/2=5

arêtes. 2. Depuis

B

, on atteint

A,C,D

, puis

E

par

D

: le graphe est connexe. Le chemin

A-B-D-E

a longueur

3

. Comme

E

n'a que

D

pour voisin et que

A

n'est pas adjacent à

D

, aucune marche de longueur inférieure à

3

ne relie

A

E

. La distance vaut donc

3

Exercice 2 — Deux triangles et un circuit eulérien

Un graphe a pour sommets $A,B,C,D,E$ et pour arêtes $AB,BC,CA,AD,DE,EA$ . Vérifier qu'il admet un circuit eulérien.
Donner un tel circuit et expliquer pourquoi ce circuit n'est pas un cycle simple.

Graphe avec les arêtes AB, BC, CA, AD, DE, EA — Les données exactes sont indiquées dans l’énoncé ; la position des sommets n’indique pas une distance.

Corrigé détaillé

1. Les deux triangles ont le sommet

A

en commun : le graphe est connexe. Les degrés sont

4

pour

A

2

pour chacun des autres sommets. Tous sont pairs, donc le critère d'Euler garantit un circuit eulérien. 2. Le parcours

A-B-C-A-D-E-A

utilise chacune des six arêtes exactement une fois. Il est fermé, donc eulérien. Il n'est pas un cycle simple : le sommet

A

est rencontré au milieu du parcours, en plus du départ et de l'arrivée.

Exercice 3 — Un parcours ouvert imposé par les degrés

On considère les arêtes $AB,BC,CD,DA,AC$ . Déterminer les extrémités possibles d'un parcours eulérien ouvert.
Construire un parcours eulérien ouvert. Peut-on parcourir toutes les arêtes une seule fois en revenant au point de départ ?

Corrigé détaillé

1. On obtient

d(A)=d(C)=3

d(B)=d(D)=2

. Le graphe est connexe et possède exactement deux sommets impairs. Tout parcours eulérien ouvert doit donc commencer à

A

et finir à

C

, ou l'inverse. 2. Le parcours

A-B-C-D-A-C

utilise successivement les cinq arêtes, sans répétition. Un circuit eulérien est impossible, car les degrés de

A

C

sont impairs. Dans un circuit, chaque arrivée à un sommet doit pouvoir être appariée à un départ.

Exercice 4 — Une impossibilité et sa réparation

Une étoile a pour arêtes $OA,OB,OC,OD$ . Peut-on parcourir chaque arête exactement une fois, sans imposer de revenir au départ ?
On peut ajouter une arête entre deux feuilles. Montrer qu'une seule arête ajoutée suffit et donner un parcours.

Corrigé détaillé

1. Le centre

O

a degré

4

et les quatre feuilles ont degré

1

. Il existe donc quatre sommets impairs. Or un parcours eulérien ne peut en avoir que zéro ou deux : le parcours demandé est impossible. 2. Ajoutons

AB

. Les degrés de

A

B

deviennent

2

; seuls

C

D

restent impairs. Le parcours

C-O-A-B-O-D

utilise chacune des cinq arêtes une fois. Zéro ajout étant impossible, un ajout est minimal.

Exercice 5 — Marches et chemins simples dans un triangle

Dans le triangle complet de sommets $A,B,C$ , énumérer les marches de longueur $3$ allant de $A$ à $B$ .
Combien de chemins simples de longueur $3$ vont de $A$ à $B$ ? Combien de chemins simples, toutes longueurs confondues, les relient ?

Corrigé détaillé

1. Les possibilités sont

A-B-A-B

A-B-C-B

A-C-A-B

. Pour vérifier l'exhaustivité : après un premier pas vers

B

, les deux choix suivants conviennent ; après un premier pas vers

C

, seul le passage par

A

permet de terminer en

B

. Il y a donc trois marches. 2. Un chemin simple de longueur

3

utiliserait quatre sommets distincts, alors que le graphe n'en possède que trois : il n'y en a aucun. Les chemins simples reliant

A

B

sont exactement

A-B

A-C-B

, soit deux.

Exercice 6 — Reconstruire un graphe à partir d'informations locales

Un graphe simple a pour sommets $A,B,C,D$ . On sait que $A$ est adjacent à $B$ et $C$ , mais pas à $D$ , et que les degrés de $A,B,C,D$ sont respectivement $2;2;3;1$ . Retrouver toutes les arêtes.
Écrire la matrice d'adjacence dans l'ordre $A,B,C,D$ , puis décider si un circuit eulérien existe.

Corrigé détaillé

1. Le sommet

C

, de degré

3

, est adjacent aux trois autres sommets : on a

AC,BC,CD

. Le sommet

A

impose aussi

AB

. Le degré de

B

est alors déjà

2

et celui de

D

déjà

1

. La liste complète est donc

AB,AC,BC,CD

. 2. La matrice est

M=\begin{pmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{pmatrix}

. Les sommets

C

D

ont des degrés impairs ; il n'existe donc pas de circuit eulérien. En revanche,

D-C-A-B-C

est un parcours eulérien ouvert.

Exercice 7 — Compter dans un graphe orienté

Les arcs sont $A\to B$ , $A\to C$ , $B\to C$ , $C\to A$ , $C\to D$ et $D\to B$ . Donner les degrés entrants et sortants.
Compter les marches orientées de longueur $3$ allant de $A$ à $B$ . Le graphe est-il fortement connexe ?

Graphe avec les arêtes AB, AC, BC, CA, CD, DB — Les données exactes sont indiquées dans l’énoncé ; la position des sommets n’indique pas une distance.

Corrigé détaillé

1. Pour

A

, les degrés entrant et sortant valent

(1;2)

; pour

B

(2;1)

; pour

C

(2;2)

; pour

D

(1;1)

. La somme des degrés entrants et celle des degrés sortants valent chacune

6

, le nombre d'arcs. 2. Les deux marches sont

A-C-A-B

A-C-D-B

; un premier pas

A\to B

impose ensuite

C

, puis

A

D

, sans arrivée en

B

au troisième pas. La marche orientée fermée

A\to C\to D\to B\to C\to A

permet d'atteindre chaque sommet depuis chacun des autres : le graphe est fortement connexe.

Exercice 8 — Euler dans un réseau à sens unique

Un réseau orienté possède les arcs $A\to B$ , $B\to C$ , $C\to A$ , $A\to D$ , $D\to A$ . Vérifier les conditions d'existence d'un circuit eulérien orienté.
Donner ce circuit. Si l'arc $D\to A$ est supprimé, donner un parcours eulérien orienté et justifier ses extrémités.

Corrigé détaillé

1. Chaque sommet a autant d'arcs entrants que sortants :

2

pour

A

1

pour les autres. Tous les sommets communiquent avec

A

dans les deux sens, donc le graphe est fortement connexe. Il admet un circuit eulérien orienté. 2. Avant suppression,

A-B-C-A-D-A

convient. Après suppression,

A

possède un départ de plus qu'une arrivée et

D

une arrivée de plus qu'un départ. Le parcours

A-B-C-A-D

utilise tous les arcs restants : il commence nécessairement à

A

et finit à

D

Exercice 9 — Acheminer un colis au moindre coût

Un réseau non orienté a les arêtes pondérées $AB:4$ , $AC:2$ , $BC:1$ , $BD:5$ , $CD:8$ , $CE:10$ , $DE:2$ , $BE:9$ . Appliquer l'algorithme de Dijkstra depuis $A$ .
Donner un trajet optimal de $A$ à $E$ . Comparer avec le trajet passant seulement par $B$ .

Corrigé détaillé

1. Après

A

, les étiquettes sont

B=4

C=2

. On fixe

C=2

, puis on obtient

B=3

D=10

E=12

. On fixe

B=3

, ce qui abaisse

D

8

. On fixe ensuite

D=8

, ce qui abaisse

E

10

. Les distances finales sont

0;3;2;8;10

dans l'ordre

A,B,C,D,E

. 2. Les prédécesseurs donnent

A-C-B-D-E

, de coût

2+1+5+2=10

. Le trajet

A-B-E

coûte

4+9=13

. Il utilise moins d'arêtes, mais son coût est supérieur : minimiser le nombre d'étapes n'est pas minimiser le coût.

Exercice 10 — Tournée d'inspection avec répétitions minimales

Les rues $AB,BC,CD,DA$ mesurent chacune $1$ km et la rue $AC$ mesure $3$ km. Un agent part de $A$ , inspecte chaque rue et revient à $A$ . Pourquoi doit-il répéter au moins une rue ?
Déterminer la longueur minimale de la tournée et en donner une.

Corrigé détaillé

1. Les degrés de

A

C

sont

3

, ceux de

B

D

sont

2

. Aucun circuit eulérien n'existe. La somme des longueurs à inspecter vaut

4+3=7

km, mais une tournée fermée doit ajouter des passages pour rendre pairs les degrés de

A

C

. 2. Les passages supplémentaires doivent relier les deux sommets impairs. Le plus court chemin de

A

C

vaut

2

km, par

B

D

, contre

3

km pour la diagonale. Le minimum est donc

7+2=9

km. La tournée

A-B-C-D-A-C-B-A

a bien cette longueur et inspecte toutes les rues.

Exercice 11 — Alternance dans un graphe biparti

On considère le graphe complet biparti de parties $\{A,B\}$ et $\{X,Y,Z\}$ : toutes les arêtes entre les deux parties sont présentes, et aucune à l'intérieur d'une partie. Donner les degrés et montrer qu'il ne contient aucun cycle de longueur impaire.
Compter les marches de longueur $4$ allant de $A$ à $B$ , puis donner un parcours eulérien.

Corrigé détaillé

1. Les degrés de

A

B

valent

3

, ceux de

X,Y,Z

valent

2

. Une marche change de partie à chaque pas. Après un nombre impair de pas, elle se trouve dans l'autre partie et ne peut revenir au sommet initial. Tout cycle a donc une longueur paire. 2. Une telle marche s'écrit

A-u-v-w-B

, avec

u,w\in\{X,Y,Z\}

v\in\{A,B\}

. Il y en a

3\times2\times3=18

. Le graphe est connexe et ses seuls sommets impairs sont

A,B

; un parcours eulérien est

A-X-B-Y-A-Z-B

Exercice 12 — Passer au graphe complémentaire

Sur les sommets $A,B,C,D,E$ , le graphe $G$ a les arêtes $AB,BC,CD,DE$ . Son complémentaire relie deux sommets distincts exactement lorsqu'ils ne sont pas adjacents dans $G$ . Lister ses arêtes et ses degrés.
Vérifier que le complémentaire est connexe et construire un parcours eulérien.

Corrigé détaillé

1. Parmi les dix paires de sommets, on retire les quatre arêtes de

G

. Il reste

AC,AD,AE,BD,BE,CE

. Chaque degré complémentaire vaut

4-d_G

: les degrés sont donc

3;2;2;2;3

dans l'ordre

A,B,C,D,E

. 2. Depuis

A

, on atteint directement

C,D,E

, puis

B

par

D

: le graphe est connexe. Seuls

A,E

sont impairs. Le parcours

A-C-E-A-D-B-E

utilise les six arêtes exactement une fois.

Exercice 13 — Une liste de degrés impose la connexité

Un graphe simple à six sommets a huit arêtes et des degrés $4;3;3;2;2,x$ . Déterminer $x$ et le nombre de sommets impairs.
Un tel graphe peut-il être non connexe ? Justifier, puis conclure sur l’existence d’un parcours eulérien.

Corrigé détaillé

1. La somme des degrés vaut

16

, donc

x=2

. Deux sommets ont un degré impair. 2. Le sommet de degré

4

appartient à une composante d’au moins cinq sommets. S’il restait un sixième sommet dans une autre composante, il serait isolé, contrairement à son degré, qui est au moins

2

. Le graphe est donc nécessairement connexe. Avec exactement deux sommets impairs, il admet un parcours eulérien ouvert.

Exercice 14 — Une liaison critique entre deux quartiers

Les arêtes sont $AB,BC,CA,CD,DE,EF,FD$ . Montrer que $CD$ est un pont, c'est-à-dire qu'en la supprimant on déconnecte le graphe.
Un parcours eulérien existe-t-il ? Expliquer combien de fois il traverse le pont et donner un exemple.

Corrigé détaillé

1. Les sommets

A,B,C

forment un triangle et

D,E,F

un autre. La seule arête reliant ces deux ensembles est

CD

. Sa suppression laisse exactement deux composantes connexes, de sommets

\{A,B,C\}

\{D,E,F\}

. 2. Les degrés de

C,D

valent

3

, les quatre autres valent

2

. Le graphe connexe admet un parcours eulérien ouvert de

C

D

. Il traverse

CD

une seule fois, comme toute arête. Par exemple :

C-A-B-C-D-E-F-D

Exercice 15 — Un réseau sans cycle

Un réseau a les sommets $A,B,C,D,E,F$ et les arêtes $AB,AC,BD,BE,CF$ . Montrer qu'entre deux sommets il existe un unique chemin simple.
Chaque arête mesure $1$ km. Quelle est la longueur minimale d'une tournée fermée partant de $A$ et parcourant toutes les arêtes ?

Corrigé détaillé

1. Chaque sommet est relié à

A

, donc le réseau est connexe. Aucun cycle ne peut contenir les feuilles

D,E,F

; après leur retrait, il reste seulement

AB,AC

, sans cycle. Deux chemins simples distincts entre les mêmes sommets formeraient un cycle. Le chemin simple est donc unique. 2. Chaque arête est un pont. Une tournée fermée qui la franchit doit la franchir à nouveau pour revenir dans la composante de départ. Il faut donc au moins

2\times5=10

km. Le parcours

A-B-D-B-E-B-A-C-F-C-A

atteint cette borne.

Exercice 16 — Des coefficients de puissance à interpréter

Pour le chemin $A-B-C$ , la matrice d'adjacence est $M=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$ . Calculer $M^2$ et interpréter ses coefficients diagonaux.
Calculer le nombre de marches de longueur $4$ allant de $A$ à $C$ . Pourquoi n'existe-t-il aucune marche de longueur $3$ entre ces sommets ?

Corrigé détaillé

1. Le produit donne

M^2=\begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix}

. Les coefficients diagonaux comptent les marches fermées de longueur

2

: une depuis

A

, deux depuis

B

, une depuis

C

. Elles correspondent à un aller-retour le long d'une arête incidente. 2. Le coefficient

(M^4)_{AC}

se calcule avec

M^2M^2

1\times1+0\times0+1\times1=2

. Les marches sont

A-B-A-B-C

A-B-C-B-C

. Le graphe est biparti de parties

\{A,C\}

\{B\}

; une longueur impaire ne permet pas de rester dans la première partie.

Exercice 17 — Même liste de degrés, graphes différents

Le graphe $G$ est le cycle d'arêtes $AB,BC,CD,DE,EF,FA$ . Le graphe $H$ a les arêtes $AB,BC,CA,DE,EF,FD$ . Comparer leurs degrés et leurs nombres d'arêtes.
Ces graphes peuvent-ils être identifiés par un simple changement de noms des sommets ? Comparer aussi leurs possibilités de parcours eulériens.

Corrigé détaillé

1. Dans les deux graphes, chacun des six sommets a degré

2

. La somme des degrés vaut

12

, donc chacun possède six arêtes. Ces données numériques sont identiques. 2. Non :

G

est connexe, tandis que

H

possède deux composantes. Un changement de noms conserve la connexité. Le graphe

G

admet le circuit eulérien

A-B-C-D-E-F-A

. Dans

H

, il est impossible de parcourir les six arêtes en une seule marche, car aucun passage ne relie les deux triangles.

Exercice 18 — Temps de trajet et nombre de correspondances

Un réseau non orienté a les liaisons $ST:12$ , $SA:3$ , $AB:3$ , $BT:3$ , $SB:8$ , $AT:10$ , pondérées en minutes. Déterminer un trajet de durée minimale de $S$ à $T$ .
Un voyageur accepte au plus deux liaisons. Quel trajet doit-il choisir ? Comparer les deux contraintes d'optimisation.

Corrigé détaillé

1. Depuis

S

, on fixe

A

3

, puis

B

6

grâce à

A

, puis

T

9

grâce à

B

. Le trajet optimal est

S-A-B-T

, de durée

3+3+3=9

minutes. Les trajets directs ou par un seul intermédiaire ne font pas mieux. 2. Avec au plus deux liaisons, les possibilités sont

S-T

12

minutes,

S-A-T

13

minutes et

S-B-T

11

minutes. Le meilleur est donc

S-B-T

. Le minimum sous cette contrainte vaut

11

, contre

9

sans contrainte sur le nombre de liaisons.

Exercice 19 — Visiter les sommets ou parcourir les arêtes

Dans le graphe complet à quatre sommets $A,B,C,D$ , donner un cycle visitant chaque sommet exactement une fois avant de revenir au départ. Existe-t-il un circuit parcourant chaque arête exactement une fois ?
Si chaque arête mesure $1$ , déterminer la longueur minimale d'une tournée fermée parcourant toutes les arêtes.

Corrigé détaillé

1. Le cycle

A-B-C-D-A

visite les quatre sommets une fois : c'est un cycle hamiltonien. En revanche, chaque sommet a degré

3

, donc les quatre sommets sont impairs. Il n'existe ni circuit eulérien ni parcours eulérien ouvert. 2. Les six arêtes donnent une longueur initiale de

6

. Il faut corriger quatre degrés impairs ; chaque passage supplémentaire modifie la parité de deux degrés, donc au moins deux passages sont nécessaires. En répétant

AB

CD

, on obtient la tournée

A-B-C-D-A-C-D-B-A

, de longueur

8

: le minimum est

8

Exercice 20 — Modéliser des rues parallèles

Deux rues distinctes $r_1,r_2$ relient $A$ à $B$ , une rue $r_3$ relie $B$ à $C$ et une rue $r_4$ relie $C$ à $A$ . Pourquoi un graphe simple ne décrit-il pas fidèlement ce réseau ? Donner les degrés du multigraphe adapté.
Donner un parcours utilisant chaque rue une fois. Écrire aussi la matrice dont chaque coefficient compte les rues entre deux sommets.

Corrigé détaillé

1. Un graphe simple ne distingue pas deux arêtes de mêmes extrémités. Il faut un multigraphe, où

r_1

r_2

restent distinctes. On obtient

d(A)=3

d(B)=3

d(C)=2

, avec une somme égale à

8=2\times4

. 2. Le parcours

A\xrightarrow{r_1}B\xrightarrow{r_3}C\xrightarrow{r_4}A\xrightarrow{r_2}B

convient. Dans l'ordre

A,B,C

, la matrice est

M=\begin{pmatrix}0&2&1\\2&0&1\\1&1&0\end{pmatrix}

. Le coefficient

2

est indispensable pour représenter les deux rues parallèles.

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 min Cours particuliers de maths expertes