Théorie des graphes et

optimisation
Chapitre1:

Introduction

Ghallabi Sameh
ISIMM
 Pourquoi les graphe
Les graphes sont des outils de modélisation puissants de situations
concrètes où interviennent des objets en interaction (en relation, en
dépendances).
 réseau de communication
 diagramme de succession de tâches en gestion de projet
 sciences sociales (modélisation des relations)
 chimie (modélisation de structures),
 ……
 Pourquoi les graphe
Résoudre des problèmes modélisés par des graphes:
 Plus court chemin d’une ville à une autre?
 Comment minimiser la longueur totale des connexions dans les réseaux?
 Comment ordonnancer l’exécution des tâches (requêtes) sur des machines,
processeurs,
... ...
 Exemple d’un graphe
La carte ci-contre représente le
réseau de tramway de la ville de
Strasbourg. Il s'agit d'un graphe
dont les sommets sont les stations.
 Exemple d’un graphe

Le réseau d'ordinateur représenté

ci-contre est un graphe complet en
effet tous les sommets sont reliés
deux à deux
 Définition
Un graphe est constitué :
 d’un ensemble fini de points appelés sommets.
 d’un ensemble fini de lignes, appelées arêtes .
De façon plus formelle, un graphe est défini par un couple G = (S, A).

Exemple:
A
B
S: l’ensemble de sommet
S=(A, B, C)
A: l’ensemble d’arêtes
C A= (AB, BC, CA)

 Un graphe peut être orienté ou non

 Graphe orienté
 Un graphe est orienté si ses arêtes, appelées arcs dans ce cas, ont un
sens de parcours.

 Dans un graphe orienté, les couples (si,sj) ∈A sont orientés, c’est à

dire que (si,sj) est un couple ordonné, où si est le sommet initial, et sj
le sommet terminal. Un couple (si,sj) est appelé un arc.
 Graphe orienté
Exemple:

représente le graphe orienté G = (S, A) avec:

S = {1, 2, 3, 4, 5, 6} et

A = {(1, 2),(2, 4),(2, 5),(4, 1),(4, 4),(4, 5),(5, 4),(6, 3)}

 Graphe non orienté
 Un graphe non orienté est un ensemble de points, appelés sommets,
reliés par des lignes, appelées arêtes.

 Dans un graphe non orienté, les couples (si,sj) ∈A ne sont pas

orientés, c’est à dire que (si,sj) est équivalent à (sj,si). Une paire (si,sj)
est appelée une arête.

Par exemple:

Représente le graphe non

orienté G = (S, A) avec
S = {A, B, C} et
A = {(A, B),(A, C),(B, C)}.
Terminologie
 L’ordre d’un graphe est le nombre de ses sommets.
 Le degré d'un sommet est le nombre d'arêtes partant de ce sommet.
 Un sommet de degré 0 est un sommet isolé.
 Deux sommets reliés par une arête sont adjacents.
 Une boucle est un arc ou une arête reliant un sommet à lui-même.
 Un graphe orienté est dit élémentaire s’il ne contient pas de boucle.
 Un graphe est dit complet si chaque sommet est adjacent à tous les
autres.
Terminologie
 Un graphe est dit pondéré si il y a des valeurs associées aux
arcs/arêtes: distances, prix, capacités d’utilisation, bandes passantes,
coût,...
 La somme des degrés de tous les sommets d'un graphe est égale au
double du nombre d'arêtes.
 Un graphe non-orienté est dit simple s’il ne comporte pas de boucle,
et s’il ne comporte jamais plus d’une arête entre deux sommets.
 Un graphe orienté est un p-graphe s’il comporte au plus p arcs entre
deux sommets.

 Un graphe partiel d’un graphe orienté ou non est le graphe obtenu

en supprimant certains arcs ou arête.
Terminologie
 Un sous-graphe d’un graphe orienté ou non est le graphe obtenu en
