Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
1
CHAPITRE 1.
FONDEMENTS DE LA THEORIE
DES GRAPHES.
1.1 DEFINITIONS ET EXEMPLES.
1.1.1 DEFINITIONS.
1.1.1.1 Graphes Orientés.
Un GRAPHE G = G(X,U) est déterminé par
Un ensemble fini X = {x
1
,x
2
,…, x
n
} dont les éléments sont appelés
sommets ou nœuds.
Un ensemble U = {u
1
,u
2
,…,u
n
}
du produit cartésien X x X dont les
éléments sont appelés arcs.
Pour un arc u = (x
i
, x
j
), x
i
est l’extrémité initiale, x
j
l’extrémité finale (ou bien
origine et destination). L’arc u part de x
i
et arrive à x
j.
Graphiquement, l’arc u se représente de la manière suivante :
x
i
x
j
FIG.1.1. Arc u=(x
i
, x
j
)
Un arc (x
i
, x
i
) est appelé une boucle.
Un p-graphe est un graphe dans lequel il n’existe jamais plus de p arcs de la forme
(i,j) entre deux sommets quelconques.
Exemple.
x1
u
4
x
4
u
7
u
1
u
3
u
5
x
5
u
6
x
2
u
2
x
3
FIG. 1.2. Graphe determiné par (X,U),
X = {x
1
, x
2
, x
3,
x
4
, x
5
} ; U = {u
1
, u
2
, u
3
, u
4
, u
5
, u
6
, u
7
}
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
2
1.1.1.2 Graphes non Orientés.
Lors de l’étude de certaines propriétés, il arrive que l’orientation des arcs ne joue
aucun rơle. On s’intéresse simplement à l’existence d’arc(s) entre deux sommets
(sans en préciser l’ordre). Un arc sans orientation est appelé arête. Pour une arête
u=(x
i
,x
j
), on dit que u est INCIDENTE aux sommets x
i
et x
j
.
Exemple.
x
1
u
6
x
4
u
7
u
1
u
2
u
3
u
4
x
5
u
8
x
2
u
5
x
3
FIG. 1.3. Graphe determiné par (X,U),
X = {x
1
, x
2
, x
3,
x
4
, x
5
} ; U = {u
1
, u
2
, u
3
, u
4
, u
5
, u
6
, u
7
, u
8
}
Un multigraphe est un graphe pour lequel il peut exister plusieurs arêtes entre
deux sommets.
Un graphe est simple :
1. s’il n’est pas un multigraphe ;
2. s’il n’existe pas de boucle.
Deux arêtes u, v sont dites paralèlles si et seulement s’elles sont des arêtes incidentes
entre deux sommets distincts. Notation : u v. Dans la figure FIG 1.3. nous avons u
1
u
2
.
1.1.1.3 Principales Définitions.
APPLICATION MULTIVOQUE. Soit G = (X,U) un graphe orienté, x
i
, x
j
deux sommets de G. On a :
x
j
est SUCCESSEUR de x
i
si (x
i
,x
j
) ∈ U ; l’ensemble des
successeurs de x
i
est noté Γ(x
i
).
x
j
est PREDECESSEUR de x
i
si (x
j
,x
i
) ∈ U ; l’ensemble des
prédécesseurs de x
i
est noté Γ
-1
(x
i
).
L’application Γ qui, à tout élément de X, fait correspondre une
partie de X est appelée une APPLICATION MULTIVOQUE.
Pour un 1-graphe, G peut être parfaitement déterminé par (X,Γ),
notation à la base d’une représentation informatique très
utilisée, les LISTES D’ADJACENCE.
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
3
EXEMPLE. X = {x
1
,x
2
,x
3
,x
4
,x
5
} ;Γ(x
1
) = x
2
;Γ(x
2
) = {x
3
,x
4
} ; Γ(x
3
)={x
4
,x
5
} ;
Γ(x
4
)={x
1
} ; Γ(x
5
)={x
4
}.
x1
x
4
x
5
x
2
x
3
FIG. 1.4. Graphe déterminé par (X,Γ)
ADJACENCE.
Deux sommets sont adjacents s’ils sont joints par un arc.
Deux arcs sont adjacents s’ils ont au moins une extrémité
commune.
DEGRES.
Le demi- degré extérieur de x
i
, d
+
(x
i
) est le nombre d’arcs ayant x
i
comme extrémité initiale ; d
+
(x
i
)=card(Γ(x
i
)).
Le demi-degré intérieur de x
i
, d
-
(x
i
) est le nombre d’arcs ayant x
i
comme extrémité finale ; d
-
(x
i
)=card(Γ
-1
(x
i
)).
Le degré de x
i
, d(x
i
) = d
+
(x
i
) + d
-
(x
i
). Le degré d’un sommet d’un
graphe non orienté est le nombre d’arêtes qui lui sont incidentes.
Une boucle augmente de deux unités le degré du sommet concerné.
EXEMPLE. [cf. FIG. 1.4]
d
+
(x
2
)= 2 ; d
-
(x
2
)= 1 ; d(x
2
)=3.
d
+
(x
4
)= 1 ; d
-
(x
4
)= 3 ; d(x
4
)=6 (il y a une boucle du sommet x
4
).
Un sommet est dit isolé si son degré est égal à zéro.
THÉORÈME. (FORMULE ENTRE DÉGRÉ ET NOMBRE DE
ARÊTES).
1.Some de degrés est égal deux fois de nombre des arêtes.
2. Soit G = (X, U) un graphe orienté. On a
∑ d
+
(x) = ∑ d
-
(x) = card(U) (nombre d’arcs).
COROLAIRE. Le nombre de sommets ayant le degré impair est pair.
DEMONSTRATION.
∑d(sommet de dégré impair)+∑ d(sommet de dégré pair) = 2 x nombre d’arcs
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
4
GRAPHE COMPLEMENTAIRE.
G=(X,G) et G =(X,U).(x
i
,x
j
) ∈ U ⇒ (x
i
,x
j
) ∉ U et (x
i
,x
j
) ∉U ⇒ (x
i
,x
j
) ∈U.
G est le graphe complémentaire de G.
GRAPHE PARTIEL.
G=(X,U) et U
p
⊂ U. G
p
=(X,U
p
) est un graphe partiel de G ;
SOUS GRAPHE.
G=(X,U) et X
s
⊂ X. G
s
=(X
s
,V) est un sous graphe de G; ó V est la
restriction de la fonction caractéristique de U à X
s
.
V={(x,y)/(x,y) ∈ U∩X
s
x X
s
}. ∀x
i
∈ X
s
, Γ
s
(x
i
)=Γ(x
i
)∩X
s
.
SOUS GRAPHE PARTIEL. Combinaison des deux définitions
précédentes.
EXEMPLE. Réseau routier.
Que les autoroutes : graphe partiel
Que la région Midi-Pyrénées: sous graphe.
Que les autoroutes Midi-Pyrénées: sous graphe partiel.
GRAPHE symétrique : (x
i
,x
j
) ∈ U ⇒ (x
j
,x
i
) ∈ U.
GRAPHE anti –symétrique : (x
i
,x
j
) ∈ U ⇒ (x
j
,x
i
) ∉ U.
GRAPHE réfléxif : (x
i
,x
i
) ∈ U, ∀ x
i
∈ U.
GRAPHE transitif : (x
i
,x
j
) ∈ U, (x
j
,x
k
) ∈ U ⇒ (x
i
,x
k
) ∈ U.
GRAPHE complet : (x
i
,x
j
) ∉ U ⇒ (x
j
,x
i
) ∈ U (il y a
uniquement une arête entre deux sommets). Un graphe complet ayant n
sommets a n(n-1)/2 arêtes. Noté K
n
.
GRAPHE HOMOGENE de degré h : tout sommet est de degré h.
CLIQUE : ensemble des sommets d’un sous graphes complet.
EXEMPLE.
x
2
x
1
x
4
x
3
FIG. 1.5. Graphe réflexif, anti symétrique, transitif et complet.
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
5
GRAPHE BI-PARTIE G=(X,U) si :
1. X partionné en X
1
etø X
2
.
2. ∀ (x
1
,x
2
) ∈ U alors x
1
∈ X
1,
x
2
∈ X
2
.
Si Card(X
1
) = n, Card(X
2
) = m, G est noté K
n,m
.
Exemple : Les graphes suivants sont bi-parties, mais non complets.
K
2,2
K
3,2
1.1.2 EXEMPLES.
EXEMPLE 1. Plus court chemin. Carte routière.
Problème 1. Un graphe orienté G = (X,U), une valuation v : U → R et
s, t deux sommets distincts de X .
Question 1. Trouver le plus court chemin entre s et t ?
Ce problème est polynomial : Algorithme de Dijkstra, Bellman-Ford (voir
Chapitre 3)
EXEMPLE 2. Arbre de poids minimum.
Réseau électrique, alimentation en eau potable à partir d’une source
unique
Problème .2. Un graphe non - orienté G = (X,U), une valuation de poids
v : U → R
+
et s, t deux sommets distincts de X .
Question 2. Trouver un arbre recouvrant de poids minimum?
Ce problème est polynomial :Algorithme de Kruskal, Prim (voir Chapitre 2)
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
6
1.2 REPRESENTATIONS DES GRAPHES.
Un certain nombre de représentations existent pour décrire un graphe. En
particulier, elles ne sont pas équivalentes du point de vue de l’efficacité des
algorithmes. On distingue principalement la représentation par matrice d’adjacence,
par matrice d’incidence sommets - arcs (ou sommets – arêtes dans le cas non
orienté) et par listes d’adjacence.
1.2.1. Utilisation de tableau.
1.2.1.1. Matrice d’adjacence.
On considère un 1-graphe. La matrice d’adjacence fait correspondre les sommets
origine des arcs (placés en ligne dans la matrice) aux sommets destination (placés
en colonne). Dans le formalisme MATRICE BOOLEENNE, l’existence d’un arc
(x
i
,x
j
) se traduit par la présence d’un 1 à l’intersection de la ligne x
i
et de la
colonne x
j
; l’absence d’arc par la présence d’un 0 (dans un formalisme dit
MATRICE AUX ARCS les éléments représentent le nom de l’arc).
Place mémoire utilisée : n
2
pour un graphe d’ordre n (i.e., n sommets).
EXEMPLE. x
2
u
2
u
1
u
4
x1 u
3
x
3
FIG.1.6. 1. GRAPHE.
La matrice d’adjacence de ce graphe est suivant :
x
1
x
2
x
3
← destination
x1
0 1 1
x
2
1 0 1
x
3
0 0 0
↑
origine
Dans le cas où le graphe est non orienté, la matrice est symétrique. Dans cas où le
graphe est valué, on utilise une matrice où l’élément d’indices x
i
, x
j
a pour valeur le
poids de l’arc u = (x
i
, x
j
) ∈ U, sinon une valeur dont on sait qu’elle ne peut être un
poids, par exemple ∝.
EXEMPLE. x
2
7 12
5
x1 2 x
3
FIG.1.7. 1. GRAPHE.
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
7
La matrice d’adjacence de ce graphe est la suivante :
x
1
x
2
x
3
← destination
x1
∝
5 2
x
2
7
∝
12
x
3
∝ ∝ ∝
1.2.1.2. Matrice d’incidence sommets – arcs.
Ligne ↔ sommet
Colonne ↔ arc.
Si u = (i,j) ∈ U, on trouve dans la colonne u : a
iu
= 1 : a
ju
= -1 ; tous les autres
termes sont nuls.
Place mémoire utilisée : n x m.
EXEMPLE. Pour le 1.graphe de la figure FIG.1.6. on a :
u
1
u
2
U
3
u
4
x1
1 -1 1 0
x
2
-1 1 0 1
x
3
0 0 -1 -1
REMARQUES : La somme de chaque colonne est égale à 0 (un arc a une origine
et une destination) ; la matrice est totalement UNIMODULAIRE, i.e., toutes les
sous–matrices carrées- extraites de la matrice - ont pour déterminant +1, -1 ou 0.
Une autre définition de la Matrice d’incidence sommets – arcs est comme suit :
Soit G = (X,U) un 1-GRAPHE, une matrice d’incidence sommets – arcs A=[a
I,j
] est
déterminée par :
a
iu
= 1 si u = (x
i
, x
j
) ∈ U,
= 0, si non.
EXEMPLE. Pour le 1.graphe de la figure FIG.1.6. on a :
u
1
u
2
U
3
u
4
x1
1 0 1 0
x
2
0 1 0 1
x
3
0 0 0 0
REMARQUES : La somme de chaque ligne est égale à la somme des arcs incidents.
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
8
1.2.2. Utilisation de pointeurs .
L’avantage de la représentation par des pointeurs ou listes d’adjacence (grâce à
l’application multivoque Γ), par rapport à celle par matrice d’adjacence, est le gain
obtenu en place mémoire ; ce type de représentation est donc mieux adapté pour
une implémentation. Le but est de représenter chaque arc
PARCOURS par son
extrémité initiale étant définie implicitement. Tous les arcs émanant d’un même
sommet sont liés entre eux dans une liste. A chaque arc sont donc associés le
noeud destination et le pointeur au prochain sommet dans la liste.
EXEMPLE. Pour le 1.graphe de la figure FIG.1.6. on a :
x
1
x
2
x
3
x
2
x
1
x
3
x
3
1.3 PARCOURS DE GRAPHES.
Beaucoup de problèmes sur les graphes nécessitent un examen exhaustif
des sommets et des arcs (arêtes) du graphe. En général, il y a deux types de
parcours : Parcours en profondeur et Parcours en largeur.
1.3.1. EN PROFONDEUR.
PRINCIPE :
À partir d’un sommet donné, à suivre un chemin le plus loin possible, puis à faire
des retours arrières pour reprendre tous les chemin ignorés précédemment.
Exemple. Considèrons un graphe comme ci-dessous :
s
7
s
1
s
5
s
8
s
6
s
3
s
2
s
4
s
9
FIG. 1.8.
La méthode de parcours en profondeur est effectueé sur le graphe de la
figure FIG.1.15 à suivre :
À partir du sommet s
1
. Le premier sommet qui est choisi est s
3
.
À partir du sommet s
3
. Les successeurs de s
3
est s
2
et
s
6.
On peut choisir s
2
À partir du sommet s
2
. Retourner s
3
. Choisir s
6
À partir du sommet s
6
. Retourner s
3
. Retouner
s
1
. Le successeur de s
1
est s
5.
À partir du sommet s
5
. Retouner
s
1
. Le successeur de s
1
est s
7.
À partir du sommet s
7.
À partir du sommet s
4
. Le sommet s
9
est marqué.
À partir du sommet s
8
.
Tous les sommets étant marqués. Le processus se termine.
z
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
9
Noté :
s[k], k : 1 n L’ensemble de n sommets,est numéroté de 1 à n.
Mark[k], k : 1 n = 1 si sommet k étant marqué,
= 0 sinon.
a[i,j], i,j : 1 n = 1 si (i,j) est un arc (ou une arête) du graphe G
= 0 sinon.
Version récursive.
Programme principal :
For (int i =1 ; i<= n ; i++) Mark[i] := 0 ;
For (int i =1 ; i<= n ; i++) if (Mark[i] == 0) PROF(i) ;
Procédure récursive :
Parcours en profondeur à partir du sommet k.
Procédure PROF(int k ) ;
{
Mark[k] := 1 ;
{Visit des sommets dans la matrice d’adjacence du sommet k}
For (int j = 1 ; j<=n ;j++)
if (Mark[j] == 0) && (a[k][j]==1) PROF(j) ;
}End PROF
La complexité : Graphe ayant n sommets et m arcs(arêtes).
Par matrices d’adjacence : O(n
2
).
Par listes d’adjacence : O(max(n,p) ).
1.3.2. EN LARGEUR.
PRINCIPE :
Explorer le graphe niveau par niveau, à partir d’un sommet donné. C’est-
à-dire, À partir d’un sommet s, on commence par visiter tous les
successeurs de s avant de visiter les autres descendants de s.
Exemple. Un parcours en largeur du graphe de la figure FIG.1.8, à partir
de sommet s
1
dans l’ordre:
s
1
.
s
3
, s
5
, s
6
, s
7.
s
2
.
s
4.
s
9
s
8
.
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
10
1.4 CONNEXITE DANS LES GRAPHES.
1.4.1. Chne - Cycle.
Une Chne est une séquence d’arêtes telle que chaque arête ait une extrémité
commune avec la suivante. Un Cycle est une chne qui contient au moins une
arête et dont les extrémités cọncident.
EXEMPLE.
x
1
u
6
x
4
u
7
u
1
u
2
u
3
u
4
x
5
u
8
x
2
u
5
x
3
FIG.1.9. <u
5
,u
2
,u
6
,u
7
> est une chne, <u
4
,u
7
,u
8
> est un cycle.
1.4.2. Chemin – Circuit.
Ce sont les mêmes définitions que les précédentes mais en considérant des
concepts orientés.
Le sous ensemble de sommets atteignables à partir d’un sommet donné, grâce à
des chemins, est appelé FERMETURE TRANSITIVE de ce sommet.
Le terme PARCOURS regroupe les chemins, les chnes, les circuits et les cycles.
Un parcours est :
ELEMENTAIRE : Si tous les sommets qui le composent sont tous distincts.
SIMPLE : Si tous les arcs qui le composent sont tous distincts.
HAMILTONIEN : Passe une fois et une seule par chaque sommet du graphe.
EULERIEN : Passe une fois et une seule par chaque arc du graphe.
PREHAMILTONIEN : Passe au moins une fois par chaque sommet du graphe.
PREEULERIEN ou CHINOIS:Passe au moins une fois par chaque arc du graphe
1.2.1 Connexité .
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
11
Un graphe non orienté est CONNEXE si ∀i,j, il existe une chne entre i et j.
On appelle COMPOSANTE CONNEXE le sous ensemble de sommets tels qu’il
existe une chne entre deux sommets quelconques.
EXEMPLE :
x1
x
2
x
3
x
4
x
5
FIG.1.10. Graphe ayant deux composantes connexes.
THEOREME 1.2.3.1.
Un graphe est connexe si, et seulement si, il ne possède qu’une composante.
1.2.2 Forte Connexité.
Une graphe orienté est FORTEMENT CONNEXE si ∀i,j, il existe un chemin
entre i et j.
On appelle COMPOSANTE FORTEMENT CONNEXE (cfc) un sous ensemble
de sommets tels qu’il existe un chemin entre deux sommets quelconques. Une
cfc maximale (cfcm) est un ensemble maximal de cfc.
THEOREME 1.2.4.1.
Un graphe est connexe si, et seulement si, il ne possède qu’une cfcm.
1.5 GRAPHE EULERIEN.
1.3.1. Problème des 7 ponts.
FIG.1.11. Problème de 7 ponts.
C’est une vrai situation à Koenigsberg (Allemande). Il ya deux régions séparées par
une rivière qui a deux iles dedans. Il y a 7 ponts qui ont relié ces régions. Un
Problème a été posé comme suit :
« Commencer par une région et se promener une fois et une seule par chaque
pont et de revenir au point de départ ».
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
12
En 1736, un Mathématcien nomé EULER a modelisé ce problème par un graphe non
orienté, sommet correspond à un région et arête à un pont. Ce Problème a été énoncé
pour un graphe ci-dessous (cf FIG 1.9) comme le suivant:
« Chercher un cycle qui Passe une fois et une seule par chaque arête ».
La résolution du problème entraine les Théorèmes d’ EULER.
A
C D
B
FIG. 1.12. Problème des 7 ponts.
1.3.2. Définition.
Un graphe non orienté (respectivement orienté) est dit un graphe EULERIEN s’il
ait un cycle (resp. circuit) Eulerien.
Exemple 1.
A
B F
C E
D
FIG. 1.13. Graphe Eulerien.
Exemple 2.
A
B F
C E
FIG. 1.14. Ce n’est pas un graphe Eulerien, mais ayant une chaine d’ Euler.
Chapitre 1. Fondements de la Theorie des Graphes.
Truong My Dung,
Mail=tmdung@fit.hcmuns.edu.vn
13
1.3.3. Théorèmes d’ EULER.
Théorème 1. Un graphe non orienté est dit Eulérien si et seulement s’il soit
connexe et tous les sommets sont de degré pair.
Théorème 2 Soit G=(X,U) un graphe orienté. Alors G est Eulérien si et
seulement si :
1. G fortement connexe et
2. d
+
(x) = d
-
(x), ∀ x.
Théorème 3. Soit G=(X,U) un graphe non orienté, pas de sommets isolés.
Alors, G a une chne Eulérienne si et seulement si :
1. G connexe et
2. Ayant justement deux sommets à degré impair.
Exemple 1. A
B F
C E
D
FIG.1.15. Graphe non orienté ayant tous les sommets à degré pair,
alors G est Eulérien.
Exemple 2.
A
B F
C E
FIG. 1.16. Graphe ayant exactement 2 sommets à degré impair, alors G n’est pas
Eulérien, mais d’après le théorème 3, G a une chaine Eulerienne.
Không có nhận xét nào:
Đăng nhận xét