Faculté des Sciences de Tunis

Graphes et Optimisation

Chapitre 1 :
Notions de base

Année Universitaire Leila Hadded

2020 - 2021 [email protected]
Théorie des graphes

La théorie des graphes permet de

résoudre des problèmes
mathématiques de manière plus
simple et plus intuitive

Graphe = un dessin géométrique défini par de

points (sommets) reliés entre eux par de liens
(arêtes)

L. HADDED 2
Aperçu historique

■ Le célèbre problème des sept ponts de Kônigsberg (Actuellement

Kaliningrad) (Euler, 1736):

4 quartiers (A, B, C, D)
7 ponts

■ Le problème consiste à déterminer s'il existe ou non une promenade

dans les rues de Kônigsberg permettant, à partir d'un point de départ au
choix (A, B, C, D), de passer une et une seule fois par chaque pont, et
L. HAoorn de revenir à son point de départ 3
Aperçu historique

• Modélisation du problème
Décrire le plan de la ville, en ne gardant que les informations importantes
Graphe
C' C Sommets = Quartiers
---~ Arêtes = Ponts
-
...A --'\V

A B B
➔
~ I) ....., • .-

■ Le problème des Sept ponts de Kônigsberg peut maintenant se formuler

de la manière suivante : Peut-on trouver un "trajet" dans ce graphe qui
passe exactement une fois par chaque arête?
L. HADDED 4
Aperçu historique

A B

■ Euler a démontré que, pour qu'un trajet passe une fois et une seule sur
chaque arête et revienne au point de départ, il est nécessaire que tous les
nœuds du graphe soient reliés à un nombre pair d'arête (graphe eulérien)

L. HADDED 5
Motivations

Un bon dessin vaut mieux qu'un long discours I

• La théorie des graphes permet de résoudre efficacement une grande

variété de problèmes pratiques en les ramenant à des configurations qui se
dessinent simplement à l'aide de points et de liaisons entre ces points

• L'utilisation judicieuse d'un graphe peut rendre certains problèmes

concrets accessibles à un raisonnement mathématique

■ Apprendre à représenter une situation à l'aide d'un graphe en se posant

d'abord les questions suivantes: ''quels objets vont être des sommets,
lesquels deviennent les arêtes P"
L. HADDED 6
Domaines d'application

■ Réseaux routiers :
- Quel est le plus court chemin, en nombre de kilomètres, passant par un certain
nombre de villes données ?
- Quel est le chemin traversant le moins de villes pour aller d'une ville à une autre ?
- Est-il possible de passer par toutes les villes sans passer deux fois par une même
route?
• Sommets : Villes ~ -.
~
~l?:--,

• Arêtes : Routes reliant les villes - , : · .... ' °!'!"

■ Réseaux sociaux :
• Sommets : Abonnés
• Arêtes : Relations entre les abonnés

■
L HADDED ••• 7
Graphe orienté

■ Un graphe orienté est défini par un couple G=(S,A) :

• S ensemble fini non vide de sommets
• A c SxS ensemble d'arcs
■ Un graphe orienté est représenté par un schéma où les sommets sont des
points et les arcs sont des flèches A
• Si a=(x,y) est un arc du graphe G :
o x : extrémité initiale de a (I (a) = x)
B E
o y : extrémité finale de a (T(a) = y)

C D

L. HADDED 8
Graphe non orienté

■ Un graphe non orienté est un couple G=(S,A) :

• S ensemble fini non vide de sommets
• A c SxS ensemble d'arêtes

■ Une arête a du graphe est une paire a= (s 1,s2) de sommets. Les sommets s1
et s2 sont les extrémités de l'arête
■ L'ordre de s 1 et de s2 dans le couple (s 1,s 2) n'a aucune importance, donc
(s 1,s2) est équivalent à (s 2 ,s 1)
A ____ _----1 B C
Exemple:
S = {A, B, C, D, E, F}
A = {(A,B), (A,F), (B,D), (B,F), (C,D), (C,E), (E,F)}

L. HADDED E 9
Graphe valué

■ Un graphe valué (pondéré) G=(S,A,c) est un graphe où on associe une

fonction c : A ➔ IR appelée coût ou poids qui représente la valeur de
chaque arc ou arête
■ Le coût d'un arc ou arête (ij) est noté c(ij)ou cij

