Upload
sophie-moreau
View
114
Download
0
Embed Size (px)
Citation preview
Chapitre VIII.Introduction aux graphes
Définitions
Structures de données
Connexité
Arbre couvrant de poids minimal
Parcours des graphes orientés
DéfinitionsGraphes orientés
• Un graphe orienté :• - ensemble des sommets• - ensemble des arcs : relation binaire
sur N
• Exemple :
),( ANG
inN
ji nnA ,
1
2 3
4
N=?, A=?
Arcs et sommets
jiij nna ,
in
jn
- l’extrémité initiale (début)
- l’extrémité terminale (fin)
est un prédécesseur de
est un successeur de
jn
jn
jn jn
Etiquettes
• Etiquettes
• Le nom d’un sommet doit être unique dans un graphe
• Plusieurs sommets peuvent avoir la même étiquette
1 2
Anne Claude
Est fille de
Chemins
• Un chemin dans un graphe orienté est une liste
• La longueur d’un chemin est k-1 = nbr arcs faisant partie du chemin
• Le cas trivial k=1: tout sommet n isolé est un chemin de longueur zéro de n à n
1,...,1,,:,..., 121 kiAnnnnn iik
Graphes cycliques et acycliques
• Un cycle dans un graphe orienté est un chemin de longueur 1 ou plus qui part et aboutit au même sommet
• Un chemin trivial (l=0) n’est pas un cycle • Une chemin composé d’un seul arc est un cycle
de longueur 1
Si un graphe a un ou plusieursCycles on l’appelle « graphe cyclique »Sinon « acyclique »
)3,3(,3,2,4,3
1
2 3
4
Problème
• Dans un graphe orienté- itinéraire représenté sous forme d’une liste simplement chainée supprimer tous les cycles
Graphes non-orientés
• Une arête est un ensemble de deux sommets • L’arête indique que les sommets sont
liés dans deux directions
• Les sommets sont dits adjacents
• Un graphe ayant des arêtes, c’est –à-dire possédant une relation symétrique des arcs est appelé un graphe non-orienté
ji nn ,
Structures de données
• (1) Listes d’adjacence• Type Liste =^maillon• Maillon=Enregistrement
• IdNoeud : Nœud {entier- pour simplifier}• Suivant: Liste
• Fin• Nœuds : tableau[1…N] de Liste
Exemple
1
2
3
4
7
5
6
1
2
6
78
5 7
3
4
Graphe orienté
Matrice d’adjacence
• arcs : tableau[1..N][1..N] de Booléen
010000008
000000007
000001006
001010005
000000004
000000103
000000012
010100001
87654321
Représentation d’un graphe non-orienté
1
2
3
4
7
5
6
1
2
6
78
5 7
3
4
Principe : remplacer chaque arête par les arcs allant dans deux directions, matrice d’adjacence est symétrique
Transformer le GO en GNO!
Connexité(1)
• Composante connexe : ensemble de sommets pour lesquels il existe un chemin entre tout sommet et n’importe quel autre sommet
• Une composante connexe est maximale : aucun sommet faisant partie d’une composante connexe ne possède un chemin vers un sommet en dehors de la composante connexe
• Si un graphe consiste en une seule composante connexe, alors on l’appelle graphe connexe
Connexité(2)
• Connexité est une relation d’équivalence définie sur les sommets du graphe non-orienté P:
• niPnj ssi il existe un chemin de ni vers nj
• 1) Réflexive : nPn pour tout sommet n puisqu’il existe un chemin de longueur 0 entre tout sommet et lui-même
• 2) Symétrique : si niPnj alors il existe un chemin de ni vers nj. Puisque le graphe est non-orienté, la séquence inverse de sommets est aussi un chemin. Donc njPni
• 3) Transitive : si niPnj et njPnk alors niPnj.
Algorithme pour construire les composantes connexes(1)
• Principe : • - Commencer par le graphe G0 composé des sommets
de G avec aucune arête. • - Considérer les arêtes de G une par une pour construire
une séquence des graphes G0, G1, G, … où Gi est composé des sommets de G et des i premières arêtes de G
Algorithme pour construire les composantes connexes(2)
• La base : la liste des arêtes non-utilisées est vide• Initialisation. G0 est seulement composé des sommets de G sans
arêtes. Chaque sommet est une composante connexe.• La récurrence. On suppose qu’on a les composantes connexes du
graphe Gi après avoir considéré les i premières arêtes. Considérons i+1 ère arête (ni, nj)
• 1. Si ni et nj font partie de la même composante de Gi , alors Gi+1 a le même ensemble des composantes connexes.
• 2. Si ni et nj font partie de composantes différentes, on fusionne les composantes contenant ni et nj afin d’obtenir les composantes connexes pour Gi+1
• Lorsqu’on a considéré toutes les arêtes de cette manière, on obtient les composantes connexes du graphe G
Construction des composantes connexes (2)
• Problèmes à résoudre : • (1) Etant donné un sommet, trouver sa
composante courante• (2) Fusionner deux composantes en une seule
• Choix de structures de données : chaque composante connexe d’un graphe sera représentée par un arbre.
• Le résultat de l’algorithme : une forêt des arbres
Construction des composantes connexes(3)
1 2
3
4
5
6
12
3
4
56
Deux polygones sont considérés adjacents ssi ils ont une arête commune
7
8
7
8
Construction des composantes connexes(4)
1
2
3
4
5
6
7
8
O
J
BC
Ve
R
Vi
B
Ro
2 6
1 3
42
5 6
4 6
1 5 4
8
7
6
Construction des composantes connexes(5)
• Liste des arêtes
1 2 3
2 6 4
3 4 3
4 6 5
5 7 8
6 5 4
7 1 2
8 1 6
N°arête N1 N2
Structures de données(1)• -Liste d’adjacence• -Liste des arêtes.• -Liste des nœuds d’un arbre
• Type ListeArêtes = ^Arête• Arête = Enregistrement• noeud1, noeud2 : TypeNoeud• Suivant : ListeArêtes• FinEnregistrement
• Arêtes : ListeArêtes• Tout sommet du graphe doit posséder un nœud d’arbre
correspondant• TypeNœud peut être une étiquette de nœud (entier)
Structures de données(2)
• Type PtrNoeudArbre = ^NoeudArbre• NoeudArbre = Enregistrement• père : PtrNoeudArbre• hauteur: entier• Fin Enregistrement• Nœuds: Tableau[1..n] de PtrNoeud• Ce tableau associe un nœud dans un
arbre général à chaque sommet du graphe
Fonctions auxiliaires
• (1)Fonction TrouveRacine( a: nœud): PtrNoeudArbre• { renvoie la racine de l’arbre contenant le nœud x correspondant au
sommet courant du graphe}• Var Racine, Courant : PtrNoeudArbre;• Début• Racine : = nœuds[a];• TQ Racine.père<>NIL faire
– Racine:=Racine^.père;
FTQ
Retourner Racine
FinTrouveRacine
Fonctions Auxiliaires (2)• (2)Procédure FusionArbres(x,y,: PtrNoeudArbre)• {fusionne les arbres dont les racines sont x et y, en faisant devenir racine du
plus bas le descendant de la racine du plus haut}• Var pbas, phaut : PtrNoeudArbre• Début• Si x^.hauteur>y^.hauteur
alors phaut:=x pbas=:=ysinon phaut:= y pbas:=x
FSi pbas^.père:= phaut; Si pbas^.hauteur = pahaut^.hauteur alors phaut^.hauteur:=phaut^.hauteur+1 FSI FinFusionArbres
Algorithme de construction des composantes connexes
• Soient G – le graphe contenant n sommets, e: sa liste des arêtes « arêtes »
• 1) Initialiser n arbres• 2)Pour toutes les arêtes dans la liste : • Si les extrémités sont dans deux arbres
différents, fusionner les composantes-arbres.
Algorithme de construction des composantes connexes(2)
• Procédure CompCon(réf Noeuds : Tableau [1..n]de PtrNoeuds; arêtes : ListeArêtes)
• Var u:TypeNoeud• a,b: PtrNoeudArbre• e:ListeArêtes• Pour u de 1 à n faire• new(Noeuds[u])• Nœuds[u].père:=NIL• Nœuds[u].hauteur:=0;• FPour• e:=arêtes• TQ e<>NIL faire• a:=TrouveRacine(e^.noeud1)• b:=TrouveRacine(e^.noeud2)• Si a<>b alors• FusionArbres(a,b); FSi• E:=e^.suivant• FTQ• FinCompCon
Analyse• Après l’exécution le tableau « Nœuds » code les arbres-
composantes-connexes. • Temps d’exécution• (1) FusionArbre : le chemin de n’importe quel nœud d’un arbre
construit par la procédure FusionArbre : le temps est inférieur à log(n). Alors TrouveRacine prend un temps en O(log(n))
• (2) Procédure FusionArbres : O(1) • (2)Initialisation (boucle Pour) O(n)• (3)Boucle while : O(mlog(n)), m – nombre des arêtes• O(n+mlog(n))• En général donc O(n+mlog(n)) –cas spécifiques • - absence des arêtes O(n)• - fortement connexe O(mlog(n))
Arbre couvrant de poids minimal
• Soit W={wi,j} l’ensemble des « poids » des arêtes du graphe G.
• Nous allons nous limiter aux graphes connexes• Un arbre couvrant (non-ordonné, sans racine = un
graphe non-orienté n’ayant pas de cycles) • Un arbre couvrant pour un graphe non-orienté G est
composé des sommets de G avec un sous-ensemble des arêtes de G qui – relient les sommets : il existe un chemin entre tous les sommets,
pris deux par deux, en prenant uniquement les arêtes de l’arbre couvrant
– forment un arbre sans racine, non-ordonné• Un arbre couvrant de poids minimal: la somme des poids
des arêtes est la plus petite que possible
Algorithme de Kruskal
• 1. Considérer les arêtes dans l’ordre croisant de leurs poids
• 2. Considérant les arêtes, • Si une arête possède ses deux extrémités dans
des composantes différentes, alors – on sélectionne cette arête pour l’arbre couvrant et on
fusionne les composantes de la même façon que dans l’algorithme de construction des composantes connexes.
• sinon – on ne sélectionne pas l’arête pour l’arbre couvrant.
Parcours des graphes orientés(1)
• Recherche en profondeur (dfs)• Principe : similaire au parcours en
profondeur des arbres.• Pb : existence des cycles ( possibilité de
boucler à l’infini!)• Solution : marquer les sommets visités• Structures de données : Graphe : tableau
de sommets avec des listes d’adjacence
Parcours des graphes orientés(2)
• Type Liste =^maillon• Maillon=Enregistrement
• IdNoeud : Nœud {entier}• Marque: (visité, non-visité)• Suivant: Liste
• Fin• Graphe : tableau[1…N] de Liste
Parcours des graphes orientés(3)• Parcours en profondeur• Procédure dfs(G: Graphe; u: entier){numéro du nœud )• Var p:Liste {liste d’adjacence du nœud u}• V: entier {sommet dans la cellule sur lequel pointe p}• Début• G[u].Marque:=Visité• p:=G[u].suivant• TQ p<>NIL faire
v:=p^.IdNoeudSi G[v].Marque:=Non-visité
alors dfs(v) FSi p:=p^.suivant FTQ Findfs
• Le temps d’exécution est proportionnel au nombre des arcs explorés.• Version itérative :utilisation d’une pile de parcours
Parcours des graphes orientés(4)
• Parcours en largeur : visiter d’abord tous les voisins du sommet courant qui n’ont pas été marqués
• Procédure bfs( G : graphe, u:entier)• Var v,w,i: entiers• F: file• Début• F:=file-vide; G[u].Marque:=Visité• Enfiler(F,u)• TQ non est-vide(F) faire• v: = premier(F); Defiler(F);• p:=G[v].suivant• TQ p<>NIL faire• w:=p^.IdNoeud• Si G[w].Marque:=Non-visité • alors• G[w].Marque=Visité• Enfiler(F,w)• FSi
FTQ• FTQ Finbfs