5
THEORIE DES GRAPHES
PLAN
• Généralités et définitions
• Représentation d'un graphe
• Arbres et arborescences
• Exploration d'un graphe
• Connexité et forte connexité
1
5.1 GENERALITES ET DEFINITIONS
5-1-1 GRAPHES ORIENTES
a f
b e
c d
EXEMPLE: G1 = (X1 , U1)
X1 = {sommets} = {a,b,c,d,e,f}
U1 = {arcs} = {(a,b),(b,a),(b,c),(c,a),(c,d),(a,f),
(e,f),(d,e),(e,d)}
2
Γ: X → P (X)
x → Γ(x) = {successeurs de x}
-------------------------------------------------------------------
EXEMPLE(suite) Γ1(b)={a,c} Γ1(f)={Ø} Γ1(d)={e}
-------------------------------------------------------------------
Chemin : suite d'arcs telle que l'extrémité
terminale d'un arc coïncide avec l'extrémité
initiale de l'arc suivant
-------------------------------------------------------------------
EXEMPLE (suite) ((a,b),(b,c),(c,d)) ou (a,b,c,d)
-------------------------------------------------------------------
3
boucle : arc du type (x,x)
x
circuit : chemin dont le premier sommet
coïncide avec le dernier
-----------------------------------------------------------------
EXEMPLE (suite) (a,b,c,a) circuit de G1
-----------------------------------------------------------------
4
chemin hamiltonien : chemin qui passe une fois
et une seule par chaque sommet
---------------------------------------------------------------
EXEMPLE (suite) (a,b,c,d,e,f)
a a f
b b e
c c d
un circuit un chemin hamiltonien
---------------------------------------------------------------
5
5-1-2 UTILISATION DES GRAPHES
• Modélisation, représentation de problèmes
Exemple: plan de ville, arbre généalogique, états
d'un système..
• Résolution de problèmes
Exemple: plus court chemin, ordonnancement, flots, ...
• Outils
Exemple: structures de données,.
• ...
6
Se n s In t e r d it
G
H
E D
A
B C
Graphe associé F
G H D
B C
A
G
F
7
Amélie et
Jules
Sophie Fabien et Y David et Z Elodie et X
Graphe associé
A-J
Marcus Norbert Zoé Loulou Bebert Charly
S F D E
M N Z L B C
8
5-1-3 GRAPHES NON ORIENTES
G= (X,A) A est un ensemble d'arêtes
arête : arc "sans orientation"
a e G3
b A3={[a,e], [b,f],
f [e,f], [d,f],...}
c
chaîne de a à d
g d [a,e],[e,f],[f,d]
Chaîne : suite d'arêtes telle que toute arête a une
extrémité commune avec l'arête précédente (sauf la
première) et l'autre avec l'arête suivante (sauf la
dernière)
9
cycle : chaîne dont les deux extrémités coïncident
---------------------------------------------------------------
EXEMPLE (suite) cycle de G3: [aefba]
---------------------------------------------------------------
chaîne et cycle sont définis aussi dans un
graphe orienté (on ne tient plus compte de
l'orientation)
---------------------------------------------------------------
EXEMPLE (suite) cycle de G1: (bacb)
---------------------------------------------------------------
10
connexité : un graphe est connexe si toute paire
de sommet est reliée par une chaîne
---------------------------------------------------------------
EXEMPLE (suite) G1 et G3 connexes,
G3' non connexe
---------------------------------------------------------------
degré x ∈X
d(x) = nombre de voisins de x
---------------------------------------------------------------
EXEMPLE (suite) dans G3 d(c) = 4 d(b) = 3
---------------------------------------------------------------
11
chaîne eulérienne : chaîne qui passe une fois et
une seule par chaque arête
Théorème d'Euler
Un multigraphe connexe admet une chaîne
eulérienne si et seulement si le nombre de
sommets de degré impair est 0 ou 2
a a
b c c
b
d
d
1766 La Pregel à Koenigsberg
12
5.2 REPRESENTATION D ’UN GRAPHE
G2 = (X,A) 4
|X 2| = n = 5 0 3 2
|A 2| = m = 9
1
5-2-1 TABLEAU DES SUCCESSEURS
Nb liste des
X suc successeurs - accès facile aux
0 1 4 successeurs
1 3 2 3 0 - assez souple
2 1 4 - assez peu de place
3 2 2 0 mémoire
4 2 1 3
13
5-2-2 DEUX TABLEAUX
0 1 2 3 4 x
IND 0 1 4 5 7 9
SUC 4 0 2 3 4 0 2 1 3
0 1 2 3 4 5 6 7 8
IND[i] = indice du premier successeur de i dans SUC
SUC : tableau des successeurs
Γ(i) = {SUC[IND[i]], SUC[IND[i]+1],... , SUC[IND[i+1]-1] }
- accès facile aux successeurs Exemple: i=3,
IND[3]=5 IND[4]=7
- très peu souple Γ(3) =
- très peu de place mémoire {SUC[5],SUC[6]}={0,2} 14
5-2-3 UNE MATRICE
0 1 2 3 4
0 0 0 0 0 1
1 1 0 1 1 0
2 0 0 0 0 1
3 1 0 1 0 0
4 0 1 0 1 0
- balayages
- place mémoire importante
- souple (évolution du graphe)
- calculs matriciels possibles
15
5-2-4 TABLEAU ADRESSANT DES LISTES
CHAÎNEES DE SUCCESSEURS
0 p 4 N u ll
1 q 0 2 3 N ul l
2 r 4 N u ll
3 s 0 2 N u ll
4 t 1 3 N u ll
- place mémoire assez faible
- souple (évolution du graphe)
- peu facile à manipuler
(ex: nombre de successeurs ?)
16
5-2-5 La Classe CGraphe
classe CGraphe
{
Nous supposerons qu'un graphe G=(X,U)=(X,*)
est défini par l'ensemble X de ses n sommets de la classe
CSommet et soit par l'ensemble U de ses m arcs de la
classe CArcs ou arêtes de la classe CArêtes soit par
l'application * de la classe CSuc qui à chaque sommet x
de X associe *(x)={successeurs ou voisins de x}
}
Dans la suite nous donnons une
présentation algorithmique des problèmes de graphes 17
5.3 EXPLORATION D ’UN GRAPHE
G=(X,A) donné avec |X|=n |A|=m
5.3.1 Descendants d'un sommet
Définition
D(x0)= {sommets x ∈X tels qu'il existe un chemin de x0 à x}
Détermination de D(x0)
Principe
marquer x0
tant que ∃ (x,y)∈A t.q. x marqué et y non marqué
faire
marquer y;
fait; D(x)={sommets marqués}
18
void Aveugle (CSommet x0;
CTab1 marque //tableau associant un booléen à
//chaque sommet initialisé à "faux";
CTab2 père//tableau associant un sommet père à
//chaque sommet initialisé à "∅"):
booléen modif = vrai;
19
début
marque[x0]=vrai;
tant que modif faire //jusqu'à ne plus pouvoir marquer de
sommets
modif = faux ;
pour tout u ∈ A faire
si marque[ext_init(u)] et non marque[ext_term(u)] alors
//ext_init(u) (resp. ext_term) =extrémité initiale (resp. terminale) de l'arc u
//l'arc u a seulement son extrémité initiale marquée
modif = vrai ;
marque[ext_term(u)]=vrai;
père[ext_term(u)]= ext_init(u);
finsi;
fait;
fait;
fin ;
20
père: tableau permettant la reconstitution des
chemins de marquage de x0 vers ses descendants.
x4*
EXEMPLE u1 u4
x3 *
u2 u8
* x0 x2
u5
u3 u7
x1 u9
* u6 x5
*
x1 x2 x3 x4 x5
père x∅
4 ∅ x∅
4 x∅
0 x∅
1
Ordre de marquage des sommets: 0, 4, 1, 3, 5 au premier passage 21
x4
EXEMPLE u91 u74
u62 u18
x0 x3 x2
5u5
u83 u37
x1 u29
4u6 x5
Ordre de marquage des sommets: 0, 1, 4 puis 3, 5 en plusieurs passages
La complexité dépend de la numérotation des arcs
Pire des cas
a b c d e f
5 4 3 2 1
Complexité (au pire): O(m.n)
La procédure suivante décrit un parcours en largeur depuis x0. 22
void Largeur (CSommet x0;
CTab2 père //tableau de n sommets initialisé à "∅";
CTab3 L //tableau de n entiers initialisé à "∞")
//L[x]longueur (nombre d'arcs) d'un chemin le plus court de x0 à x.
File F(n) //file de sommets
CTab1 marque //tableau de n booléens [Link];
initialisé à "faux";
pour tout y ∈ Γ(x) faire
CSommet x, y
si non marque[y] alors
début//initialisation
marque[y]=vrai;
marque[x0]=vrai; L[y]= L[x]+1;
L[x0]=0; père[y]= x ;
F=filevide(n); [Link](y);
finsi;
[Link](x0);
fait;
tant que non [Link] faire fait;
x = [Link]ête ; fin ;
23
x4*
u1 u4
EXEMPLE
*x0 u2 u8
x3* x2
u5
u3 u7
x1 u9
* u6 x5
*
x1 x2 x3 x4 x5 x10 x4 x3 x5
père x0 x1 x0 x1
L(x) 1 2 1 2
24
complexité: O(m) (hypothèse: m≥n)
(pour tout sommet faire / pour tout successeur faire)
EXEMPLE
arborescence "en largeur" parcourue:
xx0
0
xx11 xx44
xx3 xx55
3 25
void Imprimer_chemin (CSommet s,v)
//procédure appelée après Largeur(s,père,L)
//Imprime le chemin le plus court de s à v
début
si v == s alors imprimer s ;
sinon
si père[v]==∅ alors
imprimer "pas de chemin de" s "à" v
sinon
Imprimer_chemin(s,père[v]);
imprimer v;
finsi;
finsi;
fin; 26
Premier appel
G.Imprimer_chemin(x0 ,xn) avec x0≠xn
Les descendants de x0 ont été déterminés par un
parcours "à l'aveugle" puis en largeur à partir de
x0;
la procédure suivante décrit un parcours en
profondeur depuis x0.
27
La procédure Profondeur utilise la procédure
récursive suivante:
void Visiter (CSommet x; CTab1marque //tableau de booléen
CTab2 père //tableau sommet de sommet)
procédure récursive (utilisation d'une pile);
début
pour tout y ∈ Γ(x) faire
si non marque[y] alors
marque[y]=vrai;
père[y]= x ;
Visiter (y,marque,père);
finsi;
fait;
fin complexité: O(m)
28
procedure Profondeur (CSommet x0; CTab1 marque;
CTab2 père);
début
pour tout x∈X faire
marque[x]=faux;
père[x]= ∅ ;
fait;
marque[x0]=vrai;
Visiter(x0,marque,père);
fin ; complexité: O(m)
29
x4*
u1 u4
EXEMPLE
*x0 u2 u8
x3* x2
u5
u3 u7
x1 u9
* u6 x5
*
x1 x2 x3 x4 x5
père x0 x1 x0 x3
30
EXEMPLE
x1 x2 x3 x4 x5
père x0 ∅ x1 x0 x3
x0
arborescence x1 x4
"en profondeur" x3
parcourue:
x5
31
5.3.2 PARCOURS D’UN GRAPHE NON ORIENTE
Utilisation des deux procédures précédentes
légèrement modifiées:
remplacer Γ(x)={successeurs de x}
par V(x)={voisins de x}
5.3.3 PARCOURS COMPLET D ’UN GRAPHE
but: traitement en chaque sommet du graphe
(une seule fois).
32
A partir de Profondeur et en utilisant Visiter on obtient:
void Parcours_Graphe (CTab1 marque; CTab2 père);
début
pour tout x∈X faire marque[x]=faux; père[x]= ∅ ; fait;
pour tout x∈X faire
si non marque[x] alors
marque[x]=vrai;
Visiter (x,marque,père);
finsi;
fait;
fin ;
complexité: O(m)
33
On prendra soin d'ajouter dans Visiter
"traiter(y);"
entre "marque[y]=vrai;" et "père[y]= x;"
34
5.4 CONNEXITE
5.4.1 DEFINITIONS
sous-graphe : G'=(X',A') de G (orienté ou
non orienté):
X'⊆X A'⊆A et
∀x,y∈X', [x,y]∈A ⇔ [x,y] ∈A'
---------------------------------------------------------------
EXEMPLE (suite) e
G3'
b sous-graphe
de G3
c
g d
---------------------------------------------------------------35
sous-ensemble maximal pour une propriété ℘:
sous-ensemble tel que l'ajout d'un élément
lui fait perdre la propriété ℘
Composante connexe de G: sous-graphe de G
connexe maximal
--------------------------------------------------------------
EXEMPLE (suite)
G3' a 2 composantes connexes
---------------------------------------------------------------
36
5.4.2 DETERMINATION DES
COMPOSANTES CONNEXES D’UN GRAPHE
entrée: graphe G=(X,U)
(G est non orienté ou on ne tient pas compte de l’orientation)
sortie: liste des composantes
principe
-déterminer une composante connexe C
en partant d'un sommet quelconque
- retirer C du graphe et recommencer
37
Procédure "aveugle" de recherche
des composantes connexes:
E = X;
Tant que E non vide faire
marquer + un sommet x de E;
tant que c'est possible faire
marquer + tout voisin (non encore marqué +)
d'un sommet déjà marqué + ;
fait;
Écrire C l'ensemble des sommets marqués +; le sous
graphe de G dont les sommets sont ceux de C est une
composante f-connexe de G;
E = E - C; C = Ø;
fait; fin; complexité: O(n2)
38
b *
d
e
*a
f *
g
C2
* i
h
a: b f i
b: a f i C1
f: a b i c
i: a b f C3
39
b
d
e
f
g
h
i
40
Recherche par un parcours en profondeur:
void Comp_connexes (CComp comp //liste des composantes,
comp[I]={sommets de la Ième composantes})
CTab1 marque; CTab2 père;
CGraphe G'=(X',A'); entier nc;
début
X'=X; A'=A;
nc=0; (nombre de composantes)
pour tout x∈X' faire
marque[x]=faux;
père[x]= ∅ ;
fait;
41
pour tout x∈X' faire
nc=nc+1;
si non marque[x] alors
marque[x]=vrai;
Visiter(x,marque,père);
finsi;
Comp(nc)={x∈X'|marque[x]=vrai};
X'=X'-Comp(nc) ;
A'=sous-graphe de G défini par X';
fait;
fin;
complexité: O(m)
42
b *a
d
e
*a
f *b
g
C2
a: b
i
b: f *f h
f: i
i: - C1
c
f: -
b: - C3
a: -
43
5.4 ARBRES ET ARBORESCENCES
nombre cyclomatique :
G graphe de n sommets, m arêtes et p
composantes connexes
ν(G) = m - n + p
2 5
m=8
1 6 n=6
p=1
3 4
G5 ν (G5) = 8-6+1 = 3
ν(G) = nombre d'éléments d'une base de cycles 44
arbre: définitions équivalentes
H=(X,U), n sommets (n ≥ 2)
(1) H connexe et sans cycle
(2) H sans cycle et n-1 arêtes
(3) H connexe et n-1 arêtes
(4) H sans cycle et en ajoutant une arête on crée
un et un seul cycle
(5) H connexe et si on supprime une arête , il n'est
plus connexe
(6) une chaîne et une seule entre toute paire de
sommets 45
démonstration
(1) H connexe et sans cycle
(2) H sans cycle et n-1 arêtes
(3) H connexe et n-1 arêtes
1⇒2 H sans cycle ⇒ ν(H)=0, et H connexe
⇒ p=1 ⇒ m-n+1 = 0 ⇒ m=n-1
2⇒3 H sans cycle ⇒ ν(H)=0, et m=n-1
⇒ (n-1)-n+p=0 ⇒ p=1 ⇒ H connexe
46
démonstration
(3) H connexe et n-1 arêtes
(4) H sans cycle et en ajoutant une arête on
crée un et un seul cycle
3⇒4 H connexe ⇒ p=1, et m=n-1 ⇒
ν(H)=(n-1)-n+p=0 ⇒ H est sans cycle.
Si on ajoute une arête, on obtient H' t.q.
m'=m+1=n, n'=n et p'=1
⇒ ν(H')=n-n+1=1 ⇒ 1 cycle
47
Démonstration (suite)
(4) H sans cycle et en ajoutant une arête on
crée un et un seul cycle
(5) H connexe et si on supprime une arête ,
il n'est plus connexe
4⇒5 si H n'est pas connexe, ∃ {x,y} non reliés
par une chaîne ⇒ en ajoutant l'arête [x,y] on
ne crée pas de cycle et (4) n'est pas vérifié ⇒
H est connexe. p=1⇒m=n-1. Si on ôte une
arête, on obtient H" t.q. m"=n-2 et n"=n ⇒
ν(H")=m"-n"+p"=0 (car sans cycle)
⇒ n-2-n+p"=0 ⇒ p"=2 ⇒ H" est non connexe48
Démonstration (suite)
(5) H connexe et si on supprime une arête ,
il n'est plus connexe
(6) une chaîne et une seule entre toute paire
de sommets
(1) H connexe et sans cycle
5⇒6 H connexe ⇒∃ au moins une chaîne entre
2 sommets; la suppression d'une arête rend H
non connexe ⇒ cette chaîne est unique
6⇒1 ∃ une chaîne entre 2 sommets ⇒ H est
connexe; elle est unique ⇒pas de cycle 49
2 5
1 6
3 4
H5 un arbre de 6 sommets
graphes orientés
racine : sommet r tel qu'il existe un chemin de r à
tout autre sommet du graphe
degré intérieur([Link]érieur): d'un sommet x:
nombre d'arcs d'extrémité terminale (resp.
initiale) x notés d-(x) et d+(x) 50
arborescence: définitions équivalentes
H=(X,U) n sommets (n ≥ 2)
(1) H arbre avec une racine r
(2) ∃ r ∈ X, relié à tout x ∈ X par un
chemin unique
(3) H connexe et
∃ r ∈ X t.q. d-(r)=0 et
d-(x)=1 pour tout x ≠ r
51
(4) H sans cycle et ∃ un sommet r ∈X t. q. d-
(r)=0 et d-(x)=1 pour tout x ≠ r
c f
a r
g
d e
b
H, une arborescence
52
arborescence =
"arbre enraciné" (rooted tree)
= "arbre" en informatique
Ex: arbre généalogique, tournois, arbre des
espèces animales,...
53
arborescence binaire:
A racine
sens
a b
implicite
c d e f
g h i
(voir cours N° 3)
54