[PDF] Algorithmique des graphes - Cours 5 – Composantes fortement

View - Download Algorithmique des graphes - Cours 5 – Composantes fortement

Previous PDF

Next PDF

Algorithmique des graphes

Cours 5 - Composantes fortement connexes

František Kardoš

frantisek.kardos@u-bordeaux.fr

Définitions

Un graphe orienté est ditfortement connexesi ses sommets sont tous accessibles entre eux, i.e., pour toute paire de sommetsuetvil existe un chemin deuàvet aussi un chemin devàu.Le graphe ci-dessous est-il fortement connexe?A B C DE F G

Définitions

Un graphe orienté est ditfortement connexesi ses sommets sont tous accessibles entre eux, i.e., pour toute paire de sommetsuetvil existe un chemin deuàvet aussi un chemin devàu.Le graphe ci-dessous est-il fortement connexe?A B C DE F G

Définitions

Dans un graphe orienté, unecomposante fortement connexe est un sous-ensembleXde sommets deGinduisant un graphe fortement connexe,Xétant maximal par rapport à la connexité forte.Quelles sont les composantes fortement connexes?A B C DE F G

Définitions

Dans un graphe orienté, unecomposante fortement connexe est un sous-ensembleXde sommets deGinduisant un graphe fortement connexe,Xétant maximal par rapport à la connexité forte.Quelles sont les composantes fortement connexes?A B C DE F G

Quelques observations

Vrai ou faux?

I Soituvun arc d"une composante fortement connexe. Alors il existe un chemin devàu.I Soituvun arc d"une composante fortement connexe. Alors uvest contenu dans un circuit.I Soituetvdeux sommets d"un graphe orienté. Siuetv appartiennent au même circuit, alorsuetvsont dans la même composante fortement connexe.I Soituetvdeux sommets d"un graphe orienté. Siuetv sont dans la même composante fortement connexe, alors uetvappartiennent au même circuit.FAUX!

Quelques observations

Vrai ou faux?

I Soituvun arc d"une composante fortement connexe. Alors il existe un chemin devàu.I Soituvun arc d"une composante fortement connexe. Alors uvest contenu dans un circuit.I Soituetvdeux sommets d"un graphe orienté. Siuetv appartiennent au même circuit, alorsuetvsont dans la même composante fortement connexe.I Soituetvdeux sommets d"un graphe orienté. Siuetv sont dans la même composante fortement connexe, alors uetvappartiennent au même circuit.FAUX!

Quelques observations

Vrai ou faux?

I Soituvun arc d"une composante fortement connexe. Alors il existe un chemin devàu.I Soituvun arc d"une composante fortement connexe. Alors uvest contenu dans un circuit.I Soituetvdeux sommets d"un graphe orienté. Siuetv appartiennent au même circuit, alorsuetvsont dans la même composante fortement connexe.I Soituetvdeux sommets d"un graphe orienté. Siuetv sont dans la même composante fortement connexe, alors uetvappartiennent au même circuit.FAUX!

Quelques observations

Vrai ou faux?

I Soituvun arc d"une composante fortement connexe. Alors il existe un chemin devàu.I Soituvun arc d"une composante fortement connexe. Alors uvest contenu dans un circuit.I Soituetvdeux sommets d"un graphe orienté. Siuetv appartiennent au même circuit, alorsuetvsont dans la même composante fortement connexe.I Soituetvdeux sommets d"un graphe orienté. Siuetv sont dans la même composante fortement connexe, alors uetvappartiennent au même circuit.FAUX!

Quelques observations

Vrai ou faux?

I Soituvun arc d"une composante fortement connexe. Alors il existe un chemin devàu.I Soituvun arc d"une composante fortement connexe. Alors uvest contenu dans un circuit.I Soituetvdeux sommets d"un graphe orienté. Siuetv appartiennent au même circuit, alorsuetvsont dans la même composante fortement connexe.I Soituetvdeux sommets d"un graphe orienté. Siuetv sont dans la même composante fortement connexe, alors uetvappartiennent au même circuit.FAUX!

Calcul de composantes fortement connexes

Lemme Soit G un graphe orienté, soit C un circuit dans G. Soit G=C le graphe obtenu en réduisant C en un seul sommet, disons c. Alors G=C a autant de composantes connexes que G, en plus, I Si une composante X ne couvre pas C, alors X est une composante de G=C; I Si X est une composante couvrant C, alors XnV(C)[ fcg est une composante de G=C.Note. En réduisant un circuitC, on peut supprimer les boucles et pour tout ensemble d"arcs parallèles il suffit d"en garder un.

Calcul de composantes fortement connexes

On applique le lemme tant que le graphe contient encore des circuits.Le graphe final est un graphe sans circuit, dont tout sommet représente une composante fortement connexe du graphe de départ.On l"appelle legraphe des composantes fortement connexes

CFC(G).

Calcul de composantes fortement connexes

On applique le lemme tant que le graphe contient encore des circuits.Le graphe final est un graphe sans circuit, dont tout sommet représente une composante fortement connexe du graphe de départ.On l"appelle legraphe des composantes fortement connexes

CFC(G).

Calcul de composantes fortement connexes

On applique le lemme tant que le graphe contient encore des circuits.Le graphe final est un graphe sans circuit, dont tout sommet représente une composante fortement connexe du graphe de départ.On l"appelle legraphe des composantes fortement connexes

CFC(G).

Tester la connexité forte avec Parcours en profondeur Calculer la composante fortement connexe d"un sommetu:

Idée : Pour un sommetu, déterminer

I l"ensembleDesc(u)des sommets accessibles depuisu I l"ensembleAnc(u)des sommetsuest accessible depuis avec deux parcours en profondeur, un surG, et l"autre surG1.

La CFC(u)est alorsDesc(u)\Anc(u).

Parcours en profondeur et CFC

SoitGun graphe orienté, soitXune CFC deG. Soitxle premier sommet deXdécouvert par un parcours deGen profondeur. Alorsxest l"ancêtre commun de tous les sommets deX. Autrement dit, tous les sommets deXsont découverts et visités avant la fin de la visite dex. Par ailleurs, si d(x) = minfd(u) :u2Xg; alors f(x) = maxff(u) :u2Xg:

Parcours en profondeur et CFC

SoitX1etX2deux CFC d"un graphe orientéG. Notonsx1(resp. x

2) le premier sommet deX1(X2) découvert par un parcours de

