Embed Size (px)
Citation preview
GRAPHES E
N
INFO
RMATIQ
UE
INTRODUCTION
Les objets mathématiques appelés graphes apparaissent dans de nombreux domaines comme les mathématiques, la biologie, la sociologie, pour modéliser entre autres les relations binaires entre éléments d’un ensemble fini (on dispose d’une population et on souhaite savoir qui est en relation avec qui, par exemple).
Géométriquement un graphe se présente comme un ensemble fini de points (les sommets) qui peuvent être éventuellement reliés par des segments (les arêtes )
EXEMPLELes sommets sont numérotés de 1 à 8: 1 et 2 sont en relation, mais pas 1 et 4
1
2
4 5
3
8
6
7
EXEMPLE: GRAPHE PONDÉRÉIl est possible d’affecter un poids aux arêtes (ex: les sommets représentent des
villes et le
poids de l’arrête joignant 2 sommets
représente le distance entre les villes
correspondantes.)
1
2
4 5
3
8
67
15
2718
59
12362
39
78
48
DÉFINITION ABSTRAITE D’UN GRAPHE
La représentation des graphes par des schémas similaires aux précédents doit être précisée ; en effet il est clair que modifier la longueur des arêtes ou faire légérement pivoter une arête n ’a aucune incidence sur le type du graphe. Le point essentiel dans la définition est le nombre de sommets et les relations qui existent entre ces sommets. D’où la définition abstraite suivante:
Définition: On appelle graphe abstrait (non orienté) la donnée d’un couple (S,A) où S est un ensemble fini et A est une partie de l’ensemble des paires de sommet {{s,t} | s et t S} (notons bien que contrairement à un couple une paire n’est pas ordonnée). L’ensemble S est appelé ensemble des sommets et A ensemble des arêtes. On dira que deux sommets s et t sont reliés si la paire {s,t} est dans A.
En remplaçant paire par couple (un couple est ordonné) on obtient la notion d’arc orienté.
EXEMPLE D’ARC ORIENTÉ:
Graphiquement l’arête (s,t) est représentée avec une flèche orientée de s vers t:
Par exemple (4,7) est dans A mais pas (7,4)
Par contre (4,2) et (2,4) sont toutes deux dans A
1
2
4 5
3
8
6
7
VOCABULAIRE RELATIF AUX GRAPHES
On appelle ordre d’un graphe son nombre de sommets
On appelle boucle d’un graphe tout couple de la forme (s,s) (càd toute arête reliant un sommet à lui_même
Un graphe est dit simple s’il ne contient pas de boucle
Un sous- graphe de (S,A) est un couple (S’,A’) avec S’ sous-ensemble de S et A’=A(S’S’). (remplacer (S’S’) par l’ensemble des paires de sommets si G est non orienté ; voir exemple diapo suivante)
Si s est un sommet, on appelle degré de s le nombre d’arêtes reliant s à un autre sommet (si le graphe est orienté on note
Un chemin tracé dans un graphe est un sous-graphe simple ; on peut préciser le sommet de départ et d’arrivée.
EXEMPLE DE SOUS-GRAPHE
Sous graphe (S’,A’) avec:
S’={2,3,8,5}
A’={{2,3},{3,8},{8,5}}
1
2
4 5
3
8
6
7
REPRÉSENTATION INFORMATIQUE D’UN GRAPHE…Il existe deux manières de coder un graphe:
Par matrice d’adjacence: si n est l’ordre du graphe, et sont ses sommets, on définit la matrice d’adjacence M comme la matrice à valeurs booléenne définie par s’il existe une arête de vers et sinon. Notons pour un graphe non orienté cette matrice est symétrique. Cette représentation nécessite le stockage d’un tableau à entrées en mémoire.
Par liste d’incidence: le principe est de construire pour chaque sommet la liste des sommets qui lui sont reliés. Quand le graphe est orienté on choisit en général de retenir dans chaque entrée la liste des successeurs (ou des prédécesseurs) du sommet correspondant.
Notons que si le nombre d’arêtes est peu élevé (par exemple dans le cas d’un arbre), la matrice d’adjacence contient beaucoup de zéros ce qui induit une place mémoire importante pour peu d’informations. Dans ce cas le codage par listes est plus efficace.
REPRÉSENTATION D’UN GRAPHE
Dans le cas d’un graphe pondéré, on utilise la représentation par matrice des poids. C’est le même principe que la matrice d’adjacence, sauf que l’on place en position [i,j] le poids de l’arête reliant à s’il y en a une et sinon une valeur qui ne pas être confondue avec un poids (par exemple ou si les poids sont positifs)
Sur l’exemple vu plus haut on obtient comme matrice des poids:
PROBLÈME DU PLUS COURT CHEMIN
On considère un graphe orienté pondéré G=(S,A) dont on supposera les poids positifs. On appelera chemin tracé dans G toute suite de sommets telle que pour tout soit bien orienté (càd tq l’arête associée soit un élément de l’ensemble A ). On appelera l ’origine du chemin et son extrémité.
On appelera poids du chemin la somme des poids de ces arêtes.
On s’intéresse au problème suivant: étant donnés deux sommets et de G, comment trouver un chemin de vers de poids minimal (en pratique, les sommets peuvent représenter des villes et les poids des distances, mais dans certaines situations les poids peuvent représenter des coûts par exemple…)
EXEMPLE TEST:
On va déterminer un plus court chemin de a (=0) vers g (=6) pour le graphe suivant:
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
PRINCIPE DE L’ALGORITHME:
On va construire à chaque étape un ensemble T initialement réduit à {x} et qui est enrichi à chaque étape d’un élément,(appelé pivot) et vérifiant une certaine propriété de minimalité.
On définit une fonction qui à un sommet s associe la longueur d’un chemin de x à s de longueur minimale parmi les chemin n’utilisant que des sommets dans T .
Cette fonction est initialisée à pour tous les sommets.
On utilise aussi une fonction père qui à un sommet associe son prédecesseur dans un chemin de longueur minimale à sommets dans T.
A chaque étape, on compare pour chaque s successeur de pivot, la longueur minimale de chemins construits jusque-là avec la longueur du chemin atteignant s via pivot et on garde le minimum des deux (en changeant la valeur de père(s) en pivot si )
Pour choisir le pivot suivant, on regarde, parmi les sommets pas encore dans T, lequel réalise le minimum de
ALGORITHME
On initialise pivot à x et les valeurs de . A chaque étape (en tout):
on calcule pour les s successeur de pivot (hors de T):
-Si
on remplace par , et père(s) par pivot
On regarde le sommet qui réalise le min de hors de T et il devient le nouveau pivot ; on le rajoute à l’ensemble T
Au bout de étapes, la valeur de (y) est la longueur minimale souhaitée, et en remontant la fonction père depuis y jusqu’à x on obtient le chemin réalisant cette longueur
Dans les diapos suivantes, le tableau représente à chaque étape les valeurs du couple ((s), père(s)) pour les différents sommets s. En rouge est indiqué le nouveau pivot, que l’on rajoute à T en fin d’étape. Les sommets pris dans T sont colorés en orange.
ETAPE 1:
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (7,a) (3,a) (4,a) a,e
ETAPE 2
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (5,e) (3,a) (11,e)
(4,a) (6,e) a,e,h
ETAPE 3
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (5,e) (3,a) (11,e)
(4,a) (6,e) a,e,h,b
ETAPE 4:
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (5,e) (6,b) (6,b) (3,a) (11,e)
(4,a) (6,e) a,e,h,b,c
ETAPE 5:
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (5,e) (6,b) (6,b) (3,a) (8,c) (11,e)
(4,a) (6,e) a,e,h,b,c,d
ETAPE 6:
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (5,e) (6,b) (6,b) (3,a) (8,c) (11,e)
(4,a) (6,e) a,e,h,b,c,d,i
ETAPE 7:
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (5,e) (6,b) (6,b) (3,a) (8,c) (11,e)
(4,a) (6,e) a,e,h,b,c,d,i,f
ETAPE 8:
b c
e f g
hi
d
a
1
7 5
3
21
2
2
8
41
2
3 76
2
2
3
a b c d e f g h i T
0 (5,e) (6,b) (6,b) (3,a) (8,c) (8,e) (4,a) (6,e) a,e,h,b,c,d,i,f
,g
PREUVE DE L’ALGORITHME
La terminaison est évidente (boucle for)
La validité de l’algorithme se déduit des deux assertions suivantes:
A l’issue de chaque étape: pour tout sommet successeur de (l’ancien) pivot , est la longueur minimale d’un chemin de x vers s n’empruntant que des sommets préalablement contenus dans l’ensemble T et père(s) est le prédécesseur de s dans un chemin de ce type.
A l’issue de chaque étape, s de T est le minimum des longueurs des chemins issus de x et aboutissant à s.
La validité de la deuxième assertion appliquée au sommet y (qui est dans T à la sortie de la boucle) prouve le résultat.
IMPLÉMENTATION
On codera les graphes par leur matrice de poids
On créera une liste père indexée par les sommets et initialisée avec tous les éléments égaux au sommet de départ (a sur notre exemple). On initialisera par n’importe quoi qui n’est pas un sommet.
On créera une liste pi indexée par les sommets qui contiendra les valeurs des pi(s) (on l’initialisera avec des valeurs « infinies »)
On utilisera la fonctions successeurMat(M,i) du TD
On utilisera la classe set de python pour l’ensemble T(rappel: on peut créer un ensemble S en partant de la liste l de ses éléments puis en posant S=set(l))
