Chapitre 1: Généralités sur les graphes

Asmaa Rahim

Maître de conférence B

Année universitaire 2022-2023

1 / 32
Introduction

La théorie des graphes est une branche de mathématiques très présente

dans notre société moderne. Nous pouvons citer quelques exemples :
réseaux de transport routier, d'eau, d'électricité ; réseaux informatiques ;
réseaux sociaux ...
Ces exemples (et bien d'autres) illustrent la notion de graphe et leur intérêt
dans le monde réel. Nous allons alors donner une série de dénitions et de
propriétés des graphes permettant de répondre à des questions de la vie
réelle.
Des points et des liens reliant certains de ces points constituent un graphe.
Dans le lexique de la théorie des graphes, les points sont dits sommets et
leurs liens sont dits arêtes ou arcs.

2 / 32
I. Dénitions et concepts
de base

3 / 32
Concept orienté

Dénition : Un graphe G = (X , U) est déterminé par :

 un ensemble X d'éléments appelés sommet (représentés par des points
x1 , x2 , ..., xn ),
le nombre de sommets du graphe G est appelé l'ordre de G noté n.
 un ensemble U de couple ordonnées de sommets appelés arcs (
représentés par des èches),
le nombre d'arcs du graphe G est appelé taille de G notée m.
 Pour un arc u = (xi , xj ), xi est l'extrémité initiale, xj est l'extrémité nale.
l'arc u se présente d'une manière graphique de la manière suivante :

 Un arc (xi , xi ) est appelé une boucle.

4 / 32
Concept orienté

 Un p -graphe est un graphe où il ne peut pas exister plus que p arcs entre
deux sommets.
 Un 1-graphe est un graphe sans arcs multiples.

Example
le premier est 3-graphe et le deuxième 1-graphe.

5 / 32
Concept orienté

 xj est le successeur de xi si u = (xi , xj ) ; l'ensemble des successeurs de

xi est noté par Γ+ (xi ).
 xj est le prédécesseur de xi si u = (xj , xi ) ; l'ensemble des prédécesseurs
de xi est noté par Γ− (xi ).
Remarque. Un 1-graphe est parfaitement déni à partir de paire (X , Γ+ )
Example
Prenant le 1-graphe d'exemple précédent
Γ+ (x2 ) = {x1 , x3 }, Γ− (x3 ) = {x1 , x2 }

6 / 32
Concept non orienté

Un graphe G = (X , E ) est déni par :

 un ensemble de sommets X .
 un ensemble d'arêtes E , il est constitué de paires de sommets non
ordonnés.
Soit l'arête e = xi xj notée aussi eij , on dit que xi et xj sont les extrémités
de e ou encore qu'ils sont adjacents ou voisins.
Deux arêtes sont dites adjacentes si elles ont une extrémité commune.
Une arête e est dite incidente à un sommet xi , si ce dernier est une
extrémité de e .
 S'il peut exister dans un graphe G = (X , E ) plusieurs arêtes entre deux
sommets (arêtes multiples), alors G est multigraphe.
 Si G est un graphe sans arêtes multiples et sans boucles alors G est dit
simple.

7 / 32
Example
le graphe de cette gure n'est pas simple.

8 / 32
Notion de degré d'un sommet

Soit G = (X , U) un graphe orienté et xi , xj ∈ X .

 Le demi-degré extérieur de xi est le nombre des successeurs du
sommet xi dans G . Il est noté dG+ (xi ).
 Le demi-degré intérieur de xi est le nombre des prédécesseurs du
sommet xi dans G . Il est noté dG− (xi ).
 Le degré de xi est dG (xi ) = dG+ (xi ) + dG− (xi ).
 Le degré de xi d'un graphe non orienté est le nombre de voisins de xi .
 Le degré minimum dans un graphe est noté δ(G ) déni par

δ(G ) = min{dG (x) | x ∈ X }

 Le degré maximum dans un graphe est noté ∆(G ) déni par

∆(G ) = max{dG (x) | x ∈ X }

 Si dG (x) = 0 alors x est dit isolé dans G , et si dG (x) = 1 alors x est

pendant.
9 / 32
Notion de degré d'un sommet

Example
1. Soit le graphe suivant

dG+ (x1 ) = 1, dG− (x1 ) = 1 d'où dG (x1 ) = 2.

dG+ (x2 ) = 1, dG− (x2 ) = 0 d'où dG (x2 ) = 2.

10 / 32
Notion de degré d'un sommet