Gen profondeur.

I

SiX1!X2dansCFC(G), alorsx1est un ancêtre dex2,

I(x1)I(x2).

I SiX1 X2ouX1etX2ne sont pas du tout reliés par un arc dansCFC(G), alorsI(x1)\I(x2) =;.

Algorithme de Kosaraju

SoitGun graphe orienté.

1.

Exécuter un parcours en prof ondeurde G.

2. Exécuter un parcours en prof ondeursur le g raphe transposéG1en explorant les sommets dans l"ordre décroissant de la fin de visite du premier parcours. Les arborescences produites par le second parcours sont les

CFC deG.

Algorithme de Kosaraju - exemple

A:B;G B:E C: D:F E:D;G F:E G:B;C

Algorithme de Kosaraju - complexité

SoitGun graphe orienté.

1. Exécuter un parcours en prof ondeurde G-O(m+n). Calculer le g raphetr ansposéG1-O(m+n)si graphe représenté par listes de successeurs. 2. Exécuter un parcours en prof ondeurde G1-O(m+n). La complexité de l"algorithme de Kosaraju est doncO(m+n), la même que celle d"un parcours en profondeur.

Algorithme de Tarjan

permet de calculer les CFC en un seul parcours en profondeur. Pendant le parcours en profondeur deG, on utilise un tableau supplémentairet[]pour calculer, pour chaque sommet deG, le sommet le plus haut (l"ancêtre le plus ancien) vers lequel il est

possible de remonter grâce à des arcs de retour.Si jamais pour un sommetuà la fin de sa visite on at[u] =u,

on sais queuest la racine d"une composante fortement connexe.

Algorithme de Tarjan

permet de calculer les CFC en un seul parcours en profondeur. Pendant le parcours en profondeur deG, on utilise un tableau supplémentairet[]pour calculer, pour chaque sommet deG, le sommet le plus haut (l"ancêtre le plus ancien) vers lequel il est

possible de remonter grâce à des arcs de retour.Si jamais pour un sommetuà la fin de sa visite on at[u] =u,

on sais queuest la racine d"une composante fortement connexe.

Algorithme de Tarjan - implémentation

Danst[], au lieu de stocker

le sommet le plus haut (l"ancêtre le plus ancien) vers lequel il est possible de remonter grâce à des arcs de retour, on va stocker le début de visitedu sommet le plus haut (l"ancêtre le plus ancien) vers lequel il est possible de remonter grâce à des arcs de retour.Pour calculert[u], au début de visite deu, on l"initialise àd[u]. On le met à jour à la fin de visite de chacun de ses fils, et aussi lors d"une découverte d"un arc de retour.

Algorithme de Tarjan - implémentation

Danst[], au lieu de stocker

le sommet le plus haut (l"ancêtre le plus ancien) vers lequel il est possible de remonter grâce à des arcs de retour, on va stocker le début de visitedu sommet le plus haut (l"ancêtre le plus ancien) vers lequel il est possible de remonter grâce à des arcs de retour.Pour calculert[u], au début de visite deu, on l"initialise àd[u]. On le met à jour à la fin de visite de chacun de ses fils, et aussi lors d"une découverte d"un arc de retour. Algorithme de Tarjan - implémentationAlgorithme 1 :DFS(G)Données :grapheG débutpour chaques sommet de

Gfairecouleur[s] BLANC ;

[s] NULL ; fin temps 0 ; pour chaques sommet de

Gfairesicouleur[s] =BLANC

alorsVisiter(s) ; fin fin finAlgorithme 2 :Visiter(u)début couleur[u] GRIS ; d[u] temps temps+1 ; pour chaquev voisin de u fairesicouleur[v] =BLANC alors[v] u;

Visiter(v) ;

fin fin couleur[u] NOIR ; f[u] temps temps+1 ; fin

Algorithme de Tarjan - implémentation

Algorithme 1 :DFS(G)Données :grapheG

débutpour chaques sommet de

Gfairecouleur[s] BLANC ;

[s] NULL ; fin temps 0 ; pour chaques sommet de

Gfairesicouleur[s] =BLANC

alorsVisiter(s) ; fin fin finAlgorithme 2 :Visiter(u)début couleur[u] GRIS ; d[u] temps temps+1 ; t[u] d[u]; pour chaquev voisin de u fairesicouleur[v] =BLANC alors[v] u;

Visiter(v) ;

t[u] min(t[u];t[v]); fin sicouleur[v] =GRIS alorst[u] min(t[u];d[v]); fin fin couleur[u] NOIR ; f[u] temps temps+1 ;quotesdbs_dbs44.pdfusesText_44

[PDF] théorie des graphes python

[PDF] parcours en largeur graphe

[PDF] parcours en profondeur itératif

[PDF] algorithme parcours en profondeur python

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf