Chapitre 2 Problèmes de graphes .pdf



Nom original: Chapitre 2 - Problèmes de graphes.pdf

Ce document au format PDF 1.6 a été généré par Adobe InDesign CS4 (6.0.6) / Adobe PDF Library 9.0, et a été envoyé sur fichier-pdf.fr le 26/04/2015 à 15:09, depuis l'adresse IP 105.103.x.x. La présente page de téléchargement du fichier a été vue 1600 fois.
Taille du document: 3.5 Mo (11 pages).
Confidentialité: fichier public


Aperçu du document


chapitre

2

Problèmes
de graphes

A Le programme
L’enseignement de spécialité prend appui sur la résolution de problèmes (…).
L’étude de telles situations conduit à un travail de modélisation et place les élèves en position de recherche (…).
Exemples de problèmes

Contenus

Gestion de flux, problèmes simples de partitionnement de graphes
sous contraintes : problème du voyageur de commerce, gestion de
trafic routier ou aérien, planning de tournois sportifs, etc.

Graphes : sommets, sommets adjacents, arêtes, degré d’un
sommet, ordre d’un graphe, chaîne, longueur d’une chaîne,
graphe complet, graphe connexe, chaîne eulérienne, matrice
d’adjacence associée à un graphe.

B Notre point de vue
Ce chapitre est avant tout axé sur la résolution de problèmes. Il s’articule en trois parties.
La première partie est consacrée aux généralités : quatre problèmes permettent d’introduire les notions de base de
théorie des graphes :
Les Aventuriers du Rail permet aux élèves d’acquérir le vocabulaire de base des graphes (ordre, sommet, arête,
degré…).
Organisation de tremplin musical a pour objectif principal de découvrir le lemme des poignées de mains.
L’entrepôt est un problème d’ordonnancement.
L’aquariophile est un problème de partitionnement d’un graphe sous contraintes.
Nous avons choisi de ne parler que des sous-graphes stables et de ne plus mentionner la coloration qui n’est plus
explicitement au programme.
La seconde partie est dédiée au thème classique des chaînes eulériennes : le problème des enveloppes, celui des dominos
et celui des sept ponts de Königsberg sont proposés pour apprendre aux élèves les notions de base et leur faire
découvrir le théorème d’Euler. Traversée de frontières permet leur mise en application et Gravure industrielle
permet la découverte de l’algorithme d’Euler.
La dernière partie comprend les notions de longueur d’une chaîne et de matrice d’adjacence d’un graphe. Randonnée
en haute montagne permet aux élèves de découvrir et appliquer ces notions.
Suivent ensuite des exercices à la difficulté graduée. Nous nous sommes efforcés de varier la forme de ces exercices,
contextualisés ou non, en incluant de la logique dès que possible, et utilisant des algorithmes (spécialement celui
d’Euler).
Les travaux pratiques sont, quant à eux, consacrés à un des développements de la théorie des graphes, plus précisément
aux graphes planaires, et à l’utilisation d’un logiciel de graphes : GraphInterface (GRIN).

  Les notions abordées dans le chapitre 2  
1. Généralités sur les graphes
2. Chaînes et cycles eulériens
3. Longueur d’une chaîne et matrice d’un graphe

C Avant de commencer
Voir livre page 94 et le site www.bordas-indice.fr pour les corrections détaillées.

106

D Problèmes
Problème

1 Les Aventuriers du Rail

L’objectif de ce problème est d’acquérir le vocabulaire de base sur
les graphes, et de se familiariser avec celui-ci.
On y définit brièvement ce qu’est un graphe, la notion d’ordre
d’un graphe, d’arêtes, de degré d’un sommet
1. Il y a 14 villes donc 14 sommets.
2. Il y a 23 arêtes.
3. Sept arêtes sont reliées à Paris, une à Rome et cinq à Marseille.
4. Les degrés respectifs sont 7, 1 et 4.

Problème

2 Organisation

d’un tremplin musical

Dans ce problème, on cherche à dénombrer les arêtes d’un
graphe, d’ainsi découvrir le lemme des poignées de mains, et de
l’appliquer ensuite à l’organisation d’un tournoi.
1. a.

Problème

3 L’entrepôt

L’objectif de ce problème est de résoudre un problème
d’ordonnancement, et précisément d’utiliser un graphe orienté
pour regrouper des tâches.
1.
E
H
A

C

B

D

F

L

G

I

J

K

M

KL

M

2.
AB

CDE

Problème

FH

G

I

J

4 L’aquariophile

Dans ce problème, on réalise un partitionnement sous contraintes
d’un graphe  : la coloration ayant disparu du programme, on
résout ce genre de problème en raisonnant sur les sous-graphes
stables.
1.

