Malika More (malika.more@u-clermont1.fr)

Introduction Algorithme de Tarjan

Forte connexité

Malika More(malika.more@u-clermont1.fr)

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