Cours Théorie Des Graphes IUC

THEORIE DES GRAPHES
1 PRESENTATION
Master1
INSTITUT Universitaire de la côte
KOWO YOPO
Ulrich
Enseignant des techniques quantitatives de gestion
Date : 2024 Copyright Mai 2024 3IAC/IUC

THEORIE DES GRAPHES
2 PRESENTATION
Master1/ Chapitre 1
Cours Théorie des graphes pour étudiants

en Master1

THEORIE DES GRAPHES
3 PRESENTATION
Master1/ Chapitre 1
PLAN DU COURS
1.1- Introduction Générale
1.2- Comment Euler voit la carte?

THEORIE DES GRAPHES
4 INTRODUCTION
Master1/ Chapitre 1
OBJECTIFS DU COURS
- Histoire et evolution de la notion de
théorie des graphes
- Définir les concepts de base
- Détermination du plus court chemin

THEORIE DES GRAPHES
5 INTRODUCTION
Master1/ Chapitre 1
1- Introduction Générale
L’histoire de la théorie des graphes débute avec les
travaux du scientifique Suisse Leonard Euler ( 1707 –
1783) sur le problème devenu célèbre des ponts de
Kônigsberg ( Russie). La théorie des graphes c’est
ensuite developpé dans diverses domaines tels que: la
chimie ; la biologie ; les sciences sociales ;
l’informatique ; la physique; etc….
6 THEORIE DES GRAPHES
INTRODUCTION
Master1/ Chapitre 1
Depuis le 20𝑒 siècle cette branche constitue une discipline

à part des mathématiques.
Il faut noter que les derniers travaux sur la théorie des
graphes sont souvent effectués par les informaticiens du
fait de l’importance que l’aspect algorithmique dans leurs
données.
Date : 2024
Date : 2020 Copyright Mai
Copyright Août 2020 2024
MINESEC 3IAC/IUC IP - SCIENCE
INTRODUCTION
Master1/ Chapitre 1
Date : 2024
INTRODUCTION
Master1/ Chapitre 1
Date : 2024
INTRODUCTION
Master1/ Chapitre 1
Date : 2024
INTRODUCTION
Master1/ Chapitre 1
A quoi sert la théorie des graphes?

-Représenter un réseau social
-Représenter un réseau de transport
-Réseau informatique
-Résoudre certaines modélisations
Date : 2024
PRESENTATION
Master1/ Chapitre 1
1- GRAPHES
Date : 2024
PRESENTATION
Master1/ Chapitre 1
1.1- DEFINITION
Un graphe est un ensemble de sommets et d’arêtes qui
sont en réalité les relations entre certains de ces
sommets
Exemple:
Autrement dit :
Date : 2024
THEORIE DES GRAPHES
13 PRESENTATION
Master1/ Chapitre 1
Soit V un ensemble (fini ou infini) et E une partie de 𝑽 × 𝑽 ( i.e. une

relation sur V). Le graphe G = ( V , E ) est la donnée du couple ( V , E ).
Les éléments de V sont appelés sommets ou nœuds de G. les éléments de E
sont appelés arcs ou arêtes de G. Si V est fini , on parlera de graphe fini ( E
est alors fini et contient au plus le carré du nombre d’arcs)
1.2 – Graphes orientés
On parle de graphe orienté ou dirigé si 𝑽 = 𝒗𝒊 ; 𝒊𝝐𝑰 où I est une partie
de ℕ. Dans ce cas 𝒂 = (𝒗𝒊 ; 𝒗𝒋 ) , 𝒊 𝒆𝒕 𝒋𝝐𝑰 est un arc d’origine 𝒗𝒊 et
de destination 𝒗𝒋 pour l’arc 𝒂. On dit que 𝒗𝒊 et 𝒗𝒋 sont les
extrémités de l’arc 𝒂. 𝐛 = (𝒗𝒊 ; 𝒗𝒊 ) est une boucle de 𝒃.
Date : 2024
THEORIE DES GRAPHES
14 PRESENTATION
Master1/ Chapitre 1
Deux arcs sont dits adjacants s’ils ont au moins une

extrémité en commun.
exemple:
𝑉𝑖 𝑉𝑗
Date : 2024
THEORIE DES GRAPHES
15 PRESENTATION
Master1/ Chapitre 1
Soit 𝒂 = 𝑽𝒊 ; 𝑽𝒋 𝝐 𝑬, on dit que a est un arc sortant

de 𝑉𝑖 , ou encore un arc incident à 𝑉𝑖 vers l’extérieur
(resp un arc entrant de 𝑉𝑗 ou encore que a est un arc
incident à 𝑽𝒋 vers l’intérieur). L’ensemble des arcs
sortants de 𝑉𝑖 est noté 𝑾+ (𝑽𝒊 ) l’ensemble des arcs
entrants dans 𝑉𝑖 est noté 𝑾− (𝑽𝒊 ) l’ensemble des arcs
−
entrants dans 𝑉𝑗 est note 𝑊 (𝑉𝑗 ).
Date : 2024
THEORIE DES GRAPHES
16 PRESENTATION
Master1/ Chapitre 1
L’ensemble des arcs incidents d’un sommet v est noté 𝑊(𝑣) est on a :
𝑾 𝒗 = 𝑾+ 𝒗 ∪ 𝑾− 𝒗 on définit le demi degré sortant (resp demi-degré entrant d’un
sommet v par :𝒅+ 𝒗 = nombre d’arcs partants de 𝑣 ( resp 𝑑− 𝑣 = nombre d’arcs entrants
à 𝑣)
Si 𝐺 = (𝑉 , 𝐸) est un graphe fini alors, il est clair que : 𝑣 𝜖 𝑉 𝑑+ 𝑣 = 𝑣 𝜖 𝑉 𝑑− 𝑣
Enfin , le degré de v est 𝒅𝒆𝒈(𝒗) = 𝒅+ 𝒗 + 𝒅− 𝒗
L’ensemble des successeurs d’un somment 𝑣 est noté 𝑠𝑢𝑐𝑐 𝑣 = 𝑆1 ; 𝑆2 ; … ; 𝑆𝑘 et est
constitué des sommets si tels que (𝑣 ; 𝑆𝑖 ) 𝜖 𝑊 + (𝑣), c’est-à-dire (𝑣 ; 𝑆𝑖 ) 𝜖 𝐸. De manière
analogue, l’ensemble des prédécesseurs d’un sommet v est l’ensemble 𝑝𝑟𝑒𝑐 𝑣 =
𝑆1 ; 𝑆2 ; … ; 𝑆𝑘 des sommets 𝑆𝑖 tels que (𝑆𝑖 ; 𝑣) 𝜖 𝑊 − (𝑣) c’est-à-dire : (𝑆𝑖 ; 𝑣) 𝜖 𝐸 enfin
l’ensemble des voisins de v est simplement V 𝑣 = 𝑝𝑟𝑒𝑑 𝑣 ∪ 𝑠𝑢𝑐𝑐 𝑣 .
Si u 𝜖 𝑉(𝑣) alors on dit que u et v sont des sommets voisins ou adjacents.
Exemple : soit le graphe 𝐺 = 𝑉, 𝐸 𝑜ù 𝑉 = {𝑎, 𝑏, 𝑐, 𝑑} et
𝐸 = {(𝑎, 𝑏) ; (𝑎, 𝑒) ; (𝑏, 𝑏) ; (𝑏, 𝑐) ; (𝑐, 𝑐) ; (𝑐, 𝑑), (𝑐, 𝑒) ; (𝑑, 𝑎) ; (𝑒, 𝑎) ; (𝑒, 𝑑)}
Date : 2024
THEORIE DES GRAPHES
17 PRESENTATION
Master1/ Chapitre 1
𝐺 = (𝑉, 𝐸) est un multi graphe fini, si 𝑉 𝑒𝑠𝑡 𝑓𝑖𝑛𝑖 𝑒𝑡 𝐸 fini.
On obtient la figure: 𝑊 + 𝑎 = 𝑎, 𝑏 ; 𝑎, 𝑒 ; 𝑊 − 𝑑 = 𝑐, 𝑑 ; 𝑒, 𝑑
𝑠𝑢𝑐𝑐 𝑎 = 𝑒; 𝑑 ; 𝑠𝑢𝑐𝑐 𝑏 = 𝑏 ; 𝑐 ; 𝑝𝑟𝑒𝑑 𝐷 = 𝑐; 𝑒 𝑒𝑡 𝑣 𝑎 = 𝑏, 𝑑, 𝑒 . 𝑙𝑒𝑠 𝑎𝑟𝑐𝑠 𝑒, 𝑎 𝑒𝑡 𝑑, 𝑎 sont
adjacents. 𝑑 + 𝑐 = 3
Un multi-ensemble est un ensemble au sein duquel un même élément peut être répété plus d’une fois
Exemple : {1, 1, 2, 3} ; {1, 2, 3} 𝑒𝑡 { 1, 2, 2, 3} sont des multi – ensemble distincts. Pour distinguer les
éléments identiques utilise les indices.
Un multi – graphe 𝑮 = (𝑽 ; 𝑬) est un graphe pour lequel l’ensemble 𝐸 des 𝑎𝑟𝑐𝑠 est un multi-ensemble.
Autrement dit, il peut exister plus d’un arc reliant deux sommets donnés.
Soit 𝑃 ≥1, un P – graphe est un multi – graphe 𝐺 = 𝑉, 𝐸 pour lequel tout arc de E est répété au plus P
fois.
Un graphe 𝑮 est dit simple (ou strict) s’il ne s’agit pas d’un multi-graphe et si 𝐸 est irreflexif , c’est-à-dire
∀𝑣 𝜖 𝑉, (𝑣, 𝑣) n’appartient pas à 𝐸 (c’est-à-dire 𝐺 ne contient pas de boucle).
NB : On parle de graphe orienté ou digraphe
Date : 2024
THEORIE DES GRAPHES
18 PRESENTATION
Master1/ Chapitre 1
1. 3- Graphes non orientés
Soit 𝐺 = (𝑉 ; 𝐸) un graphe (resp un multi-graphe). Si 𝐸 a une relation symétrique sur 𝑉,
on dira que 𝐺 est un graphe (resp un multi-graphe) non dirigé ou non orienté. Autrement
dit 𝐺 est non orienté si et seulement si ∀𝑣𝑖 ; 𝑣2 𝜖 𝑉, 𝑣2 ; 𝑣2 𝜖 𝐸 => 𝑣1 ; 𝑣2 𝜖 𝐸.
Dans ce cas 𝑣1 ; 𝑣2 est représenté par un segment entre 𝑣1 𝑒𝑡 𝑣2 . Dans un graphe non
orienté l’arcs (𝑣𝑖 , 𝑣𝑗 ) 𝑒𝑡 (𝑣𝑗 ; 𝑣𝑖 ) seront représentés par {𝑣𝑖 , 𝑣𝑗 }
Soit 𝑮 = (𝑽 , 𝑬), un multi - graphe non orienté 𝑎 = 𝑣𝑖 , 𝑣𝑗 une de ses arêtes. On dit
que a est incident aux sommets 𝑣𝑖 𝑒𝑡 𝑣𝑗 . Le nombre d’arêtes incidentes au sommet 𝑣𝑖 est
le degré de 𝑣𝑖 𝑛𝑜𝑡é 𝒅𝒆𝒈 (𝒗𝒊 ).
Les boucles apportent une double contribution au degré d’un sommet.
L’ensemble des arêtes incidentes à 𝑣𝑖 se note 𝑊(𝑣𝑖 )
Date : 2024
THEORIE DES GRAPHES
19 PRESENTATION
Master1/ Chapitre 1
𝒅𝒆𝒈(𝒗𝒊 ) = nombre d’arêtes incidentes au sommet 𝒗𝒊 .
l’ordre du graphe G est le nombre de sommet V de G et sa taille est le nombre d’arêtes. Deux arêtes
sont adjacentes si elles ont au moins une extrémité en commun. Deux sommets 𝑣𝑖 ; 𝑣𝑗 𝜖𝑉 sont
adjacents si l’arête 𝑣𝑖 ; 𝑣𝑗 𝜖 𝐸. On dit aussi qu’ils sont voisins. L’ensemble des voisins de v se
note 𝑉(𝑣). Enfin, la définition d’un P-graphe est analogue à celle donnée dans le cas orienté.
Propriété: : (Handshaking Lemma) : Dans tout graphe G la somme des degrés de tous les
sommets est égale à deux fois la taille du graphe . 𝑣𝜖𝑉 deg 𝑣 = 2 𝑐𝑎𝑟𝑑𝐸
Soit 𝑲 ≥ 𝟏, un multi-graphe orienté (resp non orienté) 𝐺 = (𝑣, 𝐸) est K-régulier si pour
tout 𝑣 𝜖 𝑉, 𝑑 + 𝑣 = 𝐾 (𝑟𝑒𝑠𝑝 deg 𝑣 = 𝐾). exemple d’un graphe 3 – réguliers
Date : 2024
THEORIE DES GRAPHES
20 PRESENTATION
Master1/ Chapitre 1
Un graphe orienté (resp non orienté) est dit pondéré lorsque les arêtes (resp les
arcs) portent des poids (un nombre réel en général).
Figure :
A 14 B
Remarques :- Dans un graphe deux arêtes sont dites parallèles si elles ont la
même extrémité
- Si un graphe n’a ni arêtes parallèles , ni boucles alors ce graphe est un graphe
simple, dans le cas contraire c’est un multi- graphe
Date : 2024
THEORIE DES GRAPHES PRESENTATION
21
Master1/ Chapitre 1
1.2 Graphe complet

Un graphe est dit complet lorsque chaque sommet est relié
directement à tous les sommets du graphes.
Remarque: Dans un graphe complet le degré de chaque sommet est
égale à l’ordre du graphe moins un.
Date : 2024
THEORIE DES GRAPHES
22 PRESENTATION
Master1/ Chapitre 1
Exercice: pour chacun des graphes suivants est ce complet ou non?
a) b)
Date : 2024
THEORIE DES GRAPHES
23 PRESENTATION
Master1/ Chapitre 1
1.3 Chemin ; Circuit ; Chaîne et Cycle
Deux arêtes {u;v} et 𝑥; 𝑦 dans un graphe non orienté sont consécutives si
elles ont un sommet en commun c’est-à-dire 𝑢; 𝑣 ∩ 𝑥; 𝑦 ≠ ∅
Deux arcs 𝑢; 𝑣 et 𝑥; 𝑣 dans un graphe orienté sont dits consécutifs si
𝑣 = 𝑥 (on doit respecter l’ordre des flèches)
Un chemin dans un graphe orienté (G,E) est une suite finie d’arcs
consécutifs. Dans le cas d’un graphe non orienté on parle souvent de chaîne
Exemple: 𝐴, 𝐵 𝐵, 𝐺 𝐺, 𝐹 𝐹, 𝐷 est un chemin (ou un chaine)
Date : 2024
Date : 2020 Cop Copyright
Copyright Août 2020Mai 2024
THEORIE DES GRAPHES
24 PRESENTATION
Master1/ Chapitre 1
Propriétés des chemins:

𝑃1 - on appelle chemin de 𝑢 à 𝑣 tout chemin de la forme 𝑢 , 𝑥1 … … … . . (𝑥𝑘 , 𝑣)si le graphe
est orienté ou de la forme 𝑢 , 𝑥1 ……….. 𝑥𝑘 , 𝑣 si le graphe est non orienté.
𝑃2 − la longueur d’un chemin est le nombre d’arêtes ou d’arcs qu’il contient ( comptés avec la
multiplicité)
Un cycle ( parfois circuit dans le cas d’un graphe orienté) est un chemin d’un sommet vers lui-
même.
Remarque: un chemin sans cycle (ou sans circuit) est un chemin qui ne contient pas deux fois
le même sommet.
1.4 Graphe connexe
Un graphe est dit connexe lorsque tous les sommets du graphe sont reliés par un chemin
Si G =(V,E) est un graphe
- Si 𝐸 = ∅ , alors le graphe est dit discret
- si 𝐸 = ∅ et V= ∅ alors est un graphe nul
Date : 2024
THEORIE DES GRAPHES
25 PRESENTATION
Master1/ Chapitre 1
1.5 Chaîne Eulérien ; Cycle Eulérien

Une chaîne Eulérienne ou parcours Eulérien ou Chemin Eulérien d’un graphe
non orienté est un chemin qui passe par toutes les arêtes , une fois par arête.
Un cycle Eulérien est un chemin Eulérien fermé c’est-à-dire on part d’un
sommet on passe par toutes les arêtes une fois et on revient au sommet de
départ.
Propriétés
𝑃1 - pour qu’un graphe (G) connexe admette un cycle eulérien , il faut et il suffit
que tous les sommets de G soient de degré pair.
𝑃2 - pour qu’un graphe connexe (G) admette une chaîne eulérienne d’extrémités
A et B, il faut et il suffit que les sommets A et B soient les seuls de (G) de degré
impair
Date : 2024
THEORIE DES GRAPHES
26 PRESENTATION
Master1/ Chapitre 1
1.6 Chaîne Hamiltonienne ; Cycle Hamiltonien

Une chaine hamiltonienne est une chaîne qui passe une seule fois par chaque
sommet du graphe.
Un cycle hamiltonien est une chaîne hamiltonienne qui est cyclique.
Remarque: - la taille d’un chemin est le nombre d’arcs ou d’arêtes qui
appartiennent à ce chemin
- la longueur d’un chemin ou d’une chaîne correspond au nombres d’arcs ou
d’arêtes traversés.
Date : 2024
EXERCICE
Joël est un distributeur de logiciel informatique. Il réside au quartier KOTTO à Douala et tous les matins, il doit livrer des
logiciels dans quatre quartier à savoir : YASSA ; BONAPRISO ; AKWA et LOGBESSOU. Sachant on connait les distances
suivantes :
Quartiers Distance en Km
KOTTO YASSA 6,3Km
KOTTO BONAPRISO 14 Km
KOTTO AKWA 6,3 Km
KOTTO LOGBESSOU 12.5 Km
YASSA BONAPRISO 19 Km
YASSA AKWA 4,7 Km
YASSA LOGBESSOU 19 Km
BONAPRISO AKWA 5,6 Km
BONAPRISO LOGBESSOU 15,1 Km
AKWA LOGBESSOU 11 Km
Question : Proposez à Joël, un chemin lui permettant de livrer tous les quartiers et de retourner chez lui en
mimnisant le chemin parcouru.
27
THEORIE DES GRAPHES
28 PRESENTATION
Master1/ Chapitre 1
1.7 Exemples de familles de graphes

Une famille de graphes est un ensemble de graphes que l’on peut construire en appliquant une
certaine règle.
1.7.1 Graphes Complets
Un graphe complet à 𝑛 sommets, noté 𝐾𝑛 est un graphe pour lequel chaque sommet est voisin
de tous les autres sommets du graphe.
Ce type de graphe est utilisé pour modéliser toutes les interactions possibles entre divers
protagonistes.
Pour un graphe complet non orienté à

𝑛(𝑛−1)
n sommets il y’a : arêtes
2
Si le graphe est orienté il y’ a 𝑛(𝑛 − 1)
arêtes
Date : 2024
THEORIE DES GRAPHES
29 PRESENTATION
Master1/ Chapitre 1
1.7.2 Les chemins
Un chemin à 𝑛 sommets est un graphe connexe sans cycle où tous les sommets sont de degré
2 sauf deux qui sont de degré 1. Cette famille de graphe possède exactement 𝑛 − 1 arêtes .
La suppression d’un sommet ou d’une arête permet d’obtenir deux chemins de taille
inférieure.
0 1 2 3 4 5
Chemin de taille 5
1.7.3 Cycles
Un cycle de taille 𝑛 est un graphe connexe et dont tous les sommets sont de degré 2. On peut
le voir comme un chemin de taille 𝑛 auquel on ajoute une arête entre le premier et le dernier
sommet. Cette arête supplémentaire peut avoir un impact important sur la structure des
solutions.
Date : 2024
THEORIE DES GRAPHES
30 PRESENTATION
Master1/ Chapitre 1
3
1
Cycle de taille 5
Date : 2024
THEORIE DES GRAPHES
31 PRESENTATION
Master1/ Chapitre 1
1.7 Parcours dans un graphe
Une fois que l’on a un graphe qu’est que l’on peut en faire?
1.7.1 Algorithme de Roy - Warshall
Il calcule la fermeture transitive d’un graphe qu’il soit orienté ou non. C’est-à-dire si d’un
sommet A on va au sommet B et du sommet B on va au sommet C alors du sommet A on peut
accéder au sommet C.
1- Partant d’un graphe 𝐺 = 𝑉, 𝐴 , l’algorithme produit un second graphe 𝐺′ = 𝑉, 𝐴′ tel
qu’il existe un chemin de G allant d’un sommet 𝑢 à un sommet 𝑣 alors (𝑢, 𝑣)𝜖A′.
2- Permet de connaître l’ensemble des relations d’accessibilité au sein du graphe G
3- Complexité en 0(𝑛3 )
Date : 2024
THEORIE DES GRAPHES
32 Parcours dans un graphe
Master1/ Chapitre 2
CHAPITRE 2:
PARCOURS DANS UN GRAPHE
Date : 2024
THEORIE DES GRAPHES Parcours dans un graphe
33
Master1/ Chapitre 2
PLAN DU COURS
- OBJECTIFS
- Algorithme de Dijkstra
- Problèmes de transport
Date : 2023
34
Master1/ Chapitre 2
OBJECTIFS DU COURS
- Déterminer l’utilité d’un graphe
- Définir un sous - graphe
- Utiliser certains algorithme pour résoudre des
problèmes
Date : 2024
35
Master1/ Chapitre 2
Recherche du plus court chemin

Supposons que nous disposons un graphe pondéré. Comment determiner
un plus court chemin?
exemple: 1- comment fonctionne votre GPS?
2- comment fonctionne google Maps?
3- comment determiner le plus court chemin entre deux adresses?
Nous allons voir dans cette partie comment determiner le plus court
chemin entre deux sommets d’un graphe pondéré pour lequel les sommets
peuvent représenter des villes ou des intersections , les arcs peuvent
représenter des routes existantes et le poids d’un arc la distance à parcourir
Date : 2024
36
Master1/ Chapitre 2
2.1 Rappel sous – graphe

*Soit G un graphe . Un graphe H est appelé sous – graphe d’un graphe
d’un graphe G, si H est identique à G ou si H est obtenu par
suppression certains sommets et/ou de certaines arêtes de G.
• Un sous – graphe H d’un graphe G est stable lorsqu’il ne contient
aucune arête. Le degré de tous les sommets est donc zéro.
• Un sous – graphe H d’un graphe G est complet, lorsqu’il est
simple et ses sommets sont deux à deux adjacents.
• Un graphe H est appelé graphe partiel d’un graphe G, si H est
obtenu de G par suppression de certaines arêtes de G.
Date : 2024
37
Master1/ Chapitre 2
1 6
3
4
Graphe G
Date : 2024
38
Master1/ Chapitre 2
1 6
3
4
Sous- Graphe de G
Date : 2024
39
Master1/ Chapitre 2
1 6
2 5
3 4
Sous- Graphe stable de G
Date : 2024
40
Master1/ Chapitre 2
1 6
Sous- Graphe complet de G
Date : 2024
41
Master1/ Chapitre 2
Théorème: ( Lemme des poignées de mains)

La somme de des degrés d’un graphe est égale à deux fois le nombre
d’arêtes.
Autrement dit soit un graphe G = (V;E) , pour tout 𝑉 et 𝑑𝑣 le degré du
sommet 𝑣 on a: 𝑣𝜖𝑉 𝑑𝑣 = 2𝑐𝑎𝑟𝑑𝐸
Propriété: Un graphe simple a un nombre pair de sommets de degré impair.
Date : 2024
42
Master1/ Chapitre 2
2.1.2 Recherche du plus court chemin

Un graphe valué est un graphe pour lequel chaque arête est à un
nombre réel appelé poids ou valuation. Si ce nombre est positif, on
parle de graphe pondéré.
Remarque: tout graphe peut être considéré comme un graphe valué
ou pondéré pour lequel chaque arête a un poids de 1.
Le poids d’un chemin d’un graphe est la somme des poids des arêtes
du chemin.
Date : 2024
43
Master1/ Chapitre 2
Exemple: un taximan de la ville de Douala doit partir d’un point A

pour un point B. Le circuit routier de ce taxi est modélisé par le
graphe ci - dessous. Chaque tronçon est marqué par la distance entre
les deux extrémités du chemin.
E
D
F F
le poids du chemin A,F,C,D est
A égal à 1+3+2 = 6
C
B
Date : 2024
44
Master1/ Chapitre 2
On appelle arbre tout graphe connexe sans cycle.

Dans un arbre tout sommet de degré 1 est appelé sommet pendant ou
feuille.
Un arbre couvrant d’un graphe connexe G est un arbre qui est un
sous – graphe de G et qui contient chaque sommet de G.
Date : 2024
45
Master1/ Chapitre 2
Exemple:
2 1
3 6
4 5
Un arbre et 1,2,5 sont des feuilles
Date : 2024
46
Master1/ Chapitre 2
Exemple:
2 1
3 5
Graphe G
Date : 2024
47
Master1/ Chapitre 2
Exemple:
2 1
3 5
Arbre couvrant de G
Date : 2024
48
Master1/ Chapitre 2
Théorème1: les affirmations suivantes sont équivalentes pour tout

graphe G à n sommets.
• G est un arbre
• G est connexe
• G est connexe et comporte n-1 arêtes
• Chaque paire 𝑢, 𝑣 de sommets est relié par une seule chaîne simple
Théorème 2: un graphe est connexe si et seulement s’il contient un
arbre couvrant.
Théorème 3: Dans graphe pondéré G, on peut trouver un arbre
couvrant de poids total minimum .
Date : 2024
49
Master1/ Chapitre 2
2.2 Algorithme de parcours en largeur

Nous donnons ici les différentes étapes de l’algorithme de parcours en
largeur pour la détermination d’un arbre couvrant.
2.2.1 Algorithme (BFS ou Bread First Search)
1- choisissez un sommet de départ S et étiquetez - le 0
2- Trouvez tous les sommets adjacents à S et étiquetez les 1
3- trouvez chaque sommet marqué d’un 1 , trouvez une arête qui le
relie au sommet étiquetez 0.
Assombrir cette arête
4- Recherchez les arêtes non étiquetés adjacents à ceux avec
l’étiquette 1 et étiquetez les 2. Pour chaque sommet étiqueté 2 ,
Date : 2024
50
Master1/ Chapitre 2
Pour chaque sommet étiqueté 2 , trouvez une arête qui le relie au

sommet étiqueté 1. Assombrir cette arête. S’il existe plus d’une arête
choisissez en une arbitrairement.
5- continuez ce processus jusqu’à ce qu’il n’y’ait plus de sommets sans
étiquette adjacents à ceux étiquetés.
Si tous les sommets du graphe ne sont pas étiquetés, alors il n’existe
pas d’arbre couvrant pour le graphe.
Si tous les sommets sont étiquetés, alors les sommets et les arêtes
assombries forment un arbre couvrant pour le graphe.
Date : 2024
51
Master1/ Chapitre 2
Exemple: Déterminons un arbre couvrant du graphe suivant en

utilisant l’algorithme BFS
e f
d
a h g
b
c
Graphe G
Date : 2024
52
Master1/ Chapitre 2

e f
2
d
a h g
0
b
c
Date : 2024
53
Master1/ Chapitre 2

e f
d
a g
h
b
c
Date : 2024
54
Master1/ Chapitre 2
2.1.3 Algorithme de Prim

Principe:
1- trouvez l’arête avec le plus petit poids dans le graphe. L’assombrir et
encerclez ses deux sommets. Les liens sont rompus arbitrairement.
2- Trouvez l’arête avec les plus petit poids parmi les arêtes non
assombris restants et ayant un sommet encerclé et un sommet non
encerclé. Assombrir cette arête et son sommet non encerclé.
3- répétez l’étape 2 jusqu’à ce que tous les sommets soient encerclés.
Date : 2024
55
Master1/ Chapitre 2
Exemple: Déterminons un arbre couvrant de Poids minimal avec Prim

2 B 1 D
A 5
G
2
1
3
C 5
F
1
3
E
Date : 2024
56
Master1/ Chapitre 2
2.1.4 Algorithme de Kruskal

Principe:
1- trier les arêtes par poids croissants
2- Ajouter les arêtes à celle de poids minimal toute en évitant de créer
un cycle
Ainsi de suite
Date : 2024
57
Master1/ Chapitre 2
Exemple: Déterminons un arbre couvrant de Poids minimal avec

L’algorithme de Kruskal
2 B 1 D
A 5
G
2
1
3
C 5
F
1
3
E
Date : 2024
58
Master1/ Chapitre 2
2.1 Recherche du plus court chemin

Trouver le chemin le plus court allant d’un point A à un point B peut être
considéré de trois manières différentes:
- Plus court chemin entre deux sommets du graphe
- Plus court chemin d’un sommet vers tous les autres
- Plus court chemin de chaque sommet vers les autres
Date : 2024
THEORIE DES GRAPHES
59 PRESENTATION
Master1/ Chapitre 1
2.1 RECHERCHE DU PLUS COURT CHEMIN : Algorithme de Dijstra
L’Algorithme de Dijkstra permet de déterminer le chemin le plus court entre deux sommets
dans un graphe pondéré.
Exemple: soit le graphe ci – dessous:
1
2 B D
5
A Déterminons le chemin le
G
2 plus court entre A et G
1
3 3 en utilisant l’algorithme de
2
Dijstra
C 5
F
3 1
Date : 2024
THEORIE DES GRAPHES
60 PRESENTATION
Master1/ Chapitre 1
Dans un premier temps construisons un tableau à partir de tous les sommets du graphe:
A B C D E F G
0 2A 1A
3C 4C 4C 6C
2A
3B 5B
4C
6D 9D 8D
4C 6C
5E
7F
je fais le chemin inverse pour trouver le chemin le plus court. On obtient : A-C-E-F-G
Le poids est donc : 1+3+1+2 = 7
Date : 2024
THEORIE DES GRAPHES
61 PRESENTATION
Master1/ Chapitre 1
EXERCICE
Une région est munie d’un réseau de trains, représenté par le graphe (G) ci- dessous :
B E
21
10
D G
31
A
25
F
C
Date : :2020
Date 2024 Copyright Mai
Copyright Août 20202024
THEORIE DES GRAPHES
62 PRESENTATION
Master1/ Chapitre 1
EXERCICE
Les stations sont symbolisées par les sommets : A, B, C, D, E, Fet G. Chaque arête
représente une ligne liant deux gares. Les temps de parcours (correspondance
comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe.
Déterminer un arbre couvrant de poids minimal par l’algorithme de votre choix
Déterminer le plus court chemin en minutes, reliant la gare A à la gare G.
Justifier votre réponse grâce à un algorithme.
Quelle est la longueur en minutes de ce chemin ? quel est ce chemin ?
Date : 2024
63
Master1/ Chapitre 2
2.2 PLOBLEMES DE TRANSPORT

Objectifs: Avoir une vision éclairée de ce qui peut se passer lorsqu’on
prend les transports en commun
2.2.1 – Introduction
De nombreux problèmes peuvent être modélisés par un problème de
flots , c’est-à-dire calculer la quantité de fluide pouvant transiter sur
un réseau dont les capacités sont limitées.
Par exemple:
- Distribution d’eau dans un réseau de canalisation, transport de
pétrole sur un pipeline
..
Date : 2024 Copyright
Copyright Mai
Août 2020 2024
64
Master1/ Chapitre 2
- Système de transports dans une grande ville ( les passagers sont

considérés comme flux)
- Transport d’énergie électrique sur un réseau électrique
- Débit de données sur le réseau d’un opérateur
Date : 2024
65
Master1/ Chapitre 2
2.2.2 Réseau de transport et Flots

a – Réseau de transport
Un réseau de transport peut – être vu comme un graphe orienté , dans
lequel chaque arc est associé à une quantité maximum de flot pouvant
le traverser à un instant donné.
Un réseau de transport est un graphe 𝐺 = (𝑉, 𝐴, 𝑠, 𝑡) tel que chaque
arc (𝑢, 𝑣) possède une capacité 𝑐(𝑢, 𝑣). Un réseau de transport
possède également deux sommets particuliers généralement notés
𝑠(𝑠𝑜𝑢𝑟𝑐𝑒) et 𝑡(𝑙𝑒 𝑝𝑢𝑖𝑡)tel que 𝑊 − 𝑠 = 𝑂 et 𝑊 + 𝑡 = 𝑂
la source produit autant de flux et le puit l’absorbe.
Date : 2024
66
Master1/ Chapitre 2
Exemple : Pour plus de simplicité, on suppose que :

- Notre graphe est connexe
- Tous les sommets du graphe se trouve sur un chemin reliant 𝑠 à 𝑡 .
12
4 5
4 9
10
S 7 t
2 3
14
Question: Quelle est la quantité maximale de flots que l’on peut faire passer sur notre réseau?
Date : 2024
THEORIE DES GRAPHES
67
Master1/ Chapitre 2
b – Fonction flot
Un flot est une fonction 𝑓, appliquée à un réseau de transport
𝐺 = 𝑉, 𝐴, 𝐶, 𝑠, 𝑡 , qui associe à chaque arc (𝑢, 𝑣) une valeur 𝑓(𝑢, 𝑣)
qui respecte les trois propriétés suivantes:
1- contrainte de capacité : pour tout arc (𝑢, 𝑣) , 𝑓 𝑢, 𝑣 ≤ 𝐶(𝑢, 𝑣)
c’est-à-dire la quantité transportée doit être inférieure à la capacité de
l’arc.
2- Symétrie : pour tout couple de sommets (𝑢, 𝑣) , 𝑓 𝑢, 𝑣 = −𝑓(𝑣, 𝑢)
c’est-à-dire avoir un flot qui va de 𝑢 vers 𝑣 revient à dire que l’on a un flot
négatif de même valeur qui va de 𝑣 vers 𝑢.
Date : 2024
68
Master1/ Chapitre 2
3- Conservation du flot: pour tout sommet autre que 𝑠 ou 𝑡 , la somme

des flots entrants est égale à la somme des flots sortants c’est-à-dire on
a autant qui entre que celle qui sort. Il y’a pas de création de flux, ni
disparition spontanée du flux sur un sommet. Donc si on ne peut pas
faire sortir un flux alors il ne peut pas entrer.
Exemple: 12
12
4 5
11 15
16 20
1
4 7
10
S 4 7
9 t
0
8
13 4
4
2 3
11
14
Date : 2024
69
Master1/ Chapitre 2
En prenant le sommet 2 la quantité qui entre est 12 et celle qui sort est
12
Un flot réalisable est un flot où pour tout arc du réseau de transport , la
valeur du flot ne dépasse pas la capacité de l’arc.
Flot Réalisable Flot non réalisable
15
12 12
4 12 5 11 4 5
16 15
15 20
20 1
10
1
10
7 S 4 4 7
S 4 4 7 t
0
7 t 9
0
9
8 8 4
13 4 13 2 4
2 4 3
3 11
11 14
14
Date : 2024
70
Master1/ Chapitre 2
Quand deux arcs en sens inverse relient deux sommets , on peut toujours annuler la fonction
flot sur l’un des arcs.
Exemple de deux arcs inverses , Les deux mêmes arcs après

l’un avec un flot de 11 et l’autre annulation du flot sur l’un
avec un flot de 4. d’entre eux
Date : 2024
71
Master1/ Chapitre 2
c- Saturation d’un arc

Lorsqu’un flot passant par un arc (𝑢, 𝑣) atteint la capacité, on dit que
cet arc est saturé.
La valeur d’un flot , est égale à la somme des flots sortants du sommet
𝑠, ou bien de manière équivalente, à la somme des flots entrants au
sommet 𝑡. ( Propriété de conservation des flots)
Tout ce qui sort de 𝑠 entre en 𝑡.
Date : 2024
72
Master1/ Chapitre 2
2.2.3 – Coupe minimum

On considère un réseau de transport G = (𝑉, 𝐴, 𝐶, 𝑠, 𝑡).
Une coupe est une séparation des sommets en deux sous – ensembles A
et B, tels que : 𝑠𝜖𝐴 ; 𝑡𝜖𝐵 et 𝐵 = 𝑉/𝐴
Exemple :
A B
Date : 2024
73
Master1/ Chapitre 2
La capacité d’une coupe est la somme des capacités des arcs qui vont du 1er ensemble vers le
second ensemble, c’est-à-dire la somme des capacités des arcs allant de A vers B.
𝐶 𝐴, 𝐵 = 𝑖𝜖𝐴 ,𝑗𝜖𝐵 𝐶(𝑖, 𝑗)
Pour l’exemple ci – dessus la capacité de cette coupe est 𝐶 𝐴, 𝐵 = 12 + 14 = 26
Etant donné une coupe séparant les sommets en deux ensembles A et B. La somme des
valeurs du flot des arcs allant de A vers B moins la somme des valeurs du flot des arcs allant de
B vers A est appelé flot net traversant la coupe.
Remarque: Le flot net traversant la coupe ne dépend pas de la coupe .
12
12
A 11
4 5
15
B
16 20
1
10
S 4 4 7
7 t
0
9
8 4
13 4
2 3
11
14
Date : 2024
74
Master1/ Chapitre 2
Le flot net vaut : 12+11-4=19
Remarque: Le flot net traversant la coupe ne dépend pas de la coupe .

pour l’exemple ci – dessus le flot net vaut 12 + 14 – 4 = 19
Théorème de Ford – Fulkerson
Pour tout flot F de valeur 𝑉(𝐹) , et pour toute coupe 𝐴, 𝐵 de capacité 𝐶(𝐴, 𝐵) on a:
𝑉(𝐹) ≤ 𝐶(𝐴, 𝐵)
Une coupe (𝐴, 𝐵) est dite minimale pour un flot F si tous les arcs allant de A vers B sont
saturés et aucun arc de B vers A n’est saturé.
Date : 2024
75
Master1/ Chapitre 2
Théorème : ( coupe minimale)

S’il existe une coupe minimale pour un flot F alors ce flot est
maximal
En utilisant ce théorème , que pouvez vous en déduire à propos du
flot suivant? 𝟏𝟐
𝟏𝟐
4 5
𝟏𝟐 𝟏𝟗
𝟏𝟔 𝟐𝟎
𝟎
𝟒 𝟕
10
𝟒 𝟕
S 𝟗 t
0
𝟏𝟏
𝟏𝟑 𝟒
𝟒
2 3
𝟏𝟏
𝟏𝟒
Est – il maximal ou pas?

Date : 2024
76
Master1/ Chapitre 2
2.2.4 – Graphe Résiduel

Etant donnés un réseau de transport et un flot associé , le graphe résiduel correspond au
graphe représentant la quantité de flot pouvant être ajouté ou retiré sur chaque arc. On peut
le construire de la manière suivante:
1- on utilise le même ensemble de sommets du graphe
2- pour chaque arc 𝒇(𝒖, 𝒗) ≤ 𝑪(𝒖, 𝒗) , on peut augmenter le flot 𝑪 𝒖, 𝒗 − 𝒇(𝒖, 𝒗) et on
peut diminuer de 𝒇(𝒖, 𝒗) , ce qui revient à faire passer un flot −𝒇(𝒖, 𝒗) sur un arc (𝒖, 𝒗)
2.2.5 – Chemin augmentant

Pour un réseau de transport associé à un flot , un chemin augmentant est un chemin allant de
𝑠 à 𝑡 dans un graphe résiduel.
Un chemin augmentant 𝑃 déterminé d’un graphe résiduel 𝐺𝑟 calculé à partir d’un réseau de
transport 𝐺 associé à un flot 𝑓peut être vu comme la possibilité d’augmentation du flot 𝑓 en
modifiant la valeur du flot sur les arcs de 𝑃 dans 𝑓.
Date : 2024
77
Master1/ Chapitre 2
Afin de conserver un flot réalisable, ces arcs ne peuvent être augmentés

que de la valeur minimale des capacités du graphe résiduelle de 𝑃
Exemple :
Flot Graphe résiduel associé

12
12 12
4 5 4 5
11 19
16 20
3 9
10
1
4 7
10
S 0 7 S 7 t
9 t
0
8
13 4
4 2 3
2 3
7 7
14
Date : 2024
78
Master1/ Chapitre 2
Existe-t-il un chemin allant de 𝑠 à 𝑡?

Le graphe résiduel modélise la capacité de changement.
2.2.6 – Déroulement de l’algorithme de Ford – Fulkerson
Considérons le réseau de transport suivant:
12
4 5
4 9
10
S
7
t
2 3
14
Date : 2024
79
Master1/ Chapitre 2
2-2-7 Couplage
Le couplage d’un graphe est un ensemble d’arêtes deux à deux non
adjacentes. Un couplage est dit maximal lorsqu’on ne peut plus ajouter
d’arêtes dans le couplage. Un couplage est dit maximum lorsqu’il
n’existe pas d’autres couplages contenant plus d’arêtes.
Date : 2024
80
Master1/ Chapitre 2
Exercice d’application
4
A B
2 8
S 6
t
C D
9
Déterminer le flot maximal
Date : 2024
81
Master1/ Chapitre 2
2-3 Graphes planaires

Un graphe planaire est un graphe ayant une représentation dans le plan
sans croisement d’arêtes sur le plan.
Exemple :
Graphe complet d’ordre 4 et planaire
Date : 2024
82
Master1/ Chapitre 2
considérons un graphe planaire connexe et dessiné de manière planaire

Une face est une zone du plan tel que prenant deux points quelconques
on peut les relier de manière continue grâce à une courbe continue par
forcément droite qui ne croise aucune arête et aucun sommet.
Exemple :
B
𝐹5
A
𝐹1 𝐹3
𝐹2
D E
C
𝐹4
Date : 2024
83
Master1/ Chapitre 2
𝐹1 , 𝐹2 , 𝐹3 et 𝐹4 sont les faces internes alors que 𝐹5 est une face externe infinie.
Posons : 𝑛 = nombre des sommets
𝑚= le nombre d’arêtes
𝑓= nombre de faces
Pour l’exemple précédent on a : 𝑛 = 6; 𝑚 = 9 𝑒𝑡 𝑓 = 5
Formule d’Euler : D’après Euler le nombre de sommets plus le nombre
de faces diminuer du nombre d’arêtes est égal à 2. c’est-à-dire:
𝑛−𝑚+𝑓 =2
Exemple:
Date : 2024
84
Master1/ Chapitre 2

85
Master1/ Chapitre 2
Pour l’exemple precedent on a : 𝑛 − 𝑚 + 𝑓 = 7 − 6 + 1 = 2

Petite reflexion: on dispose de trois maisons et en face d’elles on a une source
d’eau , une source de gaz et une source d’électricité. Peut – on connecter
chacune des maisons à chacune des sources en creusant des tranchées de sorte
que les tranchées ne se croisent pas?
Propriété: Tout graphe planaire contient un sommet de degré au plus 5.
Date : 2024
86
Master1/ Chapitre 2
2.4 Coloration d’un graphe

2.4.1 – Coloration des arêtes
Soit G = (V,E) graphe non orienté. Colorer les arêtes de G consiste à donner à
chaque arête des couleurs de telle sorte que deux arêtes ayant un sommet en
commun n’ont pas la même couleur.
Exemple : soit le graphe suivant :
Bb c
a
d
g f e
Date : 2024
87
Master1/ Chapitre 2
On commence par f qui est de degré maximal 5
Bb c
a
d
g f e
On obtient une coloration vérifiant toutes les conditions du graphe précédent.
Date
Date : :2020
2024 Copyright Mai
88
Master1/ Chapitre 2
Exercice : supposons que l’on veut planifier des rencontres. On prévoit un certain
tête à tête de durée 1h à partir de 8h
Paul Noé
Nora
Isa
Fred Léa
Date : 2024
89
Master1/ Chapitre 2
Exercice : supposons que l’on veut planifier des rencontres. On prévoit un certain
tête à tête de durée 1h à partir de 8h
08h – 09h Fred – Isa
Nora – Paul
Léa – Noé
09h – 10h Fred – Noé

Paul Noé Nora – Isa
10h – 11h Fred - Nora

Nora
Isa
11h – 12h Fred – Léa

Fred Léa
Date : 2024
90
Master1/ Chapitre 2
Planifier des rencontres revient donc à faire une coloration du graphe :
On appelle ColArOpt(G) le nombre minimale de couleurs utiliser pour colorier les

arêtes de G
Soit ∆ le degré maximal de G , les arêtes issues de ce sommet doivent avoir des
couleurs différentes. D’où ColArOpt(G) ≥ ∆
Si G est biparti de degré max ∆ alors ColArOpt(G) = ∆ (KÖNIG en 1916)
Date : 2024
91
Master1/ Chapitre 2
Remarque : Il est pas toujours possible de colorier un graphe avec ∆ couleurs.

Contre exemple:
Nous sommes en présence d’un cycle à 5 sommets ( un C(5)) avec ∆= 2

ColArOpt(C(5)) = 3 = ∆ + 1
De façon générale d’après VIZING ( année 60) , si G est un graphe de degré max
∆ alors: ∆≤ ColArOpt(G) ≤ ∆ + 1. le nombre de couleurs optimal est donc soit ∆,
soit ∆+1
Date : 2024
92
Master1/ Chapitre 2
2.4.2 – Coloration des sommets
Soit G = (V,E) graphe non orienté. Colorer les sommets de G consiste à donner à
chaque sommet des couleurs de telle sorte que deux sommets ayant une arête en
commun n’ont pas la même couleur.
Algorithme de Welsh – Powell
Cet algorithme fournit une coloration explicite du graphe et donne donc un
majorant du nombre chromatique du graphe, c’est-à-dire un nombre suffisant de
couleurs pour colorier le graphe.
Principe:
1- Ranger les sommets dans l’ordre décroissant des degrés
2- Tant que tous sommets ne sont pas colorés :
• Considérer une couleur K , différente des couleurs déjà utilisées
• Considérer le premier sommet non encore coloré dans l’ordre croissant des degrés et lui
Date : 2024
93
Master1/ Chapitre 2
affecter la couleur K
• Considérer chacun des autres sommets non colorés dans l’ordre décroissant
des degrés
- s’il est adjacent à un sommet déjà coloré K, ne lui affecter aucune couleur
- Sinon lui affecter la couleur K
3- L’algorithme est terminé dès que tous les sommets sont colorés
Exemple
Date : 2024
94
Master1/ Chapitre 2
A
G
E
D
Date : 2024
95
Master1/ Chapitre 2
A
G
Sommets B C D E F A G
B Degré 4 4 2 2 2 1 1
Rouge oui oui

F
Vert oui oui oui
C
bleu oui oui
E
D
Date : 2024
96
Master1/ Chapitre 2
2.4.3 – Coloration totale

Soit G = (V,E) un graphe non orienté
Une coloration totale a pour but de colorier chaque sommet et chaque arête sous
les contraintes suivantes:
1- Deux sommets voisins n’ont pas la même couleur
2- Deux arêtes avec une extrémité commune n’ont pas la même couleur
3- un sommet et ses arêtes n’ont pas la même couleur
L’objectif est d’utiliser le plus petit nombre de couleurs noté 𝜒′′(𝐺).
Exemple :
Date : 2024
97
Master1/ Chapitre 2
5 3
2
7
6
1 4
Date
Date: 2020
: 2024 Copyright
Copyright AoûtMai
2020 2024
98
Master1/ Chapitre 2
Le sommet de degré maximal est 6

5 3
2
7
6
1 4
Date : 2024
THEORIE DES GRAPHES Graphe probabiliste
99
Master1/ Chapitre 3
CHAPITRE 3:
GRAPHE PROBABILISTE
Date : 2024
Master1/ Chapitre 3
100
OBJECTIFS DU COURS
- Définir graphe probabiliste
- Reconnaitre un etat probabiliste
- Reconnaitre une matrice de transition et un
etat stable
Date : 2024
2020 MINESEC 3IAC/IUC IP - SCIENCE
Master1/ Chapitre 3
101
3.1 – Présentation
Un graphe probabiliste est un graphe orienté et pondéré dans lequel:
• Il y’a au plus un arc d’un sommet à un autre
• La somme des poids des arcs issus d’un même sommet est égale à 1.
Remarques:
1- les poids des arcs sont alors des probabilités ( nombres compris entre 0 et 1)
2- un graphe probabiliste indique les différents états possibles d’un système (
sommets du graphe) et les probabilités de passage d’un état à l’autre ( poids des arcs).
Exemple
• Le graphe 𝑛0 1 est un graphe probabiliste d’ordre 2
• Le graphe 𝑛0 2 est un graphe probabiliste d’ordre 3
• Le graphe 𝑛0 3 n’est un graphe probabiliste car la somme des poids des arcs
issus du sommet C est égale à 0,9 et non
Date : 2024
Master1/ Chapitre 3
102
Schéma :
𝑀1
Graphe 𝒏 𝟏 𝟎 Graphe 𝒏𝟎 𝟐
Date : 2024
Master1/ Chapitre 3
103
Schéma :
Graphe 𝒏𝟎 3
Date : 2024
Master1/ Chapitre 3
104
3.2 – Etat probabiliste et matrice de transition
Soit une expérience aléatoire à deux issues possibles A et B.
A chacune de ces issues est affectée une probabilité 𝑃𝐴 et 𝑃𝐵 . Lorsque l’on répète
cette expérience, dans les mêmes conditions , on se retrouve après chaque
réalisation dans un donné. Cet état à l’issue de chacune des réalisations de
l’expérience est appelé état probabiliste.
Il peut être représenté par la matrice ligne 𝑃𝑛 = (𝑎𝑛 𝑏𝑛 ) qui traduit la probabilité
d’obtenir l’issue A ou l’issue B après 𝑛 réalisations de l’expérience aléatoire. On a
𝑎𝑛 + 𝑏𝑛 = 1 , pour tout entier naturel 𝑛.
Remarque: on généralise sans difficulté cette définition à une expérience
aléatoire ayant un nombre 𝑛 fini d’issues possibles (𝑛 ≥ 2).
Date : 2024
Master1/ Chapitre 3
105
Soit G un graphe probabiliste d’ordre 𝑛 dont les sommets sont numérotés de 1 à 𝑛
La matrice de transition 𝑀 de G est la matrice carrée d’ordre 𝑛 telle que 𝑚𝑖𝑗
est égal à la probabilité portée par l’arc reliant le sommet 𝑖 au sommet 𝑗 s’il existe
ou 0 sinon.
Date : 2024
Master1/ Chapitre 3
106
Remarque : la matrice transition 𝑀 permet d’étudier l’évolution du système que
schématise le graphe probabiliste .
Exemple :
• La matrice transition 𝑀1 associé au graphe ci – dessous est ( en supposant les
0,55 0,45
sommets rangés dans l’ordre alphabétique): 𝑀1 =
0,8 0,2
Date : 2024
Master1/ Chapitre 3
107
• La matrice transition 𝑀2 associée au graphe ci – dessous ( en supposant les
0,75 0,1 0,15
sommets rangés dans l’ordre alphabétique): est 𝑀2 = 0,4 0,4 0,2
0,6 0,1 0,3
Date : 2024
Master1/ Chapitre 3
108
Propriété1
Soit 𝑀 la matrice transition d’un graphe probabiliste associé à un système donné.
Soit 𝑃0 la matrice ligne décrivant l’état initial du système étudié.
Soit 𝑃𝑛 la matrice ligne décrivant l’état probabiliste à l’état 𝑛 du système étudié
On a les relations suivantes:
𝑃𝑛+1 = 𝑃𝑛 × 𝑀
Démonstration (pour un graphe d’ordre 2)
𝛼 1−𝛼
Soit un graphe probabiliste d’ordre 2 de matrice transition 𝑀 = 𝛽 1 − 𝛽
• Soit 𝐴𝑛 l’évènement : « on obtient A à l’étape 𝑛 »
• Soit 𝐵𝑛 l’évènement : « on obtient B à l’étape 𝑛 »
• Soit 𝑃𝑛 = (𝑎𝑛 𝑏𝑛 ) la matrice ligne décrivant l’état probabiliste à l’étape 𝑛
• Soit 𝑃𝑛+1 = (𝑎𝑛+1 𝑏𝑛+1 ) la matrice ligne décrivant l’état probabiliste à l’étape 𝑛 + 1
Date : 2024
Master1/ Chapitre 3
109
On considère l’arbre pondéré suivant:
Etape 𝑛 𝑩𝒏+𝟏
Etape 𝑛 + 1
Date : 2024
110
Master1/ Chapitre 3
On a les relations(formule des probabilités totales) :
𝑎𝑛+1 = 𝑃 𝐴𝑛+1 = 𝑃𝐴𝑛 𝐴𝑛+1 × 𝑃 𝐴𝑛 + 𝑃𝐵𝑛 𝐴𝑛+1 × 𝑃 𝐵𝑛 = 𝛼𝑎𝑛 + 𝛽𝑏𝑛
𝑏𝑛+1 = 𝑃 𝐵𝑛+1 = 𝑃𝐴𝑛 𝐵𝑛+1 × 𝑃 𝐴𝑛 + 𝑃𝐵𝑛 𝐵𝑛+1 × 𝑃 𝐵𝑛 =
(1 − 𝛼)𝑎𝑛 + (1 − 𝛽)𝑏𝑛
Cela se traduit en écriture matricielle par : 𝑃𝑛+1 = 𝑃𝑛 × 𝑀
𝑃1 = 𝑃0 × 𝑀
𝑃2 = 𝑃0 × 𝑀 × 𝑀 = 𝑃0 × 𝑀²
𝑃3 = 𝑃2 × 𝑀² × 𝑀 = 𝑃0 × 𝑀3
…………………….............................................
………………………………...............................
𝑃𝑛 = 𝑃𝑛−1 × 𝑀 = 𝑃0 × 𝑀𝑛−1 × 𝑀 = 𝑃0 × 𝑀𝑛
Date : 2024
111
Master1/ Chapitre
Remarque : la matrice 𝑀𝑛 permet de trouver l’état probabiliste à l’étape 𝑛.
Exemple: les joueurs d’un club de football sont partagés en deux équipes : une
équipe A et une équipe B. l’entraîneur change la composition de ces équipes après
chacun des matchs , suivant les performances des joueurs.
Une étude statistique menée au cours des saisons précédentes permet d’estimer
que:
• Si un joueur fait partie de l’équipe A , la probabilité qu’il reste dans cette
équipe pour le match suivant est de 0,6.
• Si un joueur fait partie de l’équipe B , la probabilité qu’il change d’équipe le
match suivant est de 0,2.
La situation précédente peut être schématisé par le graphe probabiliste ci –
dessous:
Date : 2024
112
Master1/ Chapitre
0,6 0,4
M=
0,2 0,8
Date : 2024
113
Master1/ Chapitre 3
Pour tout entier naturel 𝑛 donné, 𝑃𝑛 = 𝑎𝑛 𝑏𝑛 la matrice ligne décrivant l’état
probabiliste lors du match 𝑛.
Enzo vient d’arriver dans le club et la probabilité 𝑎0 qu’il joue dans l’équipe A
pour le match de préparation est ( match 0) est 0,1.
• L’état probabiliste initial est donc 𝑃0 = (0,1 0,9)
• On a donc par exemple 𝑃1 = 𝑃0 × 𝑀 = (0,24 0,76)
La probabilité 𝑎1 qu’Enzo joue dans l’équipe A pour le match 1 est 0,24.
• On a aussi, 𝑃2 = 𝑃0 × 𝑀² = (0,296 0,704)
La probabilité 𝑎2 qu’Enzo joue dans l’équipe A pour le match 2 est 0,296
Date : 2024
114
Master1/ Chapitre 3
3.3 Etat stable
Soit un graphe probabiliste d’ordre 𝑛 associé une expérience donnée.
On appelle état stable un état probabiliste qui n’évolue pas lors de la répétition de
l’expérience
Exemple :
0,7 0,3
Soit l’état initial 𝑃0 = 0,4 0,6 et la matrice de transition M =
0,2 0,8
On vérifie aisément que 𝑃1 = 𝑃0 et que de proche en proche que , 𝑃𝑛 = 𝑃0 pour
tout entier naturel 𝑛
L’état décrit par la matrice 𝑃0 est donc stable.
Date : 2024
115
Master1/ Chapitre 3
Propriété 2
Soit un graphe probabiliste d’ordre 2 dont la matrice ne comporte pas de 0. l’état
probabiliste 𝑃𝑛 à l’étape 𝑛 converge vers un état P indépendant de l’état initial 𝑃0
Cet état est appelé état stable du système : il vérifie l’égalité 𝑃 × 𝑀 = 𝑃
Date : 2024
THEOàRIE DES GRAPHES Graphe probabiliste
116
Master1/ Chapitre 3
3.4 Chaîne de Markov
Considérons les trois exemples suivants:
A- Modèle de météo: on suppose que dans une région s’il pleut un jour eh bien
le lendemain il pleut dans 70% des cas, par contre s’il ne pleut pas un certain jour
le lendemain il ne pleut que dans 20% des cas. On appelle 𝑋𝑛 la variable aléatoire
qui prend la valeur 1 s’il pleut et 2 s’il ne pleut pas après 𝑛 jours. Ainsi si :
𝑋0 = 1 alors on peut avoir 𝑋1 =1 et 𝑋2 =2 etc……..
B- on a une puce qui se déplace aléatoirement sur les sommets d’un carré ABCD.
Chaque seconde elle saute l’un des sommets voisins de façon équiprobable. Après
𝑛 secondes on note 𝑋𝑛 sa position. Supposons 𝑋0 = 𝑐 , 𝑋1 = 𝐷 ; 𝑋2 = 𝑐 et
𝑋3 = 𝐵
C- Problème du collectionneur : chaque semaine une père achète à son fils un
paquet de corn flakes dans lequel on trouve en cadeau une imagin
Date : 2024
117
Master1/ Chapitre 3
Il y’a 5 images différentes en tout à collectionner donc après 𝑛 semaines on
appelle 𝑋𝑛 le nombre d’images différentes que possèdent le garçon. Après 0
semaine on a 𝑋0 = 0 et donc après une semaine il va trouver une image donc sa
collection a démarré et 𝑋1 = 1, après deux semaines , il va avoir une deuxième
image et nous supposons qu’elle est différente de la première on aura 𝑋2 = 2,
après trois semaine on suppose qu’il obtient une image déjà vue donc 𝑋3 =2
et le processus continue de même.
Le point commun entre ces trois exemples est que chaque fois on a suite de
variables aléatoires (𝑋𝑛 ). Par conséquent une chaîne de Markov est une suite de
variables aléatoires et cette suite de variables va nous permettre de décrire à
chaque fois l’évolution des différentes situations, on dira qu’elle va décrire
l’évolution du système dans le temps.
Date : 2024
118
Master1/ Chapitre 3
Ces variables aléatoires prennent les valeurs dans un ensemble qui est toujours le
même. 𝑋1 ; 𝑋2 ; …………; 𝑋𝑛 prennent les valeurs dans un ensemble qui n’a que
deux valeurs possibles ( soit il pleut , soit il ne pleut pas). Cet ensemble est appelé
l’espace des états.
L’espace des états est un ensemble fini.
De façon générale une chaîne de Markov ( savant mathématicien Russe au début
du 20e siècle ) sur un espace d’état E est un processus ( suite de variables
aléatoires indexées par le temps) (𝑋𝑛 ) tel que:
• Pour tout état 𝑖 de E , l’évènement 𝑋𝑛+1 = 𝑖 ne dépend que de l’état dans
lequel était le processus à l’instant 𝒏 (« le futur ne dépend que de l’instant
présent ») on dit que le processus de Markov est un processus sans mémoire
• La probabilité de passer de l’instant 𝑖 à l’instant 𝑗 ne dépend pas de l’instant 𝑛
Date : 2023
Date : 2020 Copyright Novembre
2020 MINESEC KEYCE code:
IP -M1012
SCIENCE
119
Master1/ Chapitre 3
Comment représenter les chaînes de Markov à l’aide des graphes :
Exemple: Dans une région s’il pleut un certain jour alors il pleut alors le
lendemain avec une probabilité égale à 0,7. De plus, s’il ne pleut pas un certain
jour alors il pleut le lendemain avec une probabilité égale à 0,2. On choisit au
hasard une journée. 𝑋𝑛 est la variable aléatoire qui prend la valeur 1 s’il pleut
après 𝑛 jours et 2 s’il ne pleut pas après 𝑛 jours.
Date : 2024
Master1/ Chapitre 3
120
Date : 2024
THEORIE DES GRAPHES
121 PRESENTATION
Master1/ Chapitre 3
CHAPITRE 3:
PLANIFICATION ET
ORDONNANCEMENT

THEORIE DES GRAPHES
122 PRESENTATION
Master1/ Chapitre 3
Objectifs pédagogiques:
Chercher un ordonnancement minimisant la durée
totale d’un projet en utilisant la méthode PERT ou la
méthode MPM

THEORIE DES GRAPHES
123 PRESENTATION
Master1/ Chapitre 3
Problèmes à résoudre:
- Quel est le temps nécessaire pour réaliser l’ensemble d’un projet?
- Quelle est la date de début et de fin de chaque tâche?
- Quelles sont les tâches critiques?

THEORIE DES GRAPHES
124 PRESENTATION
Master1/ Chapitre 3
Bibliographie:
Techniques opérationnelles de l’ordonnancement
De: Edmond Maurel, Daniel Roux et Daniel Dupont

THEORIE DES GRAPHES
125 PRESENTATION
Master1/ Chapitre 3
2.1. INTRODUCTION
Toute entité économique ( entreprise industrielle, entreprise du
bâtiment, administration, sous – traitant, etc . . .) doit assurer la
cohérence technique et économique de la réalisation du produit et/ou
du service avec le contrat qui le lie au client. Cette réalisation doit
amener la satisfaction du client en respectant le cahier des charges, les
délais et coûts. Pour cela il faut effectuer deux types de gestions:
- Une gestion technique : Spécifications, délais, etc . . . .
- Une gestion économique: coûts, prix de revient, . . . . .
De plus ces méthodes peuvent permettre de prévoir au moment
opportun, les contrôles qui s’imposent en cours de réalisation ( suivi) .
THEORIE DES GRAPHES
126 PRESENTATION
Master1/ Chapitre 3
Les méthodes d’ordonnancement des tâches permettent d’avoir une

représentation graphique ( immuable ou non) d’une réalisation en
représentant chaque opération ou (tâche) par un arc, une liaison, ou un
rectangle qui peut être proportionnel ou non à la durée . Ce graphique
dans tous les cas, permet le positionnement relatif des opérations dans
le temps .

THEORIE DES GRAPHES
127 PRESENTATION
Master1/ Chapitre 3
2.2. HISTORIQUE
La plupart des méthodes ont été mises au point pour mener à bien
l’effort de reconstruction après la seconde guerre mondiale.
La méthode PERT ( Programm Evaluation and Research Task ou
Programm Evaluation and Review technic) a été mise au point lorsque
les états - unis ont entrepris de créer leur force d’attaque nucléaire (
sous – marins et fusée Polaris) . Il fallait aller vite pour rattraper le
retard pris sur l’URSS. Ce projet était soumis à de nombreux problèmes
techniques:
- Délai fixé
- Coordination de 250 fournisseurs et 9 000 sous - traitants
THEORIE DES GRAPHES
128 PRESENTATION
Master1/ Chapitre 3
Pour obtenir l’efficacité maximale des efforts de chacun pour

l’agencement du projet, il fallait disposer d’une méthode systématique
de planification, de contrôle et de correction.
La création de la méthode PERT fut décidée dans ce but, et son
utilisation ramena la durée du projet de six ans à deux ans et demi.
Dans le même temps pour les mêmes raisons d’autres méthodes ont
fait leur apparition : réseaux de PETRI, méthode MPM ( Méthode des
potentiels métra ) en France , diagramme de GANTT ,ou encore
graphes « chemin de fer » .

THEORIE DES GRAPHES
129 PRESENTATION
Master1/ Chapitre 3
2.3. Méthode PERT

2.3.1 Principe
Réduire la durée totale d’un projet par une analyse détaillée des tâches
ou activités élémentaires et de leur enchainement. On étudie les délais
sans prendre en compte les charges.
2.3.2 Notions de base
La méthode PERT s’appuie en grande partie sur une représentation
graphique qui permet de bâtir un « réseau PERT »
Un réseau PERT est constitué par des tâches et des étapes.
Etape : commencement ou fin d’une tâche. Une étape n’a pas de durée.
On symbolise un étape (ou « nœud ») sur un réseau par un cercle.
THEORIE DES GRAPHES
130 PRESENTATION
Master1/ Chapitre 3
Etape : commencement ou fin d’une tâche. Une tâche n’a pas de durée.
On symbolise un étape (ou « nœud ») sur un réseau par un cercle.
Tâche: Déroulement dans un temps d’une opération . Contrairement à
l’étape, la tâche est pénalisante car elle demande toujours une
certaine durée, des moyens (ou ressources) et coûte de l’argent. Elle
est symbolisée par un vecteur ( ou un arc orienté, ou liaison orientée)
sur lequel seront indiqués l’action à effectuer et le temps estimé de la
réalisation de cette tâche. A (12)
Exemple de réseau:
A (12) B (6) 3
1 2

THEORIE DES GRAPHES
131 PRESENTATION
Master1/ Chapitre 3
Remarques:
• La longueur d’un arc n’est pas proportionnelle au temps d’exécution
• Pour alléger la représentation, on ne note pas le nom complet de la tâche,
mais la lettre de la tâche ou le code la représentant.
2.3.3 Représentation graphique des étapes et des tâches dans un
réseau:
Tâches successives: C (3)
A (12) B (6)
Exemple: 1 2 3 4
B ne peut commencer que si la tâche A est terminée ( A précède B ou A est

antérieur à B) .

THEORIE DES GRAPHES
132 PRESENTATION
Master1/ Chapitre 3
C ne peut commencer que si les tâches A et B sont terminées ( A et B précèdent
C ou A et B sont antérieures à C ).
Remarque: En fait B terminée suffit, sinon il y’a redondance. La contrainte
d’antériorité qui lie A et C n’a pas besoin d’être représentée.
Tâches Simultanées: Elles doivent commencer au même moment en
partant d’une même étape.
D (4)
Exemple: 1
A (12) 2
3 5
D ne peut commencer que si B est terminée

Si l’on souhaite que D ne commence que si B et C sont terminées :

THEORIE DES GRAPHES
133 PRESENTATION
Master1/ Chapitre 3
Si l’on souhaite que D ne commence que si B et C sont terminées :
D (4) 5
A (12) 3
1 2
i (0)
3’
Du fait de la règle de construction qui interdit de faire se dérouler les

deux tâches B et C simultanément, nous utilisons une tâche i(0) dite :
« tâche fictive »qui sert à représenter ce type de contraintes de liaison
(contraintes d’antériorité). Il s’agit d’une tâche dont la durée et le coût
sont nuls. On la représente en pointillés

THEORIE DES GRAPHES
134 PRESENTATION
Master1/ Chapitre 3
Tâches convergentes: Plusieurs tâches peuvent se terminer sur une
même étape.
Exemple: 1
C (3)
3 4
Ici la tâche A(12) a une durée de 12 unités de temps, B(6) a une durée
de 6 unités de temps. On constate que la tâche A dure plus longtemps
que la tâche B. A est dite « pénalisante ».
Nous pouvons calculer la longueur du projet (ici : 12 + 3 = 15 unités de
temps) en prenant le chemin le pus long dit : « chemin critique ».
THEORIE DES GRAPHES
135 PRESENTATION
Master1/ Chapitre 3
Ce « chemin critique » pourra être repéré en rouge. Les tâches de ce chemin
seront à surveiller prioritairement.
2.3.4 Normalisation du graphe
Si le graphe doit débuter par plusieurs tâches simultanées . Il doit y avoir qu’une
seule étape d’entrée ( ou étape de début, ou étape de départ). Les étapes seront
donc regroupées en une seule.
Exemple:
A (12) 2
1 4
1 3
2 5
C (3) 6 4
3 Oui
Non

THEORIE DES GRAPHES
136 PRESENTATION
Master1/ Chapitre 3
Si le graphe se termine par plusieurs tâches ( plusieurs étapes de sortie ou de fin)
Il ne doit y avoir qu’une seule étape de sortie.
Exemple:
11
T (2)
11 14
12 15 12 14
V(6)
13 16
13
Non Oui

THEORIE DES GRAPHES
137 PRESENTATION
Master1/ Chapitre 3
Problèmes de dépendances: A enclenche B, A enclenche D, C enclenche D.
Nous pouvons être tentés de dessinez le gras suivant:
1 4
2
Faux
Le graphe est faux car cette construction signifie que A enclenche, A

enclenche D, C enclenche B et C enclenche D

THEORIE DES GRAPHES
138 PRESENTATION
Master1/ Chapitre 3
Pour respecter les contraintes d’antériorités du projet, on introduit une tâche
fictive comme suit:
1 A(12) B(6)
3 4
i(0)
C (3) D (4) 5
2 4

THEORIE DES GRAPHES
139 PRESENTATION
Master1/ Chapitre 3
Présentation des étapes:
Les étapes ou nœuds peuvent être représentées de différentes façons selon les
informations que l’on souhaite mettre en évidence. Date de fin au
4 plus tôt de la
tâche
4 23
ou 22 précédente
ou 22
1 Battement ou
Date de fin Date de 4
23 marge
au plus tôt début au plus
de la tâche tard de la
précédente tâche
suivante Date de début
au plus tard de
la tâche
suivante

THEORIE DES GRAPHES
140 PRESENTATION
Master1/ Chapitre 3
2.3.5 Méthodologie de construction d’un diagramme PERT
- Etablir la liste des tâches ( faire le partitionnement des tâches en fonction des
ressources).
- Déterminer des antériorités: tâches immédiatement antérieures, et tâches
antérieures.
- Determiner les niveaux d’exécution ou rang des tâches (optionnel)
- Construire le reseau PERT
- Calculer la durée du projet, les dates de début et de fin des tâches.
Déterminer le chemin critique.mettre en évidence les marges.

THEORIE DES GRAPHES
141 PRESENTATION
Master1/ Chapitre 3
2.3.6 Exercice d’application
Soit les tâches qui constituent un projet : A(3) ; B(4) ; C(2); D(3) et E(4)
Les antériorités sont les suivantes:
A enclenche C,
A enclenche D,
B enclenche E,
C enclenche E,
Afin de construire le réseau, nous allons déterminer le rang (ou niveau)
d’exécution de chaque tâche, c’est-à-dire la position chronologique
qu’elle occupe au début de son exécution dans le projet.

THEORIE DES GRAPHES
142 PRESENTATION
Master1/ Chapitre 3
Quelques Définitions à retenir
- Début au plus tôt d’exécution d’une tâche : c’est
- Battement : le battement d’une étape est la différence entre la date
au plus tard et la date au plus tôt d’une étape.
La date au plus tôt d’une étape est la durée du chemin le plus long
menant à cette étape.
La date au plus tard d’une étape est la différence entre la durée du
projet et la durée du chemin le plus long restant à faire pour terminer
ce projet.
Les étapes se trouvant sur le chemin critique ont un battement nul.

THEORIE DES GRAPHES
143 PRESENTATION
Master1/ Chapitre 3
Les marges:
Y Z A (X) Y’ Z’
4 5
La marge totale(Mt): d’une tâche, est le retard maximal que peut

prendre la réalisation d’une tâche sans retarder tout le projet .
Mt = Z’ – (X+Y)

THEORIE DES GRAPHES
144 PRESENTATION
Master1/ Chapitre 3
Les marges:
La marge libre (Ml): d’une tâche, est le retard maximal que l’on peut
prendre dans la réalisation d’une tâche sans retarder le début de ou
des tâches suivantes.
Ml = Y’ – (X+Y)

THEORIE DES GRAPHES
145 PRESENTATION
Master1/ Chapitre 3
Exercice D’application
Désignation des tâches A B C D E F G H I J K L M
Tâches antérieures
A, B B C C B;E B;E;C;F B;E;H A, B ; D B;E;C;F;H; C;G
I;J
Durées en semaines 6 10 10 12 4 2 9 5 8 2 10 3 9
Déterminer les tâches immédiatement antérieures

Déterminer les niveaux de graphes
Construire le diagramme PERT
Déterminer le chemin critique et la durée du projet
Calculer les marges libres et les marges totales des tâches B, I et K. Interpréter les résultats
THEORIE DES GRAPHES
146 PRESENTATION
Master1/ Chapitre 3
Tâches Tâches précédentes à exécuter obligatoirement Durée en jours
A - 6
B - 2
C A 3
D A 7
E A, B 2
F C 4
G C, D 2
H E 3
I F, G
4
J H, I 1
THEORIE DES GRAPHES
147 PRESENTATION
Master1/ Chapitre 3
1- Tracer le diagramme PERT en faisant ressortir les dates au plus tôt et les dates
au plus tard
2- Déterminer le ou les chemins critiques, quel est le temps minimum nécessaire
à la réalisation de ce projet ?
3- Calculer les marges libres et totales pour les tâches C, D et F.
4- Le responsable du projet redoute des difficultés techniques lors de l’exécution
de la tâche C, ce qui porterait de 3 à 4 jours la durée de cette tâche. Indiquer
l’incidence que cela aura sur la durée totale du projet. Y ‘a – t-il de nouveaux
chemins critiques ? si oui lesquels ?

Cours Théorie Des Graphes IUC

Transféré par

Droits d'auteur :

Formats disponibles

Cours Théorie Des Graphes IUC

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours Théorie Des Graphes IUC

Transféré par

Droits d'auteur :

Formats disponibles

THEORIE DES GRAPHES

INSTITUT Universitaire de la côte

Enseignant des techniques quantitatives de gestion

Date : 2024 Copyright Mai 2024 3IAC/IUC

Cours Théorie des graphes pour étudiants

Date : 2024 Copyright Mai 2024 3IAC/IUC

Date : 2024 Copyright Mai 2024 3IAC/IUC

Date : 2024 Copyright Mai 2024 3IAC/IUC

Depuis le 20𝑒 siècle cette branche constitue une discipline

A quoi sert la théorie des graphes?

Soit V un ensemble (fini ou infini) et E une partie de 𝑽 × 𝑽 ( i.e. une

Deux arcs sont dits adjacants s’ils ont au moins une

Soit 𝒂 = 𝑽𝒊 ; 𝑽𝒋 𝝐 𝑬, on dit que a est un arc sortant

1.2 Graphe complet

Exercice: pour chacun des graphes suivants est ce complet ou non?

Propriétés des chemins:

1.5 Chaîne Eulérien ; Cycle Eulérien

1.6 Chaîne Hamiltonienne ; Cycle Hamiltonien

1.7 Exemples de familles de graphes

Pour un graphe complet non orienté à

Recherche du plus court chemin

2.1 Rappel sous – graphe

Sous- Graphe stable de G

Sous- Graphe complet de G

Théorème: ( Lemme des poignées de mains)

Propriété: Un graphe simple a un nombre pair de sommets de degré impair.

2.1.2 Recherche du plus court chemin

Exemple: un taximan de la ville de Douala doit partir d’un point A

On appelle arbre tout graphe connexe sans cycle.

Un arbre et 1,2,5 sont des feuilles

Théorème1: les affirmations suivantes sont équivalentes pour tout

2.2 Algorithme de parcours en largeur

Pour chaque sommet étiqueté 2 , trouvez une arête qui le relie au

Exemple: Déterminons un arbre couvrant du graphe suivant en

Exemple: Déterminons un arbre couvrant du graphe suivant en

Exemple: Déterminons un arbre couvrant du graphe suivant en

2.1.3 Algorithme de Prim

Exemple: Déterminons un arbre couvrant de Poids minimal avec Prim

2.1.4 Algorithme de Kruskal

Exemple: Déterminons un arbre couvrant de Poids minimal avec

2.1 Recherche du plus court chemin

2.2 PLOBLEMES DE TRANSPORT

- Système de transports dans une grande ville ( les passagers sont

2.2.2 Réseau de transport et Flots

Exemple : Pour plus de simplicité, on suppose que :

3- Conservation du flot: pour tout sommet autre que 𝑠 ou 𝑡 , la somme

Exemple de deux arcs inverses , Les deux mêmes arcs après

c- Saturation d’un arc

2.2.3 – Coupe minimum

Le flot net vaut : 12+11-4=19

Remarque: Le flot net traversant la coupe ne dépend pas de la coupe .

Théorème : ( coupe minimale)

Est – il maximal ou pas?

2.2.4 – Graphe Résiduel

2.2.5 – Chemin augmentant

Afin de conserver un flot réalisable, ces arcs ne peuvent être augmentés

Flot Graphe résiduel associé

Existe-t-il un chemin allant de 𝑠 à 𝑡?

2-3 Graphes planaires