G
F

E

D
b. Il y aura 3 rencontres par groupe.
c. Il y aura 6 rencontres au total.

A
B

2. a.

C
H
2. a. Oui.
Correctif : il est possible que, dans certains manuels, le graphe de
la question 2 comporte une erreur pour l’un des sommets (B au
lieu de H). La figure correcte est la suivante :
b. Il y aura 4 rencontres par groupe.
c. Il y aura 10 rencontres au total.
3. a. Oui, par exemple :

A

C

H
D

b. Il y aura 12 soirées au total.

F

G

b. Il faudra au moins trois aquariums car les espèces A, C et H
ne peuvent cohabiter.
3. a. Oui.
b. Les espèces D, F et G peuvent cohabiter dans le même
aquarium.
Chapitre 2 Problèmes de graphes – Term ES spécialité

107

4. En quatre aquariums :
Aquarium 1 : espèces D, F et G.
Aquarium 2 : espèces A et E.
Aquarium 3 : espèces C et B.
Aquarium 4 : espèce H.
Correctif de la séquence 1 / Généralités sur les graphes (page 40) : il
se peut que dans certains manuels la figure d’exemple des graphes
orientés soit incomplète ; il manque des flèches entre les sommets
B, E et F.
B
C
A

E

D

4. Non : par exemple avec les chiffres de 1 à 6.
Ce qui ce cache en réalité ici est l’existence d’un cycle eulérien
dans un graphe complet : or, dès que l’ordre de ce graphe est
pair, les sommets seront tous d’ordre impair, rendant la chose
impossible !

Problème

7 Les sept ponts de Königsberg

L’objectif de ce problème est la découverte et la compréhension
du théorème d’Euler, à travers le problème historique qui en fut
à l’origine.
1.

F

Problème

5 Les enveloppes

L’objectif de ce problème est la découverte des chaînes eulériennes
en passant par une conjecture. Il s’agit ensuite d’appliquer
cette conjecture pour trouver des chaînes eulériennes dans des
graphes.
1. a. Non, oui et non.
b. Il semble qu’il ne faut pas avoir plus de deux sommets avec
un degré impair (et donc 0 ou 2 par construction du graphe).
2. Correctif : il est possible que, dans certains manuels, le 1er graphe
de la question 2 ne mentionne pas le sommet F. Le graphe correct
est le suivant :
A

2. Tous les sommets sont de degré impair, il y a contradiction
avec la conjecture du problème 5.
3. N’importe quelle arête reliant deux sommets distincts.

Problème

L’objectif de ce problème est de résoudre un problème concret
de traversée de frontières à l’aide de chaînes eulériennes : après
avoir modélisé ces situations par des graphes, l’élève doit être en
mesure de dire si une solution existe, puis de la trouver.
1. Possible.   2. Impossible.   3. Possible.   4. Possible.

Problème
E

B

D

C
F

E – A – B – F – E – D – F – C – B.
H – G – F – L – K – J – I – G – L – H – J.
Q – O – N – M – Q – P – O – M – R – Q – S – T – U – Q – T.

Problème

6 Un jeu de dominos

L’objectif de ce problème est de construire un cycle eulérien en
raisonnant sur des dominos particuliers. On fait aussi ici appel à
la logique et au dénombrement.
1. Il y a 10 paires de dominos possibles.
2. Par exemple : (1,2) – (2,3) – (3,4) – (4,5) – (5,1) – (1,3) – (3,5) –
(5,2) – (2,4) – (4,1) (ceci peut s’expliquer à l’aide du graphe K5
par exemple).
3. On peut insérer un domino double n’importe où dans la
chaîne (cela correspond à une boucle dans le graphe).

108

8 Traversée de frontières

9 Gravure industrielle

L’objectif de ce problème est la découverte pas à pas de
l’algorithme d’Euler, ainsi que son application à un exemple
simple.
1. E – B – A – D – C – B – D – E.
2.
Partie à graver Pt d’insertion
Supérieure

E

Chemin à insérer
E – B – A – D – C – B – D – E

Droite

I

I–F–E–H–G–F–H–I

Inférieure

M

M–J–I–L–J–K–L–M

Gauche

A

A – N – M – P – O – N – P – A

3. A – E – B – A – D – C – B – D – E – I – F – E – H – G – F – H – I –
M – J – I – L – J – K – L – M – A – N – M – P – O – N – P – A.

Problème

10 Randonnée

en haute montagne

L’objectif de ce problème est la construction d’une matrice
d’adjacence d’un graphe, mais aussi l’utilisation des puissances
de cette matrice pour résoudre des problèmes de chemins d’une
longueur donnée.




