TD 3 : parcours en largeur et en profondeur

Quelques exercices

Une k-coloration d'un graphe $G$ est une fonction $V(G) \rightarrow [1,k]$ telle que toute paire de sommets adjacents (et distincts) sont coloriés différemment (c'est-à-dire associés par $f$ à deux entiers distincts). Un graphe est biparti s'il admet une 2-coloration. Écrire un algorithme qui décide si un graphe non orienté connexe est biparti.

Principe de résolution : colorier avec une couleur le sommet de départ $s$ ; lorsqu'on marque un sommet, on lui donne la couleur opposée à celle de son père. Si on tombe sur un sommet déjà marqué, on teste si sa couleur est différente de celle du sommet courant : si ce n'est pas le cas, le graphe n'est pas biparti. L'implémentation repose sur un parcours en largeur, en $O(n+m)$.

Problème du Labyrinthe

Modélisation

Labyrinthe initial

L'idée est de trouver une modélisation simple pour pouvoir se déplacer sur le graphe : la modélisation se base sur les chemins possibles.

Modélisation des différents chemins	Modélisation des sommets	Modèle final

Résolution du problème

On peut trouver la sortie d'un labyrinthe avec 2 couleurs en "simulant" un parcours en profondeur (DFS) : au lieu d'utiliser une mémoire globale de taille n (la pile), on va utiliser un marquage local, à chaque nœud/arête, avec uniquement 2 marqueurs/craies/cailloux de couleur.

• Au lieu d'empiler un sommet, on va le marquer de la couleur 1
• Au lieu de dépiler un sommet, on doit :
  1. vérifier que tous les sommets voisins ont été visités ;
  2. revenir au sommet "père".

La première opération est facile. La deuxième l'est moins avec une mémoire locale.

1. En effet, il faut détecter facilement qu'un voisin a déjà été visité : il suffit d'y aller et si c'est le cas faire demi-tour … mais on veut éviter de parcourir plusieurs fois la même arête. Nommons par commodité la salle "courante" U. Je visite un voisin V de U et il se trouve que V a déjà été visité. Je reviens donc en U. Je n'ai pas la mémoire des autres voisins de U. Les ai-je visités ? Il se pourrait que cela soit le cas. Pour éviter cet écueil, il suffit de marquer les arêtes. Une arête marquée indique que j'ai déjà suivi le couloir correspondant. Cette opération est donc facile.

2. Il faut pouvoir remonter au père donc distinguer 2 types de marquage : les arêtes retour et les arêtes père. En résumé, la méthode est la suivante :

• Chaque nouvelle arête parcourue ou tout nouveau sommet traversé est marqué par la couleur 1 (correspond à l'empilement d'un sommet dans le DFS)
• Si on arrive à un sommet marqué, on fait demi-tour en marquant l'arête avec la couleur 2. Une arête "retour" est donc marquée par les couleurs 1 et 2 (aller et retour)
• Si toutes les arêtes incidentes sont doublement marquées sauf une, on sait qu'on a visité tous les voisins. Ainsi, l'arête restante simplement marquée est l'arête "père". Cela correspond à l'opération de dépilement de sommet du DFS. Il faut remonter au père en marquant l'arête père avec la couleur 2.

La résolution se fait via l'algorithme de Trémaux dont le fonctionnement est disponible sur la vidéo suivante.