Graphes et Optimisation

itt001il
111-Î~ F'il I Or11 Ë::W Sa
FACULTE DES SCIENCES DE TUNIS

.tVo Université de Tunis El Manar Corrigé Série 1

Leila Hadded
L. Hadded
Rappel du cours

Un graphe est un schéma constitué d'un ensemble de points, appelés "sommets" dont certain sont
reliés par des "arêtes" : défini par un couple G=(S,A)

Sommets Boucle

I
;
I

E D I
I

,
I

' ...
' I
" I
Arê e

• Boucle : Arête reliant un sommet à lui-même.

• L'ordre d'un graphe est le nombre de sommets de ce graphe : ce graphe est d'ordre 5
• Le degré d'un sommet est le nombre d'extrémités d'arêtes que l'on compte sur ce sommet
(pour une boucle, on compte deux extrémités) : d(A)= 1, d(B)=3, d(C)=4, d(D)=2 et d(E)=2
Rappel du cours

• Un graphe simple est un graphe sans boucle et tel que, entre deux sommets, il y ait au plus
une arête.
Boucle ---

Graphe non simple

Arête multiple

Règle : Somme des degrés des sommets d'un graphe = 2 * le nombre de ses arêtes
LsE5d(s) = 2 * IAI
Conséquence : La somme des degrés des sommets d'un graphe est un nombre pair.

Exemple:
1A 1 =1, d(a)= 1, d(b)= 1 -+ chaque arête est comptabilisé 2 fois
LsBd(s) = 1 + 1 = 2 = 2 * IAI
Exercice 1

Sept lycées possèdent chacun un club de théâtre. Ils proposent d'organiser un tournoi de matchs
d'improvisation, ou chaque club doit rencontrer cinq autres clubs participants. Traduire par un
graphe. L'organisation de ce tournoi est-elle possible ? Sinon proposer une autre organisation du
tournoi.
• Pour traduire une situation par un graphe : Pour savoir si on peut construire un graphe,
on indique quels sont les sommets du graphe on utilise la règle : la somme des degrés des
et ce que représente une arête entre deux sommets d'un graphe est égale au double du
sommets. nombre d'arêtes.

On traduit la situation par un graphe non orienté dont les sommets correspondent aux clubs des
lycées. Une arête entre deux sommets représente un match entre deux clubs.
Le graphe est non orienté et d'ordre 7
Si chaque club rencontre 5 autres clubs, le degré de chaque sommet est 5. Donc la somme des
degrés est 7 * 5 = 35.
Or la somme des degrés des sommets d'un graphe et un nombre pair. L'organisation de
ce tournoi est donc impossible.
Pour qu'elle soit possible entre ces 7 clubs, il faut que le degré de chaque sommet soit un
nombre pair , donc chaque club doit rencontrer 2, 4 ou 6 autres clubs.
Exercice 2

Déterminer les degrés des sommets du graphe. En déduire le nombre d'arcs de ce graphe.

Soit G(S,A) un graphe d'ordre n. Soit d(x) le degré

du sommet x E X. On admet le résultat suivant :

3 7
Lsa d(s) = 2 * IAI

Sommet 1 2 3 4 5 6 7 8 9 10 11
Degré 3 2 3 3 3 4 3 3 3 2 3

L d(s) = 3 + 2 + 3 + 3 + 3 + 4 +3+3+3+2+3= 32
s6

32 = 2 * 1 A 1 ~ le nombre d'arcs de ce graphe = 32/2 = 16

Exercice 3

1. Peut-on construire un graphe simple (aucune arête n'est une boucle et il y a au plus une arête
entre deux sommets) ayant :
a) 4 sommets et 7 arêtes ?
Si le graphe simple contient 4 sommets, chacun de ceux-ci est de degré au maximum égal à 3,
d'où une somme totale des degrés égale au plus à 12. Puisque cette somme est égale au double
du nombre d'arêtes, ce nombre d'arêtes ne peut excéder 6, donc ne peut pas être égal à 7.

b) 5 sommets et 11 arêtes ?
Si le graphe simple contient 5 sommets, chacun de ceux-ci est de degré au maximum égal à 4,
d'où une somme totale des degrés égale au plus à 20. Puisque cette somme est égale au double
du nombre d'arêtes, ce nombre d'arêtes ne peut excéder 10, donc ne peut pas être égal à 11.