1. On obtient M = ⎜




0
0
0
0
0
0

1
0
1
0
0
0

1
0
0
1
0
0

0
1
0
0
1
0

0
0
1
0
0
0

En observant le terme à l’intersection de la ligne correspondant
à E et de la colonne correspondant à S dans la matrice M4, on
voit qu’il doit exister deux chemins de longueur 4 reliant E à S :
il s’agit de E – B – D – C – S et E – B – A – C – S.
5. On forme tout d’abord la matrice d’adjacence (dans l’ordre
des sommets : E, A, B, C, D, F, G, S) :

0⎞
1⎟
0⎟
1⎟

1⎟
0⎠

2. Il y a quatre chemins partant de E et de longueur 2 :
E – A – S,  E – A – C, E – B – A  et  E – B – D.
Il y a deux chemins de longueur 2 partant de A :
A – C – B  et  A – C – S.
⎛ 0 1 0 1 1 1⎞
⎜ 0 0 1 0 0 1⎟


3. M2 = ⎜ 0 0 0 2 0 2 ⎟
0 1 0 0 1 0


⎜ 0 0 1 0 0 1⎟
⎝ 0 0 0 0 0 0⎠
On retrouve les résultats précédents en additionnant les termes
de la ligne correspondant à E ou A respectivement.



4. M4 = ⎜




0
0
0
0
0
0

1
0
2
0
0
0

2
0
0
2
0
0

0
2
0
0
2
0

1
0
2
0
0
0

2⎞
2⎟
0⎟
2⎟

2⎟
0⎠





M= ⎜





0
0
0
0
0
0
0
0

1
0
1
0
0
0
0
0

1
0
0
1
0
0
0
0

1
0
0
0
0
0
0
0

0
1
0
0
0
1
0
0

0
0
0
1
0
0
0
0

0
1
0
1
1
1
0
0

0⎞
0⎟
0⎟
0⎟

1⎟
1⎟
0⎟
0⎠

puis les réponses sont données par M 41,6 = 2, M51,6 = 1 et
M81,6 = 0.
Il y a donc 2 chemins de longueur 4 partant de E et arrivant à
S, un de longueur 5, et aucun de longueur 8.

E Exercices
POUR DÉMARrER
1   1. Tous ces graphes sont des graphes simples, à cinq
sommets.

Graphe

a

b

c

d

e

f

Nombre d’arêtes

5

7

5

7

7

6

2. Seuls d. et e. décrivent la même situation.

8   Toutes les paires de sommets adjacents et les arêtes
qui les relient ; (1,2), (1,3), (2,3), (3,4), (4,5), (5,6), et (4,6).
Les sous-graphes complets d’ordre 3 sont (1,2,3) et (4,5,6).
9   Ordre 2 : (1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,5) et (3,6).
Il n’y en a aucun d’ordre 3.
10   Le diamètre est 3.
11   Voir livre page 94.
12   1.

2   1. Tous ces graphes sont des graphes simples, à six ou

sept sommets.
Graphe

a

b

c

d

Nombre d’arêtes

6

7

6

6

2. a, c et d décrivent la même situation.
3   1. Graphe non simple. Degré de A : 4, B : 3, C : 3.
2. Graphe non simple. Degré de A : 3, B : 3, C : 5, D : 3.
3. Graphe simple. Degré de A : 1, B : 2, C : 2, D : 3.
4   1. 3 ;   2. 4 ;   3. 4.
5   Voir livre page 94.
6  

2. Le degré de chacun des sommets est 4.
3. Il comporte 10 arêtes.
13   Seul 1 est connexe.
14   Voir livre page 94.
15  

Pierre

B

A
7   a. 3 + 3 + 2 = 4 × 2
c. 2 + 2 + 2 + 2 + 2 = 5 × 2

C

D
b. 2 + 2 + 2 +2 = 4 × 2
d. 1 + 3 + 2 + 2 = 4 × 2

Feuille

Ciseaux

Chapitre 2 Problèmes de graphes – Term ES spécialité

109

16  

25   1.

Robot

C
Al
A

Zombie

Pirate

Si
H

Singe

Th

Ninja

17   1. A – B – F – H,  A – C – D – H  et  A – C – G – E – F – H.

2. Non.

⎛ 0 1 0⎞
18   1. M = ⎜ 1 0 1 ⎟
⎜⎝

0 1 0⎠


2. M = ⎜⎜
⎜⎝

0
1
0
0

1
0
1
0

0
1
0
0

0⎞
0⎟
0⎟

0⎠

