Scribd
Importer
21 vues4 pages

Algorithmes Élémentaires

Le document présente des algorithmes élémentaires liés à la théorie des graphes, notamment la détection des circuits, des racines, des composantes connexes et des composantes fortement connexes. Chaque algorithme est illustré par des exemples graphiques. Les méthodes de recherche de parcours sont mentionnées comme outils pour certaines détections.

Transféré par

Olfa Trabelsi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
21 vues4 pages

Algorithmes Élémentaires

Le document présente des algorithmes élémentaires liés à la théorie des graphes, notamment la détection des circuits, des racines, des composantes connexes et des composantes fortement connexes. Chaque algorithme est illustré par des exemples graphiques. Les méthodes de recherche de parcours sont mentionnées comme outils pour certaines détections.

Transféré par

Olfa Trabelsi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Les Graphes

Théorie et Algorithmes

* Crédits : Cédric Joncour, Université du Havre - UFR des Sciences et Techniques

Algorithmes élémentaires
Algorithmes de graphes Algorithmes élémentaires

Détection des circuits

a
g
c

d
e

b
f
Exemple 1

a
g
c

d
e

b
f

Exemple 2

Algorithmes de graphes Algorithmes élémentaires

Détection des racines / antiracines

Algorithmes élémentaires a
g
c

d
e

b
f

Exemple

N.B. Pour détecter des antiracines, on


remplace par
Algorithmes de graphes Algorithmes élémentaires

Détection des composantes connexes

Algorithmes élémentaires

a
g
c

d
e

b
f

Exemple

Algorithmes de graphes Algorithmes élémentaires

Détection des composantes connexes

Algorithmes élémentaires

Faisant appel à l’algorithme de


recherche de parcours
Algorithmes de graphes Algorithmes élémentaires

Détection des composantes fortement connexes


a
Algorithmes élémentaires g
c

d
e

b
f

Exemple 1

a
g
c

d
e

b
f

Exemple 2

Algorithmes de graphes Algorithmes élémentaires

Détection des composantes fortement connexes

a
g
c

d
e

b
f

Faisant appel à l’algorithme de


recherche de parcours

Vous aimerez peut-être aussi