Chapitre 2 :

Théorie des graphes et applications

I-Introduction :

Les graphes interviennent dans de nombreux domaines de la vie de tout les jours .Ils
servent à modéliser les structures comportant des liens entre différents [Link]
théorie de graphe joue un rôle fondamental dans la modélisation de situation
économique, techniques. C’est l’outil le plus utilisé de l’informatique, la raison en est
c 2012/2013

que le parcours de sommets et d'arêtes est réalisé facilement par les ordinateurs.
L’exemple le plus concret est celui de voyageur qui désire se déplacer d’une ville à
une autre en minimisant la distance parcourue.

Dans le présent chapitre, on introduit quelques notions de base. Traitant d'abord des
graphes en général, on aborde ensuite les graphes planaires et le fameux théorème
d'Euler. Cet objet mathématique permet de modéliser certains types de problèmes
parfois complexes et ainsi de les résoudre.

Par exemple, on peut schématiser une carte routière entre différentes villes : un
SMI-S6

sommet représente alors une ville et une arête une route, sur laquelle on indiquera
une valeur correspondant à la longueur de celle-ci.

-Problème des ponts de Königsberg

De quel problème s'agit-il ? Dans la ville de Königsberg, fondée en 1236 par le roi
Ottokar de Bavière, coule un fleuve le Pregel qui traverse toute la ville et entoure
Recherche Opérationnelle

deux îles (voir dessin).

Pour joindre les différentes rives, il y a sept ponts. La question est la suivante : peut-
on se promener d'une rive à une autre en passant sur chaque pont sans jamais
repasser deux fois sur le même chemin ?
Mohammed Berrajaa

34

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 C'est en établissant un graphe des ponts de Königsberg puis en raisonnant à partir
de ce graphe qu'Euler résolut le problème des ponts de Königsberg.
c 2012/2013

Solution :
SMI-S6

Euler a émis le théorème suivant : Pour parcourir un graphe en ne passant qu'une

fois et une seule sur chaque trait (arête) reliant les différent points (sommets), il faut
qu'il y ait au plus 2 points reliés par un nombre impaire de chemin.

Dans le cas des ponts de Königsberg, en regardant le graphe, on voit que chaque
sommet est connecté à un nombre impair d'arêtes. Il ne peut donc pas y avoir de
solution au problème des ponts de Königsberg.
Recherche Opérationnelle

II-Vocabulaire de base

II-2 notion de flèches et d’arrêtes :

Sommets :

Soient s et s’ deux éléments de S

On appelle flèche de source (d’origine) s et de but (de destination) s’, le couple (s,s’).

et on note cette flèche s → s’ ;

Mohammed Berrajaa

On appelle arête reliant s et s’, l’ensemble {s, s’}.

Et on la note : s --- s’ ou s’ --- s.

35
-si a= s→ s’ ou a= s --- s’, s et s’ sont appelés les extrémités de a ;

-on dit que s --- s et s → s sont des boucles.

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013
 II-3 Définition des Graphes, parcours et cycles :

Définition 2.1. On appelle graphe non orienté tout couple = (S, A) oǔ

-S est un ensemble fini dont les éléments sont appelés sommets (ou nœuds) ;

-A est un multi-ensemble fini des arêtes.

Par exemple, pour le graphe de la figure 1, on a :

c 2012/2013

S= {A, B, C, D}

A= {A B, A B, A C, A C, C D, A D, B D}

Définition 2.2. Graphe orienté : lorsqu’on affecte un sens de parcours à un graphe,

on dit qu’il est orienté.chaque sommet dispose d’un sommet prédécesseur et
[Link] le pratique on met des flèches aux arrêtes du graphe.

Defintion 2.3. Un graphe = (S, A) est dit simple si A set un ensemble et ne
SMI-S6

contient pas de boucle.

Le graphe de la figure 2 est un graphe simple.

Définition 2.4. Un graphe = (S, A) est dit complet si deux sommets quelconques
distincts sont reliés par au moins une arête ou une flèche .autrement dit : si toute
paire de sommets de G est une arête.
Recherche Opérationnelle

Définition 2.5. Ordre d’un graphe : l’ordre d’un graphe est définie par le nombre de
ses sommets.

Définition 2.6. Degré d’un sommets : le degré d’un sommet est le nombre des
sommets voisins avec lesquels il est en relation.

Définition 2.7. Sommets adjacents : sommets reliés entre eux par une arrête.

Définition 2.8. Parcours ou chaine eulérienne : on appelle parcours eulérien d’un

graphe tout chemin passant une seule fois par chaque arête du [Link] utilise
aussi le terme de chaine eulérienne.
Mohammed Berrajaa

36

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

c 2012/2013

Définition 2.9. Cycle hamiltonien : est un parcours ne passant qu’une seule fois et
une seule par chacun des sommets du [Link] la différence avec le parcours
eulérien qui concerne les arêtes alors que pour le cycle hamiltonien il s’agit des
sommets. A priori cela peut paraître une autre formulation de la même chose, mais il
n'en est rien. Ainsi les problèmes qui associent les parcours eulériens et les cycles
SMI-S6