⎛ 0 1 1⎞
3. M = ⎜ 1 0 1 ⎟
⎜⎝

1 1 0⎠



4. M = ⎜

⎜⎝

0
0
1
1
0

0
0
0
1
1

1
0
0
0
1

1
1
0
0
0

0⎞
1⎟
1⎟
0⎟

0⎠

P
2. Il y au total 5 possibilités :
Simon en A, Alvin en P et donc Théodore en H.
Simon en A, Alvin en C et Théodore en H ou P (soit deux
possibilités).
Simon en H, Théodore en P et donc Alvin en C.
Simon en P, Alvin en C et Théodore en H.
27   a. Oui car la somme des degrés proposés est paire :

19   Voir livre page 94.
20   1.

A
A

B

B
C
C

D

21   Voir livre page 95.
22   1. L’ordre de ce graphe est 5.

2. Ce graphe ne présente pas de boucle, car la diagonale est
remplie de zéros.
3. D’après la matrice, ce graphe compte 8 arêtes (somme des
degrés divisée par 2), il s’agit donc du graphe d.

b. Non car la somme des degrés proposés est impaire.
28   Non car si cela était possible, on pourrait construire un
graphe ayant 15 sommets avec chacun un degré égal à 3 ; or
15 × 3 = 15 est un nombre impair !
29   1. Malheureusement, Laurent ne peut pas organiser un tel
tournoi, car cela reviendrait à construire un graphe à 5 sommets
de degré 3 chacun ; or 5 ×  3 = 15 est un nombre impair.
2. Par exemple :

⎛ 0 0 1 1⎞

23   M2 = ⎜ 0 0 0 1 ⎟
⎜ 1 1 0 0⎟

⎜⎝

0 1 2 0⎠

Par exemple : le cœfficient à la place 4, 3 signifie qu’il existe
deux chemins de longueur 2 qui relient le 4e sommet au 3e.

POUR s’entraîner
24   1.

Car une face est adjacente à quatre autres.
2. L’ordre de ce graphe est 6.
3. 4 + 4 + 4 + 4 + 4 + 4 = 12 × 2

110

30   Le graphe complet d’ordre 5 a tous ses sommets de degré
4, et possède donc 5 × 4 = 10 arêtes.
2
Il en manque donc 4.
31   Le sous-graphe constitué des sommets B, D et F est le
sous-graphe stable d’ordre maximal.
32   La chaîne A – B – C – D – E – F – G passe par tous les
sommets du graphe, donc ce graphe est connexe.
33   Un tel graphe comporte nécessairement une boucle !
34   Voir livre page 95.
35   Faux : l’ordre de ce graphe est 7, et le plus grand degré 5.
36   Vrai : géométriquement il s’agit d’un triangle.
37   Vrai : il s’agit du carré avec ses diagonales au centre de
la figure.
38   Impossible car il existe 4 sommets de degré impair.
39   Voir livre page 95.
40   Tous les sommets de ce graphe connexe sont de degré 4.
D’après le théorème d’Euler, ce graphe admet un cycle eulérien.

41   1. a. Vrai : d’après le tableau des sommets et de leurs
degrés respectifs :

Sommet

A

B

C

D

E

F

Degré

4

4

2

2

3

5

D’après le théorème d’Euler, il existe une chaîne eulérienne
reliant E à F.
b. Faux (elle devrait commencer par E si elle se termine par F).
2. Via l’algorithme d’Euler : F – B – C – F – D – A – F – E – A – B – E.
42   Voir livre page 95.
44   1. Les sommets sont chacune des salles, et les arêtes
symbolisent les portes existant entre les salles.
2. D’après le tableau suivant :
Sommet Boutique A B
Degré

1

4

4

C D E

F G H Accueil

4

2

4

4

4

2

3

Ainsi, via le théorème d’Euler, ce graphe connexe admet une
chaîne eulérienne d’extrémités l’accueil et la boutique (les deux
sommets de degré impair).
3. Accueil – G – H – E – F – B – E – D – B – A – C – D – G – C –
Accueil – A – Boutique, par exemple.
45   1. Une arête entre deux sommets modélise une frontière
entre deux pays.
2. Dans ce graphe connexe, seuls A et E sont de degré impair ;
d’après le théorème d’Euler, il existe donc un tel circuit.
Par exemple : A – B – C – F – A – E – C – D – E – G – D – F – E.
3. Non, car ce graphe n’admet pas de cycle eulérien.
46   1.

F

B
C
D

49   Faux, car il y a deux sommets de degré impair : A et F.
50   1.

G

F

A

B

D

C

E