supprimant certains sommets et tous les arcs ou arêtes incidents aux
sommets supprimés.
 Soit G = (S,A) un graphe orienté ou non orienté
 G’ = (S’, A’) est un sous graphe de G si S’ ⊂ S et A’ ⊂ A.
Exercice
1) Dessiner les graphes complets non orientés d’ordre 2, 3 et 4.
2) Dessiner un graphe non orienté complet à 4 sommets.

-Quel est le degré des sommets de ce graphe?

- Combien d’arêtes possède-t-il?
Notion d’adjacence entre sommets
 Dans un graphe non orienté, un sommet si est dit adjacent à un
autre sommet sj s’il existe une arête entre si et sj. L’ensemble des
sommets adjacents à un sommet si est défini par:

adj(si) = {sj/(si, sj) ∈ A ou (sj, si) ∈ A}

 Dans un graphe orienté, on distingue les sommets successeurs

des sommets prédécesseurs:

succ(si) = {sj /(si, sj) ∈ A}

pred(si) = {sj /(sj, si) ∈ A}
Notion de degré d’un sommet
 Dans un graphe non orienté, le degré d’un sommet est le nombre
d’arêtes incidentes à ce sommet.

 Dans un graphe orienté, le demi-degré extérieur d’un sommet si ,

noté d ◦+(si), est le nombre d’arcs partant de si.

 De même, le demi-degré intérieur d’un sommet si , noté

d◦−(si), est le nombre d’arcs arrivant à si .

 Dans un graphe orienté, on a: d(si) = d+(si) + d−(si).

Exercice
On considère le graphe orienté G = (S, A) tel que S = {1, 2, 3, 4, 5}
A = {(1, 2),(1, 4),(2, 2),(2, 3),(2, 4),(3, 5),(4, 3),(5, 3)}

1. représenter graphiquement ce graphe,

2. donner le demi-degré extérieur de 2 et le demi-degré intérieur de
4,
3. donner les sommets prédécesseurs de 4 et les sommets
successeurs de 2,
4. donner un graphe partiel et un sous-graphe de ce graphe.
Accessibilité
graphe non orienté: Entre deux sommets, il existe une succession
d’arêtes.

• J est accessible depuis A

•A est accessible depuis J
•⇒l’accessibilité est symétrique
• ⇒Chaine
Définitions
Dans un graphe non orienté, une chaine est une suite finie,
débutant et finissant par un sommet.
Une chaîne est une succession d'arêtes mises bout à bout.
La longueur de la chaîne est le nombre d'arêtes qui la compose.
On dit qu'une chaîne est fermée si ses extrémités coïncident.
Un cycle est une chaîne fermée dont les arêtes sont toutes
distinctes.
On appelle distance entre deux sommets la longueur de la plus
petite chaîne les reliant.
On appelle diamètre d’un graphe la plus longue des distances
entre deux sommets.
Exemple
Dans le graphe ci-contre,
 A – B – C – D – E est une chaîne de longueur 4.
 A – B – E – D – B – A est une chaîne fermée de longueur 5.
 B – C – D – E – B est un cycle de longueur 4.
Accessibilité
graphe orienté: Entre deux sommets, il existe une succession d’arcs

x4 est accessible depuis x9

 x9 n’est pas accessible
depuis x4
⇒l’accessibilité est non
symétrique
⇒Chemin
 Chaine - Cycle ! Graphe non
orienté
Chaines (cas non orienté)
Liste d’arêtes consécutives (ou de sommets)
Longueur d’une chaine = nombre d’arêtes
Cycle (cas non orienté)
Chaine fermée
Longueur d’un cycle = nombre d’arêtes
Exemple: (A, B, D, E) et (H, K, J, I, G, H)
Chemin - Circuit ! Graphe orienté
Chemin (cas orienté)
Liste d’arcs consécutifs
Longueur d’un chemin = nombre d’arcs
Circuit (cas orienté)
Chemin fermé
Longueur d’un circuit = nombre d’arcs
Exemple: (x1, x2, x6, x3) et (x7, x1, x11, x10, x8, x7)
Définitions
Chaine/Cycle/Chemin/Circuit élémentaires
passe au maximum une seule fois par chacun des sommets
 Chaine/Cycle/Chemin/Circuit simples