hamiltoniens sont différents.

Recherche Opérationnelle

La chaine 4→5→0→1→2→8→6→7→3→9 est une chaine hamiltonienne.

Définition 2.10. Graphe hamiltonien : graphe qui dispose un cycle hamiltonien.

Définition 2.11. Soit = (S, A) un graphe orienté.on appelle chemin de longueur p
Mohammed Berrajaa

toute suite

c= ( a1, a2 ,..., a p ) oŭ pour tout i, (1≤ i≤ n), ai Є A et pour tout i, (1< i< p)
l’origine de ai est le but de ai 1 . 37

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 On dit alors que c est un chemin ayant pour origine l’origine a1 et pour but le but
de a p .

Graphe réflexif : si  S (si , si )  A

Graphe symétrique : si , s j  S (si , s j )  A  (s j , si )  A

c 2012/2013

Graphe asymétrique : si , s j  S (si , s j )  A  ( s j , si )  A

Graphe transitif : si , s j  S (si , s j )  A , (s j , sk )  A  (si , sk )  A

Représentation du Graphe :

Matrice d’Adjacence :
SMI-S6

La matrice d’adjacence fait correspondre les sommets origines des arcs (placé en
ligne dans la matrice) aux sommets destination (placés en colonnes).Dans la
formalisme matrice booléenne, l’existence d’un arc ( si , s j ) se traduit par
l’existence d’un « 1 » à l’intersection de la ligne si et de colonne sj ; l’absence
d’un arc par la présence d’un « 0 ».
Recherche Opérationnelle

Exemple :
Mohammed Berrajaa

38

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 Matrice d’incidence :

Ligne ↔ sommet

Colonne ↔ arc

Si u= (i, j) Є A, on trouve dans la colonne a : aiu =1 a ju = -1 et tous les autres

termes sont nuls.
c 2012/2013

Exemple :
SMI-S6

Graphes planaires

Définition
Un graphe est planaire s'il admet une représentation plane (en 2 dimensions) et si
Recherche Opérationnelle

deux arêtes ont un point commun, celui-ci est une des extrémités de chacune des
deux arêtes.

Exemple
Mohammed Berrajaa

39
Formule d'Euler

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 Définition
Si on prend un graphe planaire connexe (continu) ayant m sommets et de n arêtes et
si f désigne le nombre de faces alors :

m+f-n=2

Cette formule apparue en 1752 permet d’énoncer le théorème suivant ;

Théorème des polyèdres réguliers :

c 2012/2013

Il n’existe pas d’autres polyèdres réguliers que le tétraèdre, cube, l’octaèdre, le

dodécaèdre et l’icosaèdre.

Algorithme de coloration de Welsh et Powell

Cet algorithme couramment utilisé permet d'obtenir une assez bonne
coloration d'un graphe, c'est-à-dire une coloration n'utilisant pas un trop grand
nombre de couleurs. Cependant il n'assure pas que le nombre de couleurs
utilisé soit minimum (et donc égal au nombre chromatique du graphe).
SMI-S6

Étape 1
Classer les sommets du graphe dans l'ordre décroissant de leur degré, et
attribuer à chacun des sommets son numéro d'ordre dans la liste obtenue.
Étape 2
En parcourant la liste dans l'ordre, attribuer une couleur non encore utilisée au
premier sommet non encore coloré, et attribuer cette même couleur à chaque
sommet non encore coloré et non adjacent à un sommet de cette couleur.
Étape 3
Recherche Opérationnelle

S'il reste des sommets non colorés dans le graphe, revenir à l'étape 2. Sinon, la
coloration est terminée.

Exemples d’application de la théorie des graphes :

Coloration des sommets d'un graphe planaire

Théorème des quatre couleurs

On peut colorer les sommets d'un graphe planaire (sans boucles) en utilisant au plus
quatre couleurs de telle sorte que toutes les arêtes aient des extrémités de couleurs
différentes.
Mohammed Berrajaa

Le théorème des 4 couleurs, énoncé (mais non démontré) en 1853 par Francis
Guthrie, indique que quatre couleurs suffisent pour colorier une carte géographique
de telle sorte que deux pays frontaliers soient toujours de couleurs différentes. Au-
delà de l’enjeu mathématique lié à ce théorème, ces questions de coloriage ont des
applications pratiques plus larges, notamment en téléphonie mobile ; elles permettent 40
effectivement de réduire les fréquences d'émissions utilisées, équivalent des
couleurs.

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 Pour colorer les arêtes d’un graphe, on peut se ramener au problème de la coloration
des sommets, il suffit pour cela de travailler non pas sur le graphe lui même, mais sur
le graphe adjoint, noté ’, et que l’on définie ainsi :

 A chaque arête d’un graphe correspond un sommet de ’.

c 2012/2013

 Deux sommets de ’ sont reliés par une arrête si les deux arrêtes
correspondante de  sont adjacentes.

On peut ensuite appliquer par exemple l’algorithme de Welsh sur le graphe ’,
pour colorer ses sommets, une fois cela fait, on colorera les arrêtes de  de la
même couleur que les sommets de ’.
SMI-S6
Recherche Opérationnelle