2. Alan peut incriminer de manière certaine : Bérénice, Delphine,
Frédéric et Ghislain. Il est possible qu’Edgar aie vendu la mèche,
auquel cas Corentin pourrait être également soupçonné.
51   1.

M

S

B

C

L

V
Paco peut se rendre de Valence à Mâcon en quatre étapes :
Valence  –  Grenoble  –  Lyon  –  Bourg-en-Bresse  –  Mâcon.
2. Il sera obligé de repasser par Valence. En huit étapes :
V – G – L – S – V – G – L – B – M.
52   1.

A

H

J

F
A

E

B

C
E

2. Le graphe est d’ordre 6. Les degrés des sommets sont :
Sommet

A

B

C

D

E

F

Degré

3

4

2

4

4

3

3. Dans ce graphe connexe, seuls deux sommets sont de degré
impair : A et F. Il existe, d’après le théorème d’Euler, une chaîne
eulérienne reliant A à F : les survivants peuvent s’échapper de
l’île et le bateau est censé les attendre dans la région F.
47   1. Les degrés des sommets sont :
Sommet

B

C

D

F

N

T

Degré

2

4

4

5

3

4

2. La chaîne B – C – D – F – N – T passe par tous les sommets du
graphe, donc le graphe est connexe.
3. D’après le théorème d’Euler, ce graphe connexe admet une
chaîne eulérienne d’extrémités F et N. Par exemple :
N – D – C – B – F – T – D – F – C – T – N – F.
48   Vrai, le graphe est connexe et seuls A et F sont de degrés
impairs.

I

D
G

K

L

M

N

2.
A

B

CD

EF

GH

IJK

L

M

N

3. On peut en conclure qu’il faudra huit mois au total.
53   Vrai : par exemple E – A – D – B – E.
54   Faux : par exemple A – D – B – E – C.
55   a. 2 ; b. 4 ; c. 6. Oui : le diamètre d’un tel arbre est 2n, où n
est le nombre d’étages de l’arbre.
56   a. 2. b. 4. c. 6. Oui : le diamètre d’un tel arbre est 2n, où n
est le nombre d’étages de l’arbre.
57   1. L’ordre de ce graphe est 7.
Sommet

A

B

C

D

E

F

G

Degré

3

3

3

2

4

3

2

Chapitre 2 Problèmes de graphes – Term ES spécialité

111

2.
d
A
B
C
D
E
F
G

A
X
X
X
X
X
X
X

B
1
X
X
X
X
X
X

C
2
1
X
X
X
X
X

D
3
2
1
X
X
X
X

E
2
2
1
1
X
X
X

F
1
1
2
2
1
X
X

G
1
2
2
2
1
2
X

On peut en conclure que le diamètre de ce graphe est 3.
58   On obtient la matrice d’adjacence suivante :


M= ⎜
⎜⎝

0
1
1
0

1
0
1
0




61   1. M = ⎜





1
0
1
0
0
1
0

0
1
0
1
1
0
0

0
0
1
0
1
0
0

0
0
1
1
0
1
1

1
1
0
0
1
0
0

1⎞
0⎟
0⎟
0⎟

1⎟
0⎟
0⎠

3. 1 + 1 + 2 + 1 = 5 chaînes de longueur 2 partent de A sans
y revenir.
62   Voir livre page 56.
63   1.
A

0⎞
0⎟
.
0⎟
⎟⎠
0

1
1
0
0

0
1
0
0
0
1
1

D

B

En nommant les sommets dans l’ordre alphabétique on obtient :
A
B

C

E
C
2. Il y en a 3 : B – C – E – D, B – C – A – D et B – E – A – D.
64   Vrai : tous les termes hors de la diagonale sont non nuls. Il
n’y a, par contre, pas de chemin de longueur 3 reliant le dernier
sommet à lui-même, ni le sixième à lui-même.
65   Vrai : Il suffit de faire la somme des termes de la cinquième
ligne.
66   Vrai : par exemple : A – B – D – E – B – C – E – F – C.
67   1.
E

D

⎛ 4 2 3 2 1⎞
⎜ 2 3 2 2 2⎟

59   1. M2 = ⎜
3 2 4 2 1⎟

⎜ 2 2 2 3 2⎟
⎜⎝

1 2 1 2 2⎠

2. Il y a deux chaînes de longueur 2 entre A et B.
3. Il y a trois chaînes de longueur 2 entre C et A.
4. Après avoir calculé M3, on dénombre sept chaînes de
longueur 3 entre B et D.
60   Correctif : il est possible que, dans certains manuels, le graphe
G comporte des erreurs. La figure correcte est la suivante :

H

F

I

B
A
C

E


1. On obtient M = ⎜

⎜⎝

0
0
0
0
1

1
0
1
0
0



M= ⎜

⎜⎝

D
0
1
0
1
0

0
1
1
0
1

1⎞
0⎟
0⎟ .
1⎟

0⎠

2. Évident.
3. Il y en a cinq : D – E – A – B – C – B, D – C – B – D – C – B,
D – E – D – E – A – B, D – E – A – E – A – B et D – C – D – E – A – B.
4. Le coefficient à l’intersection de la première ligne et de la
première colonne de M5 vaut bien 1 ; il s’agit de :
A – B – C – D – E – A.
5. Non, il y a cinq cycles partant de B.

112

G
2. Dans l’ordre alphabétique des sommets, on obtient :
0
1
0
1
1

1
0
1
0
1

0
1
0
1
1

1
0
1
0
1

1⎞
1⎟
1⎟ .
1⎟

0⎠

68   1. Oui car la matrice n’est pas symétrique.

2.

A

B

D
C

⎛ 9
3. On a M = ⎜⎜ 7
3
⎜⎝
0
3 reliant A à C.

3
2
1
0

4
3
1
0

6 ⎞
10 ⎟ donc il y a 4 chemins de longueur
7 ⎟

1 ⎠

POUR faire le point
Voir livre page 95 et le site www.bordas-indice.fr pour les
corrections détaillées.

Travaux pratiques
TP

1 Les graphes planaires

Il s’agit, dans ce TP, de l’étude d’un approfondissement de la
théorie des graphes issue d’une énigme très classique : l’énigme
des trois maisons. On y résout en partie le problème du cavalier et
on aborde aussi le théorème de Kuratowski-Wagner.
A. Exemple de graphes planaires
1.
A
B
C

E
G
L
2. Non.
3. Non : A et B ne sont pas reliés par exemple.
4. En dessinant K4 ainsi :

TP

2 Utilisation du logiciel GRIN

Dans ce TP, on utilise les possibilités de GRIN pour résoudre
facilement des problèmes de chaînes eulériennes, mais aussi des
problèmes de cycles hamiltoniens plus connus sous le nom du
problème du voyageur de commerce.
Fichiers associés sur www.bordas-indice.fr et sur le manuel
numérique premium : 02_TESspe_TP2_partie_A.net, 02_
TESspe_TP2_partie_B1.net et 02_TESspe_TP2_partie_
B2.net (fichiers GRIN)
A. Chaînes eulériennes
2. Le graphe admet une chaîne eulérienne mais pas un cycle
eulérien.
3. a. Le graphe admet un cycle eulérien.
b. Le graphe admet un cycle eulérien.
c. Le graphe admet un cycle eulérien.
B. Le problème du voyageur de commerce :
les cycles hamiltoniens
Tous les graphes proposés sont hamiltoniens.

POUR ALLER PLUS LOIN
77   Une personne peut serrer la main d’au plus 6 autres
personnes. Pour que les nombres de poignées de mains
échangées soient tous distincts, il s’agit nécessairement des
nombres 6, 5, 4, 3, 2, 1 et 0.
Il y a une personne qui a échangé 6 poignées de main ; c’est
donc son conjoint qui n’en a échangé aucune.
On obtient le graphe provisoire suivant :

Il y a une personne qui échange 5 poignées de mains ; c’est
donc son conjoint qui en échange une seule.

5. Non.
B. Le problème du cavalier
1

2

3

3

8

1

4

5

6

4

11

6

7

8

9

9

2

7

10

11

12

10

5

12

C. Notion de mineur dans un graphe
Il suffit de fusionner deux à deux les sommets extérieurs avec
les sommets intérieurs les plus proches.
D. Caractérisation de Kuratowski-Wagner
1. K3,3 est un mineur de ce graphe.
2. K5 est un mineur de ce graphe.
3. K3,3 est un mineur de ce graphe.
4. K5 est un mineur de ce graphe.

On obtient donc :

Il y a une des personnes des deux couples non encore
considérés qui échange 4 poignées de main , donc son conjoint
en échange 2.
Ainsi, le dernier couple, M. et Mme Euler, a donc échangé
chacun 3 poignées de mains.
Chapitre 2 Problèmes de graphes – Term ES spécialité

113

1

78   1.

2
5

4
3
2. Il faut trouver un sous-graphe stable d’ordre maximal : le
plus grand est d’ordre 3 et est composé des sommets 5, 3 et 2
ce qui répond à la question.
79   1.
2.