Exemple:

L. HADDED 10
Ordre d'un graphe

■ L'ordre d'un graphe est le nombre de ses sommets : 1 S 1

Exemple:
S = {A, B, C, D, E, F}
G est d'ordre 6 = 1S 1

L. HADDED 11
Adjacence des sommets et des arêtes

■ Deux sommets sont adjacents (ou voisins) s'il existe une arête (arc) entre
eux
■ Deux arêtes (arcs) sont adjacentes si elles ont une extrémité commune
■ Une arête (arc) est incidente à un sommet x six est l'une de ses extrémités
■ Une boucle est une arête ou un arc (x,x) qui relie un sommet à lui-même

Exemple:

o Le sommet A est adjacent aux sommets B et F

E
o Les arêtes (A, B) et (B, D) sont adjacentes car elles ont une extrémité commune
L HAoorn qui est le sommet B 12
Degré d'un sommet

■ Le degré d'un sommets est le nombre d'arêtes ayant comme extrémité ce

sommet, noté d(s)
• Lorsque d(s)=O, on dit que s est un sommet isolé

Exemple:
d(A) = d(C) = d(D) = d(E) = 2
d(B) = d(B) = 3

E
L. HADDED 13
Propriétés sur les degrés des sommets

Théorèmes:
■ La somme des degrés des sommets d'un graphe est un nombre pair (égale
à deux fois le nombre d'arêtes) :

I
sEs
d(s) = 2IAI
■ Le nombre de sommets de degré impair est toujours pair

Exercice:
Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit
relié avec exactement trois autres ?
L. HADDED 14
Degré d'un sommet

Soit x un sommet d'un graphe orienté :

■ On note d +(x) (le demi-degré extérieur A

de x) le nombre d'arcs partant de x
(ayant x comme extrémité initiale) E
■ On note d-(x) (le demi-degré intérieur
de x) le nombre d'arcs arrivant à x
C D
(ayant x comme extrémité fmale)
■ d(x) = d +(x) + d-(x) d(D)=4
d+(D) =1
d-(D) =3

L. HADDED 15
Degré d'un sommet

Soit x un sommet d'un graphe orienté :

• S(x) = {y E S / (x,y) E A} appelé ensemble des successeurs de x
• P(x) = {y E S / (y,x) E A} appelé ensemble des prédécesseurs de x
• d+(x) = {a E A/ I(a)=x} nombre d'arcs ayant pour extrémité initiale x
• d-(x) = {a E A/ T(a)=x} nombre d'arcs ayant pour extrémité fmale x

S(A)= {B, C}
P(A)= {D, E}

C D

L. HADDED 16
Sous graphe / Graphe partiel

■ Sous graphe : Soit G = (S,A) un graphe. Pour un sous-ensemble de

