Graphes et optimisation

Accueil > Cours > Applications des parcours de graphes

Applications des parcours de graphes

mercredi 17 août 2005, par

Accessibilité

Pour connaître les sommets accessibles depuis un sommet donné d’un graphe (orienté ou non), il suffit de faire un parcours en profondeur à partir de ce sommet, en marquant les sommets visités :

marquage des accessibles depuis un sommet s:
visiter s
visiter un sommet t:
SI t n'a pas encore été visité ALORS
        marquer t;
        visiter tous les successeurs de t
FIN SI

Composantes connexes d’un graphe non orienté

La composante connexe d’un sommet est l’ensemble des sommets accessibles depuis . On peut colorier les composantes connexes en adaptant l’un des algorithmes de parcours : par exemple (parcours en profondeur)

colorier les composantes connexes :
POUR tout sommet s
        SI s n'a pas encore été visité ALORS
                choisir une nouvelle couleur;
                visiter s
        FIN SI
FIN POUR
visiter un sommet s:
SI s n'a pas encore été visité ALORS
        colorier s;
        visiter tous les successeurs de s
FIN SI

Graphe orienté sans circuit

Un graphe orienté comporte un circuit si et seulement si, lors du parcours des sommets accessibles depuis un sommet, on retombe sur ce sommet. Pour savoir si un graphe est sans circuit, il suffit donc d’adapter l’un des algorithmes de parcours, en maintenant une liste des sommets critiques (en cours de visite) :

graphe sans circuit :
POUR tout sommet s
        SI s n'a pas encore été visité ALORS
                visiter s
        FIN SI
FIN POUR ;
répondre ``oui''
visiter un sommet s:
SI s est dans la liste critique ALORS
        répondre ``non'';
        sortir
SINON
        ajouter s à la liste critique;
        visiter tous les successeurs de s;
        enlever s de la liste critique
FIN SI

Tri topologique d’un graphe orienté sans circuit

Le tri topologique d’un graphe orienté sans circuit est une numérotation des sommets dans laquelle les descendants d’un sommet de numéro sont nécessairement de numéro supérieur à .
L’ordre inverse de l’ordre de post-visite, dans le parcours en profondeur du graphe, permet son tri topologique : en effet, lorsqu’on a terminé la visite d’un sommet , on a terminé la visite de tous ses descendants. Par conséquent, si vient avant dans l’ordre de post-visite, n’est pas un descendant de .

numéroter les n sommets du graphe :
        k := n;
        visiter tous les sommets
visiter un sommet s:
SI s n'a pas encore été visité ALORS
        visiter tous les successeurs de s;
        affecter à s le numéro k;
        k := k-1;
FIN SI