On se propose alors de trouver le plus court chemin d’un sommet à un autre du

graphe. Chaque arête prendre une valeur différente. Dans une application pratique
cette valeur peut représenter une distance, un coût ou bien encore une dépense
d’énergie :

Deux algorithmes sont alors à notre disposition :

Le premier s’applique dans le cas ou les valeurs associées aux arêtes sont
positives : c’est l’algorithme de Dijkstra.
Le second algorithme, dit de Bellman, permet des calculs plus complexes puisqu’il
inclut aussi les valeurs négatives (ce qui peut être utile pour des calculs de coûts par
Mohammed Berrajaa

exemple).

Algorithme de Dijkstra
Cet algorithme permet à partir d’un graphe quelconque avec des arêtes positives, de 41
calculer le plus court chemin d’un point de départ vers tous les autres.

Déroulement de l’algorithme :
On associe à chaque point une marque. Au début toutes les marques sont égales à
Mohammed Berrajaa | Recherche Opérationnelle 2012-2013
 l’infini excepté celle du point de départ qui vaut zéro. Les marques initiales sont dites
provisoires et au fur et à mesure de l’algorithme elles diminuent jusqu’à prendre une
valeur minimale, on dit alors que la marque est définitive. A chaque étape on étudie
les arêtes qui partent d’un point et on recalcule les marques des points adjacents, on
modifie la valeur de la marque uniquement si ce nouveau calcul mène à une valeur
inférieure. La première étape part du point choisi comme étant le départ. Les
marques provisoires sont toutes inscrites dans une liste provisoire et à chaque étape
la plus petite marque provisoire devient définitive. On détermine donc à chaque
étape le chemin le plus court pour aller du départ à un des sommets du graphe. A
l’étape suivante on repart du sommet qui vient d’être marqué définitivement. On
c 2012/2013

continue ainsi jusqu’à ce qu’une étape n’entraîne la modification d’aucune marque.

Illustration :
Voici le déroulement de l’algorithme de Dijkstra pour le graphe suivant. ; . On choisit
A comme sommet de départ. Dans cet exemple on notera la marque associée à un
point entre parenthèses.
SMI-S6
Recherche Opérationnelle

Etape 0 :

Marques provisoire(s) Marque qui devient définitive à la fin de

cette étape
A(0) B(infini) C(infini) D(infini) E(infini) A (0)
F(infini) G(infini) H(infini)

Etape 1 :

En partant de A on a trois arêtes qui rejoignent B,C et D.

Chacun de ces sommets voit donc sa marque provisoire
modifiée. En effet :
6< infini d’où B change sa marque en 6,
Mohammed Berrajaa

2< infini d’où C change sa marque en 2,

4< infini d’où D change sa marque en 4.
D’autre part la marque de C devient définitive puisque c’est
la plus petite des marques provisoires à cette étape. 42

Marques provisoire(s) Marque qui devient définitive à cette

étape

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 A(0) B(6) C(2) D(4) E( infini ) C (2)

F( infini ) G( infini ) H( infini )

Etape 2 :

En partant de C on a deux arêtes qui

rejoignent E et F. Chacun de ces sommets
voit donc sa marque provisoire modifiée. En
c 2012/2013

effet :
marque (C) +distance (C, E)=3< infini d’où E
change sa marque en 3,
marque(C) +distance(C, F)=6< infini d’où F
change sa marque en 6.
La marque de E devient définitive.

Marques provisoire(s) Marque qui devient définitive à cette

SMI-S6

étape
A(0) B(6) D(4) E(3) F(6) G( infini ) H( infini E (3)
)

Etape 3 :
Recherche Opérationnelle

En partant de E on a quatre arêtes

qui rejoignent G, H, B, F. Pour ces
sommets on observe différents
cas :
pour G et H cf. étapes
précédentes,
marque(E)+distance(E,B)=4< 6
d’où B change sa marque en 4,
marque(E)+distance(E,F)=7> 6
d’où F garde sa marque provisoire
à 6,
La marque de B devient définitive.

Marques provisoire(s) Marque qui devient définitive à cette

étape
Mohammed Berrajaa

A (0) B (4) D (4) E (3) F (6) G (15) H (8) B (4)

43

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 Chapitre 3: Problèmes d’ordonnancement.

– Programmes de production.
c 2012/2013

– Lancement d’une nouvelle activité ou d’un nouveau produit.

– Construction immobilière de grands édifices (bâtiments, usines,

administrations, routes, barrages…).

– Entretien des grandes installations.

– Élaboration d’emplois du temps…

SMI-S6
Recherche Opérationnelle
Mohammed Berrajaa

44

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

45
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

46
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

47
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

48
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

49
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

50
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

51
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

52
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

53
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

54
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

55
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

56
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

57
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

58
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

59
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

60
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

61
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

62
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

63
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

64
 Mohammed Berrajaa Recherche Opérationnelle SMI-S6 c 2012/2013

Mohammed Berrajaa | Recherche Opérationnelle 2012-2013

65