Faculté des Sciences de Tunis

Graphes et Optimisation

Chapitre Il :
Cheminement et connexité

Année Universitaire Leila Hadded

2020 - 2021 [email protected]
Chaine et cycle

■ Dans un graphe non orienté G, une chaîne est une suite de la forme
(s0,a1,s 1,a2, ••• ,sk-I,ak,sk) présentant alternativement des sommets (si) et des
arêtes (3i), telle que ai= (si_1 ,si) est une arête de G, i =l, ... ,k

Exemple:
A D

ABCDE est une chaîne (une chaîne peut passer plusieurs fois par une même
arête (resp. sommet))
L. HADDED 2
Chaine et cycle

■ Une chaîne simple est une chaîne gui ne passe pas deux fois par une
même arête (toutes les arêtes sont distinctes)

Exemple:
A D

BECDEA est une chaîne simple (aucun de ses arêtes n'apparaît plus d'une fois)
BECDEB n'est pas une chaîne simple
L. HADDED 3
Chaine et cycle

■ Une chaîne élémentaire est une chaîne qui ne passe pas deux fois par un
même sommet (tous les sommets sont distincts)

Exemple:
A D

BECDEA est une chaîne non élémentaire (sommet E apparaît deux fois)

L. HADDED 4
Chaine et cycle

■ Un cycle est une chaîne simple dont les extrémités sont confondues (s 1=
sk)
■ La longueur d'une chaîne (resp. cycle) est le nombre d'arêtes constituants
cette chaîne (resp. cycle)

Exemple:
A D

L.HAooEt\BCDEA est un cycle de longueur 5 5

Chemin et circuit

B B

E D E D
,
NON-ORIENTE .
ORIENTE

Terminologie des graphes orientés : Arête = Arc

Chaîne = Chemin (simple, élémentaire)
Cycle = Circuit

L. HADDED 6
Chaine et chemin

Remarques:
■ Une boucle est un cycle de longueur 1
■ Si le graphe est simple, la chaîne (resp. chemin) peut être définie par la
suite des sommets constituants cette chaîne (resp. chemin)
■ Par convention, on impose à toute chaîne de contenir au moins une arête
Exemples:
o (v4,e4,v3,e 2,v2,e 1,v1) est une chaîne (graphe simple :
(v4,e 4,V 3,e2, V2,e1, V1) = (v4,V 3,V2, V1))
oLes chaînes (v4,v3,v2,v 1) et (v 1,v2,v3,v4)
sont identiques
L. HADDED 7
Vz
Distance et diamètre

■ La distance entre deux sommets x et y notée d(x, y) est la longueur de la

plus courte chaîne (resp. chemin) reliant ces deux sommets
■ Le diamètre d'un graphe G noté DM(G) est:
DM(G) = Max [d(x,y)]; {x, y ES/ x*y}

Exemple:
o La distance entre a et e est 1
o La distance entre a et d est 2
o Le diamètre du graphe est 2 (car c'est la plus
grande distance entre 2 sommets quelconques)

L. HADDED 8
Graphe eulérien

■ Un cycle eulérien passe une fois et une seule par chaque arête d'un graphe
et revient au point de départ
■ Un graphe est dit Eulérien s'il admet un cycle eulérien
■ Plus simplement, on peut dire qu'un graphe est eulérien s'il est possible de
dessiner le graphe sans lever le crayon (et sans passer deux fois sur le
même trait!)
Théorème d'Euler:
1. Un graphe admet un cycle eulérien si et seulement si il est connexe et n'a
aucun sommet de degré impair (Départ = Arrivée)
2. Un graphe admet une chaine eulérienne entre les sommets x et y si et
seulement si il est connexe et si x et y sont les deux seuls sommets de degré
impair (Départ = l'un des sommets impairs, Arrivée = l'autre sommet
impair)
L. HADDED 9
Graphe eulérien

Exemple:
Le graphe ci-dessous est-il eulérien? Si oui proposer un cycle eulérien

Cycle eulérien: 1-8-5-7-4-6-2-3-1-5-4-2-1

