DM 1 - Points d'articulation et composantes biconnexes

Dans ce devoir à la maison, nous continuons à travailler sur le plan du métro parisien que l'on considère comme un graphe non orienté, comme au TD 3. Le but est de calculer les points d'articulation et les composantes biconnexes d'un graphe correspondant à un réseau de transport dans un état plus ou moins perturbé.

Le travail demandé pour la partie 1 est assez voisin de l'exercice 3 du TD 3, auquel on se reportera pour les détails (l'exercice 2 du TD 3 n'est pas nécessaire pour ce DM). Cette partie 1, bien traitée, suffira pour obtenir la note A.
La partie 2 demande un peu plus de réflexion mais reste relativement simple à programmer.
La partie 3 est nettement plus difficile.

Pour faciliter la correction, il est demandé que l'exécution se fasse comme il est précisé dans l'énoncé de chaque question et que les sorties respectent le format indiqué. Les sorties graphiques sont facultatives.

Ce devoir doit être rendu au plus tard le mercredi 23 mars 2005. La remise des travaux se fera par la commande :

/users/profs/info/Depot/INF_431/deposer [pgm] DM_1 [gpe]

où [pgm] doit être remplacé par la liste des noms des fichiers contenant vos programmes et [gpe] doit être remplacé par votre numéro de groupe. Par exemple, pour déposer des fichiers Liste.java et Graphe.java qui sont dans le répertoire courant, un élève du groupe 18 doit taper :

/users/profs/info/Depot/INF_431/deposer Liste.java Graphe.java DM_1 18

1. Points d'articulation

Travail demandé

Le programme se lancera par la commande :

java Articulations lignes

où lignes sera remplacé par le nom d'un fichier descriptif des lignes, par exemple, lignes3.data.

La sortie du programme devra être une suite de lignes de la forme :

pour la composante connexe de uneStationRacine (taille : t1)
  les points d'articulation sont :
    nomDeStation n11
    ...
    nomDeStation n1k
pour la composante connexe de autreStationRacine (taille : t2)
  il n'y a pas de point d'articulation
...

Indications

On balaye les stations dans l'ordre des numéros croissants et, pour chaque station non encore visitée, on lance un calcul des points d'articulations de la composante connexe, en prenant cette station pour racine. On n'affichera un résultat que pour les composantes de taille t_i supérieure ou égale à 3, on sait que celles de taille inférieure ne peuvent pas avoir de point d'articulation. En suivant les indications données pour l'exercice 3 du TD 3, les informations collectées pendant la dfs suffisent pour afficher ensuite le résultat attendu. Les noms des stations qui sont des points d'articulation seront listés dans l'ordre de leur visite par la dfs, suivi chacun par le nombre n_ij de composantes biconnexes qui s'y articulent (c'est le nombre de composantes qui s'y attachent plus une, sauf dans le cas de la racine).

Facultatif

Exemples

Avec le fichier lignes3.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.
Avec le fichier lignes4.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.
Avec le fichier lignes5.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.
Avec le fichier lignes6.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.

2. Composantes biconnexes

Définition, propriétés

Une composante biconnexe est un ensemble maximal d'arêtes (non orientées) qui vérifient la propriété suivante :
Soient a et b deux arêtes distinctes, alors il existe un cycle simple (qui ne passe pas deux fois par le même sommet) qui passe par a et b.
En corollaire, lorsque aucun cycle ne passe par une arête, celle-ci forme une composante biconnexe à elle seule.

Les points d'articulation sont les sommets du graphe qui sont partagés par plusieurs composantes biconnexes.

Lorsque l'on détecte que le sommet i est un point d'articulation, c'est-à-dire lorsque l'on a terminé l'exploration d'un sommet k voisin de i et tel que numAttache[k] == num[i], alors on sait que la composante biconnexe qui contient l'arête (i,k) est incluse dans l'ensemble des arêtes considérées depuis le début de l'exploration de k.
Il faut noter que cet ensemble peut contenir plusieurs composantes biconnexes, si l'exploration récursive de k a rencontré d'autres points d'articulations.

Méthode

Pour construire les composantes biconnexes, on va utiliser une pile d'arcs (pour chaque arête, on ne considère que l'arc qui est déterminé par le sens du parcours par la dfs).
Chaque fois que l'on commence l'exploration d'un sommet k à partir d'un sommet i, on empile l'arc (i,k).
On doit aussi empiler les arcs qui ferment les cycles non triviaux. On n'empile donc pas les arcs de retour du sommet courant vers son père, car il s'agit de l'arc réciproque d'un arc déjà dans la pile.
Si, au retour de l'exploration de k, on a numAttache[k] == num[i], alors on obtient le détail d'une composante biconnexe en dépilant jusqu'à l'arc (i,k) inclus.
On notera que si l'exploration de k a rencontré des composantes imbriquées, celles-ci auront été déjà dépilées, avant de quitter leur point d'attache respectif.
On pourra aussi éventuellement trouver d'autres composantes attachées en i, elles commenceront par des arcs (i,k') différents.