Example
2. dG (x5 ) = 4 car la boucle est comptée 2 fois.

11 / 32
Théorème fondamental de graphes

Théorème
Soit G un graphe d'ordre n et de taille m alors
X
dG (x) = 2m
x∈X

Démonstration
Le degré de chaque sommet x est le nombre d'arcs (arêtes) incidentes à x.
Or chaque arc (arête) a deux extrémités.

Conséquence
Le nombre de sommet de degré impair dans un graphe est pair.

12 / 32
Quelques graphes

a. Graphe régulier : un graphe G est dit graphe k -régulier si ∀x ∈ X ,

dG (x) = k .
b. Graphe symétrique : ∀xi , xj ∈ X , (xi , xj ) ∈ U =⇒ (xj , xi ) ∈ U
c. Graphe antisymétrique : ∀xi , xj ∈ X , (xi , xj ) ∈ U =⇒ (xj , xi ) ∈
/U
d. Graphe complet : ∀xi , xj ∈ X , (xi , xj ) ∈
/ U =⇒ (xj , xi ) ∈ U .
De même, un graphe non orienté simple d'ordre n est dit complet
noté Kn est le graphe dont tous les sommets sont voisins.
e. Graphe biparti : un graphe est biparti s'il existe une partition de son
ensemble de sommets en deux sous-ensembles X1 et X2 de sorte que
deux sommets de même sous-ensemble ne soient jamais adjacents. Il
se note G = (X1 ∪ X2 , U).
Un graphe simple avec | X1 |= p et | X2 |= q est dit biparti complet
et noté Kp,q si ∀x1 ∈ X1 , ∀x2 ∈ X2 , x1 x2 ∈ E .

13 / 32
Quelques graphes

Example
Le graphe suivant est un graphe biparti complet K2,3

14 / 32
Quelques graphes

f. Graphe complémentaire d'un graphe simple :