c) 10 sommets et 46 arêtes ?
Si le graphe simple contient 10 sommets, chacun de ceux-ci est de degré au maximum égal à 9,
d'où une somme totale des degrés égale au plus à 90. Puisque cette somme est égale au double
du nombre d'arêtes, ce nombre d'arêtes ne peut excéder 45, donc ne peut pas être égal à 46.
Exercice 3

2. Soit un graphe simple sans boucles ayant n sommets. Combien peut-il avoir d'arêtes au
maximum?

On peut avoir n * (n-1) arêtes au maximum

2
L. Hadded
Rappel du cours

• Un graphe complet est un graphe simple dans lequel chaque sommet est relié à tous les
autres.
• Dans un graphe complet d'ordre n , le degré de chacun des sommets est n - 1.

Les graphes complets d'ordre 2, 3, 4 et 5 sont donnés ci-dessous :

0-----0
Graphe K2 Graphe K Gr21,phe Ks
Rappel du cours

• Une chaîne une suite d'arêtes consécutives reliant deux sommets (deux sommets consécutifs
sont reliés par une arête)

A - C - D - F - E - D est une chaîne

A - C - F - B n'est pas une chaine (entre les sommets

C et F on n'a pas une arête)

• Un chemin est une chaîne orientée dans un graphe orienté.

A

A - C - E - B - C - E - G est un chemin

A - C - E - F n'est pas un chemin (EF n'est pas un arc)

.F

E
Rappel du cours

• Un graphe non orienté est connexe s'il existe une chaîne pour aller d'un sommet quelconque
à n'importe quel autre sommet du graphe.
'~ emple : graphe connexe Exemple : graphe non connexe

b b On ne peut pas aller du

sommet b au sommet e
C C

d d

• Un graphe orienté est fortement connexe si : V x, y E S, il existe un chemin de x vers y, et

un chemin de y vers x.

Graphe fortement non fortement connexe : de b

connexe on ne peut pas aller à d
Exercice 4

Trois pays envoient chacun à une conférence deux espions ; chaque espion doit espionner tous
les espions des autres pays (mais pas son propre collègue !) .
1. Représentez cette situation par un graphe d'ordre 6 dans lequel chaque arête reliant i et j
signifie que i espionne j que et j espionne i.

2. Ce graphe est-il complet ? Est-il connexe ?

• Ce graphe n'est pas complet car deux espions d'un même pays ne s'espionnent pas, donc les
sommets correspondants ne sont pas adjacents.
• Ce graphe est connexe car entre tout couple de points, il existe au moins une chaîne.
Exercice 4

3. Quel est le degré de chaque sommet ? Déduisez-en le nombre d'arêtes

Chaque espion espionne exactement 4 autres; 2 de chaque pays. Chaque sommet est adjacent à
exactement 4 autres sommets. Tous les sommets sont de degré 4.

Le nombre d'arêtes est égal à la somme des degrés des sommets divisée par deux d'où I A 1 = ½
(4 *6) = 12
L. Hadded
Ra el du cours

Une h in· e é Iê . e èst une ,cha11'ne gur

U ne
1 I le eu é ien ·e,s · une cha'l'\n·e
cont.·,e nt D l ie fois e·t une seule toutes les
eul.érienne fer.mée.
ar:etes du g.rap~ ,e _

Parcourir une fois et une seule toutes les arêtes d'un graphe connexe sans lever le
crayon, revient à chercher une chaîne eulérienne :

s· tous les
.
sommets
s.o,nt paf rs
5 ' 1I existe exa1c tement
1 1e · X
. ,.
U!TI 111112 1 Ullr Ir ·
Départ = 1 un des somm,ets i1npairs
A r1n \tée, ·= l'autre so 111n.et i111 pa Ir
1D·ans taus ~es. au ·res cas
Rappel du cours

Prouver l'existence d'un cycle eulérien ou d'une chaîne eulérienne

• M,e, t h,o,d e