passe au maximum une seule fois par chacun des arcs/arêtes

(E, D, C, A, B): chaine élémentaire

(et simple)

(B, D, E, A, C): chaine élémentaire

(et simple)

(A, B, D, C, A, E, D): chaine simple

(non élémentaire)
Notions de connexité
Connexité
Cas des graphes non orientés. Un graphe non orienté est connexe si
chaque sommet est accessible à partir de n’importe quel autre.
Exemple: le graphe non orienté suivant n’est pas connexe, car il
n’existe pas de chaîne entre les sommets a et e

Le sous-graphe défini par les sommets {a, b, c, d} est connexe.

Notions de connexité
Forte Connexité :
Un graphe orienté est fortement connexe si chaque sommet est
accessible à partir de n’importe quel autre.
Exemple,

Un graphe est Un graphe n’ est pas

fortement connexe fortement connexe

Graphe acyclique
Un graphe non orienté est dit acyclique si il ne contient pas de
cycle.
Un graphe orienté est dit acyclique si il ne contient pas de circuit.
 Arbre
On appelle arbre tout graphe connexe sans cycle.
un graphe non orienté comportant n sommets, les propriétés
suivantes sont équivalentes pour caractériser un arbre :
-G est sans cycle et connexe,
- G est sans cycle et comporte n−1 arêtes,
-G est connexe et comporte n−1 arêtes,
-Nœuds de l’arbre = sommets du graphe

-Feuilles = sommets de degrés 1 / Noeuds interne = sommets de degré >

1
-Les sommets 1, 2 et 5 sont les feuilles
arborescence
Une arborescence est un graphe orienté sans circuit.
Elle admet une racine s0 ∈ S telle que, pour tout autre sommet si
∈ S, il existe un chemin unique allant de s0 vers si .
Si l’arborescence comporte n sommets, alors elle comporte
exactement n − 1 arcs.
Par exemple, le graphe suivant est une arborescence de racine a :

Racine: sommet de degré

entrant = 0
Feuilles: sommet de degré
sortant = 0
Graphes planaires
Soit G un graphe orienté ou non. On dira que G est planaire s’il
admet une représentation où ses arêtes (ou arcs) ne se coupent pas.

Exemple:
Graphes planaires
Exercice : Montrer que les graphes suivants sont planaires :

Correction : on peut le représenter de la façon suivante.

Faces d’un graphe planaire
Etant donnée une représentation planaire d’un graphe G, le plan se
retrouve divisé en un certain nombre de régions qu’on appelle les
faces de la représentation planaire.

Théorème d’Euler: s + f = 2 + a

Par exemple, le graphe suivant : possède 4 faces (notées A, B, C et D).

les arêtes (1, 2),(1, 4),(4, 3),(3, 2),(5,
6) et (5, 7) constituent des frontières
entre des faces différentes
Faces d’un graphe planaire
Exercice:
Considérons un graphe G dont les degrés de ses sommets sont
4, 4, 4, 4, 3, 3.
a) Combien d’arêtes possède G ? Justifier.
b) Donner une représentation planaire de G en déterminant
d’abord le nombre de faces.
c) Vérifier que la somme des degrés des faces est égal au
double du nombre d’arêtes.
 Représentations non graphiques
d’un graphe
Représentation par matrice d’adjacence

Les matrices sont l’une des structures de données utilisées en

informatique pour représenter les graphes et les relations.

La représentation par matrice d’adjacence de G consiste en une

matrice booléenne M de taille n × n telle que M[i][j] = 1 si (i, j) ∈
A, et sinon M[i][j] = 0.

