Embed Size (px)
Citation preview
Introduction Algorithme de Tarjan
Forte connexité
Malika More([email protected])
IREM Clermont-Ferrand
Formation ISN
20 octobre 2011
Introduction Algorithme de Tarjan
Plan du cours
1 Introduction
2 Algorithme de Tarjan
Introduction Algorithme de Tarjan
1 Introduction
2 Algorithme de Tarjan
Introduction Algorithme de Tarjan
Graphe non orienté
On peut parcourir les arêtes dans les deux sens
A
B
C
D
E
F
G
H
I
J
Introduction Algorithme de Tarjan
Connexité
A
B
C
D
E
F
G
H
I
J
Un graphe (non orienté) estconnexe lorsqu’il n’estcomposé que d’un seul« morceau »S’il y a plusieurs morceaux, onparle des composantesconnexes du graphe
Introduction Algorithme de Tarjan
Connexité
A
B
C
D
E
F
G
H
I
J
Les sommets d’unecomposante connexe sontmutuellement accessiblesUn parcours permet dedéterminer la composanteconnexe du sommet de départ
Introduction Algorithme de Tarjan
Graphe orienté
Chaque arc a un sens (flèche)On ne peut suivre un arc que dans le sens de la flèche
A
B
C
D
E
F
G
H
I
J
Introduction Algorithme de Tarjan
La notion de connexité est différente
A
B
C
D
E
F
G
H
I
J
On peut aller de J à C, maispas de C à JSi tous les couples desommets d’un graphe orientésont mutuellementaccessibles, on dit qu’il estfortement connexe
Introduction Algorithme de Tarjan
La notion de connexité est différente
A
B
C
D
E
F
G
H
I
J
Le graphe orienté ci-contrecomprend plusieurscomposantes fortementconnexesComment calculer lacomposante fortementconnexe d’un sommet ?
Introduction Algorithme de Tarjan
Un algorithme simple mais long
A
B
C
D
E
F
G
H
I
J Trouver tous les sommetsaccessibles à partir de X enutilisant un parcoursPour chaque sommet Yaccessible à partir de X ,utiliser un parcours pourvérifier si X est aussiaccessible à partir de Y
Introduction Algorithme de Tarjan
1 Introduction
2 Algorithme de Tarjan
Introduction Algorithme de Tarjan
Idée générale
A
B
C
D
E
F
G
H
I
J
On effectue un parcours enprofondeur à partir d’unsommet du graphe à l’aided’une pile Parcours enmémorisant le rang deDécouverte de chaquesommet visitéPendant le parcours, oncalcule les composantesfortement connexesrencontrées à l’aide d’unedeuxième pile Tarjan et d’unIndex associé à chaquesommet visité
Introduction Algorithme de Tarjan
Préliminaire
A
B
C
D
E
F
G
H
I
J1
2
3
45
67
8
9 10
Parcours en profondeur àpartir de A et rang deDécouverte
Arc de liaison : rougeArc avant : CG, JIArc arrière : BA, DC, IJArc transverse : GE , ED, HC
Introduction Algorithme de Tarjan
Les 5 règles de calcul
A
B
C
D
E
F
G
H
I
J1
2
3
45
67
8
9 10
1 La première fois qu’onrencontre un sommet X , onl’empile sur Tarjan et oninitialise son Index avec lavaleur Découverte(X )
Introduction Algorithme de Tarjan
Les 5 règles de calcul
A
B
C
D
E
F
G
H
I
J1
2
3
45
67
8
9 10
2 Quand on visite à partir de Xun arc arrière (i.e. qui revientvers un sommet Y déjà visitéet stocké dans la pileParcours), on met à jourIndex(X )=Min(Index(X ),Index(Y ))
Introduction Algorithme de Tarjan
Les 5 règles de calcul
A
B
C
D
E
F
G
H
I
J1
2
3
45
67
8
9 10
3 Quand on visite à partir de Xun arc transverse (i.e. quirevient vers un sommet Y déjàvisité et tel queIndex(Y )<Index(X )), àcondition que Y soit stockédans la pile Tarjan, on met àjourIndex(X )=Min(Index(X ),Index(Y ))
Introduction Algorithme de Tarjan
Les 5 règles de calcul
A
B
C
D
E
F
G
H
I
J1
2
3
45
67
8
9 10
4 Quand on revient à X aprèsavoir dépilé de la pileParcours son successeur Y ,on met à jourIndex(X )=Min(Index(X ),Index(Y )) pour que X hériteéventuellement de l’indexcalculé pour Y
Introduction Algorithme de Tarjan
Les 5 règles de calcul
A
B
C
D
E
F
G
H
I
J1
2
3
45
67
8
9 10
5 Au moment de supprimer unsommet X de la pileParcours, si on aIndex(X )=Découverte(X ),alors X et tous les sommetsempilés au-dessus de lui dansla pile Tarjan forment unecomposante fortementconnexe de graphe : on lesdépile tous de Tarjan et biensûr on dépile seulement X deParcours
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :
Tarjan :
Sommet A B C D E F G H I JDécouverteIndex
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A
Tarjan :A
Sommet A B C D E F G H I JDécouverte 1Index 1
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A
Tarjan :A
Sommet A B C D E F G H I JDécouverte 1Index 1
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2Index 1 2
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2Index 1 1
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2Index 1 1
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C
Sommet A B C D E F G H I JDécouverte 1 2 3Index 1 1 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C
Sommet A B C D E F G H I JDécouverte 1 2 3Index 1 1 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C D
Tarjan :A B C D
Sommet A B C D E F G H I JDécouverte 1 2 3 4Index 1 1 3 4
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C D
Tarjan :A B C D
Sommet A B C D E F G H I JDécouverte 1 2 3 4Index 1 1 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C D
Sommet A B C D E F G H I JDécouverte 1 2 3 4Index 1 1 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C D
Sommet A B C D E F G H I JDécouverte 1 2 3 4Index 1 1 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C D
Sommet A B C D E F G H I JDécouverte 1 2 3 4Index 1 1 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F
Tarjan :A B C D F
Sommet A B C D E F G H I JDécouverte 1 2 3 4 5Index 1 1 3 3 5
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F
Tarjan :A B C D F
Sommet A B C D E F G H I JDécouverte 1 2 3 4 5Index 1 1 3 3 5
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F E
Tarjan :A B C D F E
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5Index 1 1 3 3 6 5
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F E
Tarjan :A B C D F E
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5Index 1 1 3 3 3 5
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F
Tarjan :A B C D F E
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5Index 1 1 3 3 3 5
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F
Tarjan :A B C D F E
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5Index 1 1 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F
Tarjan :A B C D F E
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5Index 1 1 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F G
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 7
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F G
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F G
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C F
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B C
Tarjan :A B C D F E G
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A B
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7Index 1 1 3 3 3 3 3
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J
Tarjan :A B J
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 8Index 1 1 3 3 3 3 3 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J
Tarjan :A B J
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 8Index 1 1 3 3 3 3 3 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H
Tarjan :A B J H
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 8Index 1 1 3 3 3 3 3 9 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H
Tarjan :A B J H
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 8Index 1 1 3 3 3 3 3 9 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H
Tarjan :A B J H
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 8Index 1 1 3 3 3 3 3 9 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H I
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 9 10 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H I
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 9 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H I
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 9 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J H
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A J
Tarjan :A B J H I
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :A
Tarjan :A B
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :
Tarjan :
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Exemple
Début Animation Fin AnimationA
B
C
D
E
F
G
H
I
J
Parcours :
Tarjan :
Sommet A B C D E F G H I JDécouverte 1 2 3 4 6 5 7 9 10 8Index 1 1 3 3 3 3 3 8 8 8
Introduction Algorithme de Tarjan
Nécessité d’une preuve
On se convainc assez facilement que l’algoritmhe deTarjan permet de calculer les composantes fortementconnexes d’un graphe orientéMais la preuve que c’est bien le cas est loin d’êtreévidente...
Introduction Algorithme de Tarjan
Autre exemple
A B CD
E F G
H
Introduction Algorithme de Tarjan
Autre exemple
A B CD
E F G
H
Introduction Algorithme de Tarjan
Autre exemple
A B CD
E F G
H
1 2 3 4
5678
Introduction Algorithme de Tarjan
FIN