5. Courges  –  Ail  –  Poireaux, Pommes de Terre  –  Choux,
Tomates, Radis  –  Petits Pois.
83   Cela revient à prouver que le graphe modélisé par la toile
admet une chaîne eulérienne voire un cycle eulérien.
Or dans ce graphe connexe, tous les sommets sont de degré
pair : d’après le théorème d’Euler, l’araignée a tissé sa toile en
une seule fois.
84   1.
M
D

C
A

S

E

K

P

Q

J

H
2.

I

2. Le graphe composé des sommets F, A et M.
3. Il en faudra au moins 3 pour passer séparément Français,
Anglais et Mathématiques.
4. Oui car les sommets F, I et D forment un sous-graphe
stable : Français, Informatique et Dessin pourront être passés
simultanément. L’épreuve de Sport pourra se dérouler pendant
celle de Mathématiques ou d’Anglais.
81   Non, car le graphe associé n’est pas connexe : la case
centrale ne peut être atteinte.

82   1.

2. La somme des degrés vaut 32 donc il y a exactement 16
arêtes.
3. Le sous-graphe composé des sommets Pt, T, Co et R est
complet. Il faudra donc au moins 4 parcelles différentes.
4. Radis – Petits Pois, Pommes de Terre  –  Choux, Tomates 
–  Poireaux et Courges  –  Ail.

114

N

F

D

F

M

E

L

I

A

80   1.

G

A

B

CD

E

FGH

I

J

K

L

MNP

Q

3. Pour chaque sommet, on note la durée de l’étape la plus
longue, puis on ajoute :
2 + 0,5 + 1 + 2 + 2 + 5 + 3 + 1 + 1 + 1 + 2 = 20,5 semaines.
La partie qui ralentit le processus est le Level Building.
85   1. Non car il manque par exemple une arête reliant F à B.
L’ordre du graphe est 7.
2. Il s’agit d’un sous-graphe complet d’ordre 4.
3. Il lui faudra au moins 4 couleurs, car A, B, C et D ne peuvent
être de la même couleur deux à deux.
4. Les sommets étant classés dans l’ordre alphabétique :



M= ⎜





0
1
1
1
0
0
0

1
0
1
1
1
0
1

1
1
0
1
1
0
0

1
1
1
0
1
0
0

0
1
1
1
0
1
1

0
0
0
0
1
0
1

0⎞
1⎟
0⎟
0⎟.

1⎟
1⎟
0⎠

5. Le nombre de chemins de longueur 8 reliant B à D est donné
par M82,4 = 12 636.
6. Car, dans ce graphe connexe, le théorème d’Euler ne
s’applique pas : il y a quatre sommets de degré impair (A, B,
E et G).
7. Pour que le théorème d’Euler s’applique, il suffit de créer une
liaison entre deux sommets parmi A, B, E et G.
Les deux sommets restants seront les extrémités de la chaîne
eulérienne.
Les possibilités sont au nombre de 6 : A – B, A – E, A – G, B – E,
B – G et E – G.
86   1. Le nombre de questionnaires est le nombre d’arêtes : la
somme des degrés des sommets vaut 20 donc il y a exactement
10 arêtes.

2. Les sommets étant classés dans l’ordre alphabétique :



M= ⎜




0
1
1
1
0
1

1
0
1
1
1
1

1
1
0
1
0
0

1
0
1
0
1
0

0
1
0
1
0
0

1⎞
1⎟
0⎟
0⎟

0⎟
0⎠

3. Ce graphe n’est pas complet car il manque par exemple une
arête reliant E à F.
Il est connexe car la chaîne F – A – B – C – D – E passe par tous
les sommets.
4. a. Pour trouver une chaîne eulérienne dans ce graphe
connexe, il faut s’assurer qu’au plus deux sommets sont de
degré impair : seuls B et C le sont.
On doit donc nécessairement commencer une telle visite par
B ou C.
b. Si on commence la visite par C, on la termine nécessairement
en B.

C AP VERS LE BAC
Sujet

A
A

1.

B
C

S

D

E

F
G

H

2. Non, car dans ce graphe connexe il y a plus de deux sommets
de degré impair : le théorème d’Euler ne s’applique pas et on
ne peut trouver de chaîne eulérienne.
3. La matrice M est nécessairement symétrique.
4. a. Il faut regarder le cœfficient M45,5 = 31. Il y a donc 31
chaînes de longueur 4 reliant D à lui-même.
b. Il faut regarder le cœfficient M41,4 = 2. Il y a donc deux chaînes
de longueur 4 reliant S à C.
c. Non car M43,4 = 0. Il est donc impossible de joindre la salle B
à la salle C avec un chemin de longueur 4.

Sujet

B
A

1.
B

E

C
D
2. Le sous-graphe constitué des sommets A, B, C et D et des
arêtes les reliant est complet.

