Chapitre VIII. Introduction aux graphes Définitions Structures de données Connexité Arbre...

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