Travail demandé

Le programme se lancera par la commande :

java Biconnexes lignes

où lignes sera remplacé par le nom d'un fichier descriptif des lignes, par exemple, lignes3.data.

La sortie du programme devra être une suite de lignes de la forme :

point d'attache uneStationAttache [a1]
  nomDeStation -> nomDeStation
  ...
  taille de cette composante biconnexe : n1 arc(s)
point d'attache autreStationAttache [a2]
  ...
...

Indications

On balaye les stations dans l'ordre des numéros croissants et, pour chaque station non encore visitée, on lance un calcul des points d'articulations de la composante connexe, en prenant cette station pour racine. Quand, au retour de l'exploration de k, on a numAttache[k] == num[i], on indique que la station i est un point d'attache et le nom de la station est suivi de la valeur de articulation[i], entre crochets, par exemple [a₁]. Ensuite, on liste les arcs de la composante biconnexe que l'on vient d'identifier, dans l'ordre donné par la pile et, pour finir, on indique le nombre d'arcs dépilés. Lorsque plusieurs composantes biconnexes sont attachées au même point, elles seront listées dans l'ordre [1], [2], etc., mais pas nécessairement de manière consécutive car il peut y avoir des composantes imbriquées.

Exemples

Avec le fichier lignes3.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.
Avec le fichier lignes4.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.
Avec le fichier lignes5.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.
Avec le fichier lignes6.data, on doit obtenir ce résultat, qui peut s'illustrer ainsi.

Un coloriage qui affecte des couleurs différentes à des composantes adjacentes n'est pas facile à obtenir, surtout si l'on veut utiliser un nombre minimal de couleurs (qui est le nombre maximal de composantes adjacentes). C'est le but de l'extension qui suit.

3. Extensions

Coloriage des composantes biconnexes

Un bon coloriage, comme ceux donné ci-dessus, doit attribuer des couleurs différentes aux composantes adjacentes. Pour y arriver "au vol", pendant la dfs, il faut respecter deux règles :

• Deux composantes qui ont le même point d'attache doivent avoir des couleurs différentes. C'est relativement facile puisque cela se décide dans une même instance d'appel de la dfs.
• Une composante doit avoir une couleur différente de celles de toutes les composantes attachées en dessous d'elle (mais deux de ces composantes peuvent avoir la même couleur, si elles ne sont pas attachées au même point). Pour cela, avant de dépiler les arcs pour les dessiner, il faut balayer la pile pour y retrouver les points d'attaches de ces composantes et les couleurs qu'elles utilisent. On peut alors en déduire une couleur disponible pour la nouvelle composante.

En fait, cette manière d'affecter les couleurs, en remontant, ne permet pas d'assurer le nombre minimal de couleurs. On le voit par exemple avec le fichier lignes5.data pour lequel on obtiendrait un coloriage de ce genre, alors que deux couleurs suffisent.

Une autre manière de faire est de construire l'arbre des composantes biconnexes, comme expliqué ci-dessous. Il est alors relativement simple de colorier de manière minimale, par une descente dans cet arbre.

Arbre des composantes biconnexes

Plus exactement, il s'agit d'une forêt dont chaque arbre correspond à une composante connexe du graphe initial. Pour un certain choix d'un sommet r, racine de la composante connexe, l'arbre est défini par l'imbrication de la découverte des composantes biconnexes durant la dfs. Chaque noeud de l'arbre correspond à une composante biconnexe, il est étiqueté par une liste des arcs qui la composent. Pour deux noeuds A et B de l'arbre, on construit un arc de A vers B si le point d'attache de la composante B est un sommet de la composante A, autrement dit, si le dernier arc du chemin qui va de la racine r vers le point d'attache de la composante B, est un arc de la composante A.
Comme pour le coloriage "au vol" vu ci-dessus, c'est au moment de construire le noeud A, qu'on doit faire l'inventaire des composantes B qui s'y rattachent. On peut regarder les arcs qui composent A, comme pour la question précédente, en faisant attention car deux arcs peuvent conduire au même point d'attache. On peut faire mieux en gérant correctement un pile de composantes biconnexes. Il y aura un cas particulier un peu délicat, lorsque la racine de la dfs est un point d'articulation.