O n véri ·u!
1 1
q ae le graphe- est· coninexe , 1gu ~s on _5· mus les somme~s sont- de deg ~
---}
recherche .e degré de: cha:œn des so,m m,e ts~ pair, il lors le·· graphe a,dmet ua cy~le.
eulé(··,en.

Si dé JX, SÇ)mmets se-u l,en1ent ~ont de d~gré

impa1ir a, ors 1e grap,he adm,e/ u.nè.c-harne
e•uléri:en ne d extremi.tés ces sommets~

Un graphe connexe admet une chaîne eulérienne si le nombre de ses sommets

de degré impair est O ou 2.
Exercice 5

Est-il possible de tracer les figures suivantes sans lever le crayon (et sans passer deux fois sur le
meme trait.... )i-lP
A ·,
. ourquo1"i).

Tracer les figures « sans lever » le crayon revient à trouver une chaine eulérienne. Or ceci n'est
possible que si et seulement si le nombre de sommets de degré impair est égal à O (on aura
affaire à un cycle eulérien, donc le retour se fera sur le sommet de départ) ou à 2.

■ Pour le premier graphe, c'est impossible, tous les sommets étant de degré impair.
■ Pour les trois autres graphes, c'est possible.
■ En ce qui concerne le 3ème graphe, tous les sommets étant de degré pair, on a même
l'existence d'un cycle eulérien.
Exercice 6

Dans une région, cinq pays se partagent l'espace géographique. Est-il possible de visiter ces pays,
en ne traversant qu'une seule fois chaque frontière ?

Le graphe associé est connexe. Degré de chacun des sommets :

A 8 C D E E
3 2 4 2 3

Comme A et E sont les seuls sommets de degré impair, le graphe admet une chaîne eulérienne
d'extrémités A et E : A - B - C - E - D - C - A - E
On peut donc visiter ces pays en traversant une seule fois chaque frontière.
Exercice 7

Le ramassage des ordures ménagères dans une ville dont un plan est représenté ci-contre, à
l'aide d'un graphe, doit être effectué en minimisant le trajet à effectuer. Les sommets sont les
différents carrefours et les arêtes sont les voies de circulation. A B c

a) Est-t-il possible de partir d'un carrefour et d'y revenir en empruntant chaque voie une fois et
une seule.
Le problème revient à chercher un cycle eulérien.
Le graphe G admet deux sommets de degré impair A et E, donc le graphe n'admet pas de cycle
eulérien. D'où il n'est pas possible de partir d'un carrefour et d'y revenir en empruntant chaque
voie une fois et une seule.

b) Le graphe ci-dessus admet-il une chaîne eulérienne? Si oui, en déterminer une.

Le graphe G admet exactement deux sommets de degré impair donc admet une chaîne
eulérienne : A-B-D-A-F-G-D-F-E-D-C-B-E-G-H-C-E
L. Hadded
Rappel du cours

• Le diamètre d'un graphe est la plus grande distance entre deux sommets quelconques.

✓ Distance entre deux sommets longueur de la chaîne la plus courte qui les relie
=
✓ Longueur d'une chaîne = nombre d'arêtes qui la composent

• Matrice d'adjacence : est symétrique si le graphe est non orienté