Soit G = (X , E un graphe simple, le graphe complémentaire
Ḡ = (X , Ē ) est constitué des sommets de G mais exclusivement des
arêtes qui ne sont pas dans G
i.e x1 x2 ∈/ E ⇒ x1 x2 ∈ Ē .
Example
Un graphe et son complémentaire

15 / 32
Construction de graphes à partir d'un autre

Soit G un graphe (orienté ou non), A ⊂ X , V ⊂ U (ou E )

 Sous-graphe engendré (induit) par A est le graphe G1 (A, V ) dont les
sommets sont des éléments de A les arcs (ou arêtes) ayant les deux
extrémités dans A.
 Graphe partiel engendré (induit) par V est le graphe G2 (X , V ) ayant
les sommets de G et les arcs (ou arêtes) de V .
 Sous-graphe partiel engendré par A et V est le graphe partiel de
G1 (A, V ) engendré par V .
Example
Soit le graphe G suivant :

16 / 32
Construction de graphes à partir d'un autre

Example
Soit A = {x1 , x2 , x3 }, le sous-graphe engendré par A est :

Figure  Sous-graphe

17 / 32
Construction de graphes à partir d'un autre

Example
Soit V = {u1 , u3 , u4 }, le graphe partiel engendré par V est :

Figure  Graphe partiel

18 / 32
Example
Le sous-graphe partiel engendré par V et A est :

Figure  Sous-graphe partiel

19 / 32
Représentations d'un
graphe

20 / 32
Matrice d'adjacence

Soit G un graphe d'ordre n, la matrice d'adjacence sommet-sommet est

une matrice carrée n × n
 M dénie par :
k s 0 il y a k aretes ou arcs allant de i vers j
mi,j =
0 sinon
Remarques
- Si le graphe n'est pas orienté, la matrice est symétrique.
- Pour des graphes valués, remplacer 1 par la valeur numérique de l'arc.
- la somme des éléments de la i-eme ligne de M est égale au degré
extérieur d + (xi ) du sommet xi de G .
 la somme des éléments de la j-eme colonne de M est égale au degré
intérieur d − (xj ) du sommet xj de G .

21 / 32
Matrice d'adjacence

Example

0 1 1
 

M = 1 0 1
0 0 0

22 / 32
Matrice d'incidence

Sommet-arc
La matrice d'incidence sommet-arc d'un graphe G = (X , U) est une
matrice A à coecients 0, 1, −1 et 2 en cas de boucle, chaque ligne
correspond à un sommet et chaque colonne correspond à un arc.
si u = (i, j) ∈ U, on trouve dans la colonne u : aiu = 1, aju = −1 et
tous les autres termes sont nuls.
Sommet-arête
La matrice d'incidence sommet-arête d'un graphe G = (X , E ) est une
matrice A à coecients 0, 1 et 2 en cas de boucle, chaque ligne
correspond à un sommet et chaque colonne correspond à une arête e .
si e = ij ∈ E , la colonne e a tous les éléments nuls sauf aie = 1 et
aje = 1

23 / 32
Matrice d'incidence

Example

24 / 32
Listes d'adjacence

Soit G = (X , U ) un graphe d'ordre n, les sommets du graphe G sont notés

x1 , x2 , . . . , xn . La représentation par listes d'adjacence de G consiste en un
tableau T de n listes, une pour chaque sommet de X . Autrement dit, T [xi ]
contient la liste de tous les sommets successeurs de xi .
 Si le graphe G est non orienté, la liste d'adjacence est la liste des voisins
de chaque sommet.

Example

25 / 32
II. la connexité dans les
graphes

26 / 32
Chaîne

Une chaîne d'un graphe G (orienté ou non) est une suite de la forme :
P = (x0 , u1 , x1 , . . . , uk , xk )
où k est un entier positif.
 Le nombre d'arcs ou d'arêtes qui composent une chaîne P est appelé
longueur de cette chaîne noté k .
 x0 et xk sont les extrémités de la chaîne.

 Si G est simple, on écrit P = (x0 , x1 , . . . , xk ).

 Une chaîne est dite simple si ses arcs ( ou arêtes) sont deux à deux
distincts. On dit que la chaîne ne passe pas deux fois par le même arc ( ou
arête).
 Une chaîne est dite élémentaire si ses sommets sont deux à deux
distincts. On dit que la chaîne ne passe pas deux fois par le même sommet.

 Si P est une chaîne de longueur nulle alors P est réduite à un seul

sommet.
27 / 32
Chaîne

Example

 P = (x1 , u2 , x2 , u5 , x3 , u7 , x4 , u4 , x5 , u6 , x3 , u5 , x2 ) cette chaîne n'est ni

simple ni élémentaire.
 P = (x1 , u2 , x2 , u1 , x1 , u3 , x5 ) simple mais pas élémentaire.
 P = (x1 , u2 , x2 , u5 , x3 ) élémentaire donc simple.

Remarque :
 Une chaîne élémentaire est simple.
28 / 32
Cycle

Un cycle est une chaîne de longueur k ≥ 1 simple et fermée. C'est donc

une chaîne de la forme :

C = (x0 , u1 , x1 , . . . , uk , x0 )

 Il n' y a pas de cycle de longueur nulle.

 Un cycle de longueur 1 est une boucle.
 Lorsque G est simple, C est noté C = (x0 , x1 , . . . , xk , x0 )
 Un cycle est élémentaire si ses sommets xi , i = 0, k sont deux à deux
distincts. Celui-ci est noté Ck .
 Un cycle est dit pair( resp. impair) si sa longueur est paire ( resp.
impaire).

Théorème(Caractérisation des graphes bipartis)

Un graphe G est biparti ssi il ne contient pas de cycles impairs

29 / 32
Cycle

Example

C1 = (x1 , u3 , x5 , u6 , x3 , u8 , x1 , u2 , x2 , u1 , x1 ) n'est pas un cycle élémentaire.

C2 = (x1 , u3 , x5 , u6 , x3 , u5 , x2 , u1 , x1 ) est un cycle élémentaire.

Proposition
si δ(G ) ≥ 2 alors G contient un cycle.
30 / 32
Graphes et sous-graphes connexes

 Un graphe G est connexe si pour tout couple x et y de sommets avec

x 6= y , il existe une chaîne reliant x à y .

 Une composante connexe de G est un sous-graphe connexe maximal.

Maximal veut dire qu'il n'existe pas de sous-graphe engendré connexe qui
contient strictement (pour les sommets) ce sous-graphe.

 On dit que G est connexe si et seulement s'il a une seule composante

connexe.

 Chaque composante connexe est un graphe connexe.

 Un point d'articulation d'un graphe est un sommet dont la suppression

augmente le nombre de composantes connexes.

 Un isthme est une arête dont la suppression augmente le nombre de

composantes connexes.

31 / 32
Graphes et sous-graphes connexes

Example

Figure  Graphe ayant trois Composantes Connexes

32 / 32