Dans une matrice d’adjacences, les lignes et les colonnes

représentent les sommets du graphe. Un « 1 » à la position (i, j)
signifie que le sommet i est adjacent au sommet j.
 Représentations non graphiques
d’un graphe
Représentation par matrice d’adjacence
Soit le graphe non orienté G = (S, A), où S = {s1, . . . , sn}.
Dans une matrice d’adjacences, les lignes et les colonnes
représentent les sommets du graphe.
M[i][j] est le nombre d'arêtes joignant le sommet i au sommet j.
Exemple:
 Représentations non graphiques
d’un graphe
Représentation par matrice d’adjacence
Application
Soit le graphe suivant non orienté G = (S, A).

Donner la matrice d'adjacence correspondante :

 Représentations non graphiques
d’un graphe
Représentation par matrice d’adjacence
G est le graphe non orienté.
La matrice d’adjacence a plusieurs caractéristiques :
1- Elle est carrée : il y a autant de lignes que de colonnes.

2- Il n’y a que des zéros sur la diagonale allant du coin supérieur gauche au coin
inférieur droit. Un « 1 » sur la diagonale indiquerait une boucle.

3- Elle est symétrique : mij = mji . On peut dire que la diagonale est un axe de
symétrie.

4-Une fois que l’on fixe l’ordre des sommets, il existe une matrice d’adjacences
unique pour chaque graphe. Celle-ci n’est la matrice d’adjacences d’aucun autre
graphe.
 Représentations non graphiques
d’un graphe
Représentation par matrice d’adjacence
Soit une matrice d'adjacence M d'un graphe G non orienté d'ordre n
dont les sommets sont numérotés de 1 à n.
Le nombre de chaîne de longueur k reliant le sommet i au sommet j
est égal au terme mij de la matrice Mk .
Exemple:
•Le nombre de chaîne de longueur 4 reliant
le sommet 1 au sommet 3 est égal au
coefficient a13 ou a 31 de la matrice A4.

• Il existe 11 chaînes de longueur 4 reliant

les sommets 1 et 3.
 Représentations non graphiques
d’un graphe
Représentation par matrice d’adjacence
Dans la matrice d'adjacence d'un graphe orienté, le coefficient
mi,j désigne le nombre d'arcs d'origine i et d'extrémité j.

Exemple: Pour le graphe suivant, on trouve la matrice d'adjacence

Cette matrice n'est plus symétrique. En revanche, le terme d'indice (i,j) de la

matrice Mn compte toujours le nombre de chemins allant de i vers j.
 Représentations non graphiques
d’un graphe
Représentation par liste d’adjacence
On peut aussi représenter un graphe en donnant pour chacun de
ses sommets la liste des sommets auxquels il est adjacent. Ce
sont les listes d’adjacences.
Exemple:
 Représentations non graphiques
d’un graphe
Exercice 1:
Donnez les représentations par matrice d’adjacence et listes
d’adjacence des graphes suivants
 Représentations non graphiques
d’un graphe
Correction:
 Représentations non graphiques
d’un graphe
Exercice 2:
1) Quelle matrice peut-être la matrice d’adjacence d’un graphe non
orienté?

2)

a) combien de chemins de longueur 2 de s3 à s3 ?

b) combien de chemins de longueur 3 de s4 à s2 ?
c) combien de chemins de longueur 4 de s2 à s3 ?
 Représentations non graphiques
d’un graphe
Exercice 3:

Combien de chemins de longueur 3 de s1 à s2

Combien de chemins de longueur 3 de s3 à s1
 Représentations non graphiques
d’un graphe
Représentation par matrice d’incidence
Dans une matrice d’incidence: le rôle des lignes et des colonnes
n’est donc pas similaire.

Une ligne représente un sommet.

 Une colonne une arête ou un arc.
 Représentations non graphiques
d’un graphe
Représentation par matrice d’incidence

Considérons un graphe non orienté d’ordre n possédant m arêtes ,