► Chaque ligne correspond à un sommet
► Chaque colonne correspond à un sommet Les voisins du sommet A
Les successeurs du
sommetA
A B .
A B' C
À 0 l J l À 0 l [

B l 0 .1 l lJ 0 0 l l.
C l I 0 0 C 1 0 0 0
ni l ! 0 0 D 0 0 0 0
A tA: 0 arête De A ,. : Oarc
Aet.B: l arête De A.v :rsB: l arc

D · 1: : 0 arête De B . er A: O arc
D t .D: 0 arête
Rappel du cours

• Matrice d'incidence:
► Chaque ligne correspond à un sommet
► Chaque colonne correspond à une arête (resp. arc)

Les extrémités de l'arête a sont les sommets A et B donc

on met 1 dans les lignes associés aux sommets A et B
b
b C d e
C
A 1 0 1 1 0
B 1 1 0 0 1
C 0 1 1 0 0
C D 0 0 0 1 1
■ Le sommet A est l'extrémité initiale de l'arc a
b donc on met 1
.a b d p
C
,.,_ ■ Le sommet B est l'extrémité finale de l'arc a
A 1 0 -1 1 0
donc on met -1
B -1 1 0 0 1
C 0 -1 1 0 0
D 0 0 0 -1 -1
'-
Exercice 8

On considère quatre villes V 1, V 2, V 3 et V 4 dans un pays où le trafic aérien est encore très réduit :
il existe seulement un vol direct de V 1 vers V 2 et vers V 4, de V 2 vers V 3 , de V 3 vers V 1 et vers V 4 ,
de V 4 vers V 2 •
1. Représenter les données par un graphe convenable.
Les sommets du graphe étant les villes, et les arêtes étant les liaisons, un graphe représentant la
situation est le suivant :

2. Vérifier qu'il existe au moins un vol de chaque ville Vi vers chaque ville Vj, i * j, comportant
au plus deux escales.
Il existe au moins un vol de chaque ville Vi vers chaque ville Vj, i * j, comportant au plus deux
escales, car le graphe est connexe et son diamètre est égal à 3 (chemin de V 4 vers V 1).
Exercice 8

3. Donner la matrice d'adjacence du graphe.

V1 V2 Va V4
V1 0 1 0 1
V2 0 0 1 0
Va 1 0 0 1
V4 0 1 0 0

4. Donner la matrice d'incidence du graphe.

a b C d e f
V1 1 0 0 1 -1 0
V2 -1 1 0 0 0 -1
Va 0 -1 1 0 1 0
V4 0 0 -1 -1 0 1
Exercice 9

Reconstruisez les graphes à partir des matrices suivantes :

a) l 1 1
A= 1 0 1 1
1 l 0 ()
1

1 l 0 () .

Matrice d'adjacence (voir les colonnes de la matrice)

Graphe non orienté (car la matrice d'adjacence est symétrique)
Exercice 9

Reconstruisez les graphes à partir des matrices suivantes :

b) 1 1
A- 0 0 0 l
0 0 0 l
0 0 1 0

Matrice d'adjacence (voir les colonnes de la matrice)

Graphe orienté (car la matrice d'adjacence n'est pas symétrique)

0.....------►.1
Exercice 9

Reconstruisez les graphes à partir des matrices suivantes :

c) 1 -1 0 1 0 0
-1 0 1 0 0 -l
A=
0 1 0 0 -1 1
0 0 -1 -1 1 0

Matrice d'incidence (dans chaque colonne on a un 1 et un -1)

Graphe orienté (extrémité initiale= 1 et extrémité finale= -1)
L. Hadded
Rappel du cours

Algorithme de marquage pour la détermination d'une CFC

1. Marquer par(+) et(-) un sommet aléatoire s

2. Marquer par (-) tous les prédécesseurs d'un sommet marqué par (- )
Marquer par (+) tous les successeurs d'un sommet marqué par (+)
Jusqu'à ce qu'on ne puisse plus marquer de sommets

Les sommets marqués à la fois par (+) et (-) appartiennent à la composante fortement
connexe de sommet s
Exercice 10

Déterminer les composantes fortement connexes des graphes suivants :

+
- +

Si on a
+ + +
alors

Si on a - alors - -
+ +
Exercice 10

Déterminer les composantes fortement connexes des graphes suivants :

+
-

Si on a
+ + +
alors

Si on a - alors - -
-+
Exercice 10

Déterminer les composantes fortement connexes des graphes suivants :

Si on a
+ + +
alors

Si on a - alors - -

3 composantes fortement connexes (CFC) :

{0, 1, 2} ; {3,4} et {5}
Exercice 10

Déterminer les composantes fortement connexes des graphes suivants :

+
f
-

+ C
- h+
Si on a
+ + +
alors

Si on a - alors - -
+
Exercice 10

Déterminer les composantes fortement connexes des graphes suivants :

C
h +
Si on a
+ + +
alors

Si on a - alors - -
+
Exercice 10

Déterminer les composantes fortement connexes des graphes suivants :

Q
C
1h + + +
Si on a alors

k - /
g Si on a - alors - -
/ +

d+ +
Exercice 10

Déterminer les composantes fortement connexes des graphes suivants :

Q
C
1h + + +
Si on a alors

k - /
g Si on a - alors - -
/

4 composantes fortement connexes (CFC) :

{a, h} ; {b, i, g} ; {d} et {f, c, e, j, k}