3. a. La chaîne A – B – C – D – E passe par tous les sommets
donc le graphe est connexe.
b. Il n’est pas complet car il manque une arête reliant C à E.
4. Ce graphe est connexe et seuls C et E sont de degré impair :
d’après le théorème d’Euler, ce graphe admet une chaîne
eulérienne.
5. Les sommets C et E : ainsi tous les sommets seront de degré
pair et le théorème d’Euler assurera dans ce graphe connexe
l’existence d’un cycle eulérien.
6. Par exemple CDACBAEBDE.
7. Il s’agit bien de transformer la chaîne eulérienne trouvée
précédemment en cycle eulérien : conformément à la
question 5, il faut construire une passerelle entre C et E.

C

Sujet

1. La chaîne A – D – F – B – C – E passe par tous les sommets du
graphe : deux quelconques sommets peuvent être reliés par
une chaîne . Ce graphe est bien connexe.
2. Seuls deux sommets, A et F, sont de degré impair. D’après
le théorème d’Euler, il existe une chaîne eulérienne reliant A
à F ; par exemple : A – D – F – B – A – C – D – E – B – C – E – F.
3. Toujours d’après le théorème d’Euler, on devrait n’avoir que
des sommets de degré pair pour garantir l’existence d’un cycle
eulérien.
4. Une arête reliant A à F.



5. M = ⎜




0
1
1
1
0
0

1
0
1
0
1
1

1
1
0
1
1
0

1
0
1
0
1
1

0
1
1
1
0
1

0⎞
1⎟
0⎟
1⎟

1⎟
0⎠

6. Résultats obtenus avec la calculatrice.
7. Ce nombre correspond au cœfficient M 3 1,6 = 5.
Ces chaînes sont : A – C – E – F, A – C – D – F, A – C – B – F, A –
B – E – F, A – D – E – F.

D

Sujet

1. L’ordre de ce graphe est 6.
On dresse le tableau sommets / degrés :
Sommet

A

B

C

D

E

F

Degré

4

3

4

3

3

3

2. Dans ce graphe connexe, il y a quatre sommets de degré
impair.
D’après le théorème d’Euler, ce graphe n’admet pas de chaîne
eulérienne ni de cycle eulérien.
Un piéton ne peut donc pas emprunter toutes les avenues une
fois et une seule.



3. M = ⎜




0
0
1
1
0
0

1
0
1
0
0
0

0
0
0
1
0
1

0
0
0
0
1
0

1
0
0
0
0
1

0⎞
1⎟
0⎟
0⎟

0⎟
0⎠

4. Il y en a deux : D – A – B et D – C – B.
5. Ce nombre correspond au cœfficient M24,2 = 2.
Chapitre 2 Problèmes de graphes – Term ES spécialité

115

B

87   1.

A

C

À l’aide de la calculatrice, on trouve M31,2 = 13. Il y a donc 13
chaînes de longueur 3 reliant A à B.
88   1. Dans ce graphe connexe, seuls les sommets A et I sont
de degré impair. D’après le théorème d’Euler, le graphe admet
une chaîne eulérienne.
2. En présentant les résultats dans un tableau :
Chaîne à insérer

E
D
2. Ce graphe connexe admet un cycle eulérien d’après le
théorème d’Euler : en effet tous ses sommets sont de degré
pair (égal à 4).
⎛ 0 1 1 1 1⎞
⎜ 1 0 1 1 1⎟
3. M = ⎜ 1 1 0 1 1 ⎟ .
⎜ 1 1 1 0 1⎟
⎜⎝

1 1 1 1 0⎠

116

Chaîne courante

aucune

AEI

ABCA

ABCAEI

BFGB

ABFGBCAEI

CDHC

ABFGBCDHCAEI

DEFD

ABFGBCDEFDHCAEI

GHIG

ABFGHIGBCDEFDHCAEI

3. Une arête reliant A à I.


Chapitre 2 - Problèmes de graphes.pdf - page 1/11
 
Chapitre 2 - Problèmes de graphes.pdf - page 2/11
Chapitre 2 - Problèmes de graphes.pdf - page 3/11
Chapitre 2 - Problèmes de graphes.pdf - page 4/11
Chapitre 2 - Problèmes de graphes.pdf - page 5/11
Chapitre 2 - Problèmes de graphes.pdf - page 6/11
 




Télécharger le fichier (PDF)


Chapitre 2 - Problèmes de graphes.pdf (PDF, 3.5 Mo)

Télécharger
Formats alternatifs: ZIP



Documents similaires


chapitre 2 problemes de graphes
theorie des graphes
graphes
graphe
thgraphes
serie graphes

Sur le même sujet..