dont on a numéroté les n sommets et les m arêtes.

 Graphe non orienté

 Représentations non graphiques
d’un graphe
Représentation par matrice d’incidence

Considérons un graphe orienté d’ordre n possédant m arêtes , dont

on a numéroté les n sommets et les m arêtes.

 Graphe orienté
 Représentations non graphiques
d’un graphe
Représentation par matrice d’incidence:

Exemple
 Représentations non graphiques
d’un graphe
Représentation par matrice d’incidence:

Remarque
Un graphe orienté possédant une boucle ⇒ matrice d’incidence
impossible.

le sommet A est ici origine et extrémité de l’arc e7, on devrait donc affecter au
coefficient situé sur la première ligne et la septième colonne à la fois les valeurs 1
et −1, ce qui est bien sûr impossible.
Notion de graphe eulérien
Un graphe est dit connexe si on peut relier deux quelconques de
ses sommets par une chaine.
Une chaine eulérienne est une chaine satisfaisant aux conditions
suivantes:
- elle contient toutes les arêtes du graphe
- chaque arête n’est pas décrite qu’une seule fois.
Plus simplement, on peut dire qu’un graphe est eulérien s’il
est possible de dessiner le graphe sans lever le crayon.

Exemple:

La chaîne B – A – D – B – C – D – E – A – C
est par exemple une chaine eulérienne.
Notion de graphe eulérien
Un cycle eulérien est une chaine eulérienne fermée.

Exemple:

Dans le graphe ci-contre, la chaîne

A – B – C – D – E – F – A est un cycle eulérien.
Notion de graphe eulérien
Théorème d'Euler : Soit G un graphe connexe.

-G admet un cycle eulérien si, et seulement si, tous les sommets

de G sont de degré pair.

- G admet une chaîne eulérienne si, et seulement si, deux

sommets de G exactement sont de degré impair. Dans ce cas, la
chaîne est d'extrémité ces deux sommets.
Notion de graphe eulérien
Théorème : Un multigraphe orienté fortement connexe admet un
circuit eulérien si et seulement si d ◦+(si) = d ◦−(si) pour tout sommet si
∈ S.

Théorème : Un multigraphe orienté connexe admet un chemin

eulérien si et seulement si il existe deux sommets v0 et v1 tel que
-d +(v0) = d −(v0) + 1,
-d +(v1) = d −(v1) − 1
- pour tout v ∈ V \ {v0, v1}, d −(v) = d +(v),
Notion de graphe eulérien
Exercice: Montrer que le graphe suivant est eulérien
Graphes hamiltoniens
une chaine hamiltonienne passe une et une seule fois par chacun
des n sommets du graphe.
On appelle cycle hamiltonien un cycle élémentaire de longueur n.
On dit qu’un graphe est hamiltonien s’il est possible de trouver un
cycle passant une et une seule fois par tous les sommets.
Un graphe possédant un cycle ou une chaine hamiltonien sera dit
graphe hamiltonien.
Graphes hamiltoniens
Exemple:

G2

G1
le graphe suivant ne possède pas de
cycle hamiltonien, mais possède
Le graphe possède
une chaine hamiltonienne (< a, b, e,
un cycle hamiltonien
d, c >).
(< a, e, b, d, c, a >)
Graphes biparti
Un graphe est dit biparti s’il existe S1 et S2, deux sous-ensembles
de S tels
-qu'il n'y ait aucune arête entre éléments de S1 et aucune arête entre
éléments de S2
-S1 ∪ S2 = S et S1 ∩ S2 = ∅
Graphes biparti
un graphe est dit biparti complet entre un ensemble de n
sommets et un ensemble à m sommets tel que:
-Chaque sommet du premier ensemble est relié à tous les sommets
du second ensemble.
-Si le premier ensemble m et le second ensemble n, le graphe
biparti complet est noté Kn,m.
Exemple:
Exercice