L. HADDED 10
Graphe hamiltonien

■ Un cycle hamiltonien est un cycle qui passe par tous les sommets du
graphe une et une seule fois (il existe une arête reliant le sommet de départ au
sommet d'arrivée)
■ Un graphe est dit hamiltonien s'il possède un cycle hamiltonien
Théorème:
Soit G = (S,A) un graphe simple d'ordre ~3. Si pour toute paire u,v de
sommets non adjacents, on a d(u)+d(v)>n, alors G est hamiltonien
Exemple: 1 ~ - ------ 2
Cycle hamiltonien :
o(l - 2 - 3 - 4)
o(3 - 2 - 1 - 4)
L. HADDED 11
Connexité (graphe non orienté)

■ Un graphe non orienté G=(S,A) est dit connexe si : V x,y ES, il existe une
chaîne reliant x à y
■ Un graphe orienté est connexe si le graphe non orienté associé est
connexe
Exemples:
....
.. ................. ..
.. .
. . 'I
.... \
. ' · --. . _ ___ . ... . ,,
. ----------t~ ..
:

• ........
.... .............. .... ... .

1 Graphe connexe 1 Graphe non connexe 1

Ce graphe est non connexe malgré qu 'il est constitué

de deux composantes connexes séparées
L. HADDED 12
Connexité (graphe non orienté)

■ Une composante connexe C d'un graphe non orienté G=(S,A) est un sous-
ensemble maximal de sommets tels que deux quelconques d'entre eux
soient reliés par une chaîne: si x E C, alors :
o 'v y E C, il existe une chaîne reliant x à y,
o 'v k E S \ C, il n'existe pas de chaîne reliant x à k

■ Un graphe est connexe si et seulement si il a une seule composante

connexe -- --- -.....

Exemple: ' ' I

\ I
'1 --
,.
/ ,'- -
/ .... "
., ,,
,,,,,,,,,.,,.
,
1

-- ------ -- -----
_.,,,.,,,~
~
L. HADDED 13
' ' ....
- -- -- -
Algorithme de marquage pour la détermination d'une CC

Construction de la composante connexe (CC) :

(i) Marquer (+) le sommet i
(ii) Marquer(+), tout sommet adjacent à un sommet marqué(+)
Jusqu'à ce qu'on ne puisse plus marquer de sommets

Les sommets marqués sont ceux de la composante connexe de i

L. HADDED 14
Connexité (graphe orienté)

■ Un graphe orienté G = (S,A) est dit fortement connexe si : V x,y E S, il

existe un chemin de x vers y, et un chemin de y vers x
■ Propriété: Un graphe orienté fortement connexe est connexe

Exemple:

Graphe fortement Graphe non fortement

L. HADDED
connexe connexe 15
Connexité (graphe orienté)

■ Une composante fortement connexe C d'un graphe orienté G = (S,A) est

un sous-ensemble maximal de sommets tels que deux quelconques d'entre
eux soient reliés par un chemin: si x E C, alors :
o 'v y E C, il existe un chemin de x vers y, et un chemin de y vers x
o 'v k E S \C, il n'existe pas de circuit passant par x et k

Exemple:
Ce graphe a deux composantes
fortement connexes : {a, b, c, d}
{e, f, g}

L. HADDED 16
Algorithme de marquage pour la détermination d'une CFC

Construction de la composante fortement connexe (CFC):

(i) Marquer (+) et (-) le sommet i
(ii) Marquer (-) tous les prédécesseurs d'un sommet marqué (-) et
marquer(+) tous les successeurs d'un sommet marqué (+).
Jusqu'à ce qu'on ne puisse plus marquer de sommets

Les sommets marqués à la fois par (+) et (-) appartiennent à la composante

fortement connexe de i

L. HADDED 17
Algorithme de marquage pour la détermination d'une CFC

ALG 0RITHME DE MARQU.A,GE

1

Première Composante: C1={1 .2 ,3.4,5} 1 Deuxième Compooanœ: C2•{8 .7} 1

Troisième Composante: C3={8}

L. HADDED 18