sommets S' c S, le sous-graphe de G induit par S' est le graphe G' = (S',
A(S')) dont l'ensemble des sommets est S' et l'ensemble des arêtes (arcs)
A(S') est formé de toutes les arêtes (arcs) de G ayant leurs deux extrémités
dans S'. Autrement dit, on obtient G' en enlevant un ou plusieurs sommets
de G, ainsi que toutes les arêtes (arcs) incidentes à ces sommets

■ Graphe Partiel : Soit G = (S,A) un graphe. Le graphe G' = (S,A') est un

graphe partiel de G, si A' c A. Autrement dit, on obtient G' en enlevant
une ou plusieurs arêtes (arcs) au graphe G

L. HADDED 17
Sous graphe / Graphe partiel

Graphe Sous Graphe

Exemple:

0
...
S = { 1 ,2,3,4 } S' = { 2 ,3,4}
A= { {1 ,3} , {2 ,3} , {3,4}} A'= { {2,3} , {3 ,4}}

Graphe Graphe Partiel

0 0
...
0 S'=S
S = { 1 ,2 ,3,4}
A= { {1 ,3} , {2 ,3} , {3,4}} A'= { {2,3} , {3,4}}
L. HADDED 18
Graphe régulier

■ Le degré d'un graphe est le degré maximum de tous ses sommets

■ Un graphe non orienté est dit régulier (ou k-régulier), si tous ses sommets
ont le même degré k

Exemple:
Degré du graphe = 4 (à cause du
sommetv3)

L. HADDED 19
Graphe simple / Multigraphe

■ Un graphe non orienté est dit simple s'il ne possède ni boucle ni arêtes
multiples (une arête qui est représentée p fois dans un graphe / p >1)

Exemple:
G est un multigraphe

0 isol e'
sommet

8 sommets
boucle 12 arêtes

L. HADDED 20
Graphe complet

■ Un graphe non orienté simple est dit complet Kn avec n sommets est un
graphe dans lequel chaque sommet est relié à tous les autres

Exemple:
Voici les cinq premiers graphes complets

• •
Dans un graphe complet Kn, le nombre d'arêtes est égal à n (n-l)
2
L. HADDED 21
Graphe biparti

■ Un graphe biparti est un graphe tel

que l'ensemble des sommets peut
être partitionné en deux sous- X y
ensembles disjoints X et Y tels que
chaque arête du graphe a la forme (x,
y), avec x E X et y E Y

■ Un graphe Biparti complet est un

graphe biparti tel que tout sommet
de X est adjacent à tout sommet de Exe111ple de graphe
Y. Si IX 1= m et I Y 1 = n, on écrira : biparti co111plet

~,n
L. HADDED 22
Graphe planaire

■ Un graphe est dit planaire, s'il peut être dessiné dans le plan sans
croisement d'arêtes

Exemple:
Comme le graphe de droite ne contient pas de croisement, K 4 est planaire

L. HADDED 23
Représentation des graphes : Matrice d'adjacence (Sommets - Sommets)

■ La matrice d'adjacence associée à un graphe non orienté G d'ordre n est la

matrice carrée M(G) de dimension nxn définie par:

mr;
1
= {k s'il y. ak arêtes allant de i à j
' 0 sino.n

Exemnle:
A B B
• • A
B
0

1
A
1
0
C
0

1
D
1
0
~ M=c
0 1 0 1
[)
1 0 1 0
D C
L. HADDED Place mémoire n 2
= 24
Représentation des graphes : Matrice d'adjacence (Sommets - Sommets)

Soit G=(V,A) un graphe orienté, avec V={v 1,v2, ••• ,vn}. La matrice d'adjacence
du graphe est la matrice M(G) dont les coefficients (mi,j) sont défmis par:

m - _= {1,si (vi,vi ) E A
0, si ( v i, vi ) ~ A
11
'

Exemple:
A B C D E
A
0
A 1 1 0 0
B 0 0 1 1 1
B E
~ M~ 0 0 0 1 0
D 1 0 0 0 0
E 1 0 1 1 0
C D
L. HADDED 25
Représentation des graphes : Matrice d'adjacence (Sommets - Sommets)

Propriétés:
Avec les notations précédentes, nous avons les propriétés immédiates
suivantes:

■ La somme des éléments de la jème colonne de M est d-(x) : d-(~)=L i=l

~j

L. HADDED 26
Représentation des graphes : Matrice d'incidence {Sommets -Arêtes)

Soit G=(V,A) un graphe non orienté sans boucle, avec V={v 1,v2, ••• ,vn} et A= {
a1,a2, ••• ,am}. On appelle matrice d'incidence de G la matrice M(G) dont les
coefficients (mij) :
m, ={ 1 si vi est extrémité de <½
1
0 sinon

Exemple:

a b C d e f
1 1 0 0 0 1 0
2 1 1 0 0 0 1
3 0 1 1 0 0 0
d b 4 0 0 1 1 0 0
4 3
5 .o 0 0 1 1 1
C
L. HADDED
Place mémoire n = x m 27
Représentation des graphes : Matrice d'incidence {Sommets -Arcs)

Soit G=(V,A) un graphe orienté sans boucle, avec V={v 1,v2, ••• ,vn} et A= {a 1,a
2, ••• ,am}. La matrice d'incidence aux arcs est définie par:

1 si vi = I(<½)
m;j = -1 si vi = T(<½)
0 sinon

Exemple:

a b C d e f

1 1 0 0 0 -1 0
2 -1 1 0 0 0 -1
3 0 -1 1 0 0 0
d b
4 0 0 -1 1 0 0
4 3 5 0 0 0 -1 1 1
L. HADDED C 28