Graphes II

1. * On utilise les structures du fichier GrapheEditeur.java (cliquer ici pour télécharger) rencontrées dans l'exercice 3 du tp 9. Dans la classe GrapheApplication, faire une méthode
   int[][] adjascence(Graphe g)
   qui retourne la matrice d'adjascence d'un graphe. (On définit adj[i][j]=1 s'il existe une arête du sommet numéro i vers le sommet numéro j, adj[i][j]=0 si i=j et adj[i][j]=-1 dans les autres cas.) Faire une méthode
   int[][] distances(int[][] adj)
   qui retourne la matrice des distances (en nombre minimum de sommets) entre chaque paire de sommets par l'algorithme de Floyd-Warshall: dist[i][j] doit être égal à la longueur minimale d'un chemin du sommet numéro i vers le sommet numéro j, et -1 s'il n'existe pas de tel chemin.
   [corrigé]

2. ** On reprend l'exercice précédent. Faire une méthode
   int[][][] distances2(int[][] adj)
   qui retourne un tableau tb de longueur 2 tel que tb[0] est la matrice des distances (comme pour la méthode distances) et tb[1] est une matrice telle que tb[1][i][j] est le numéro d'un quelconque sommet d'un des plus courts chemins entre i et j, s'il en existe (ce sommet devra être différent de i et de j lorsque la distance entre les deux sommets sera supérieure ou égale à 2). Faire une méthode
   void plusCourtsChemin(int[][][] tb,int i,int j)
   qui affiche en temps linéaire un plus court chemin entre i et j, s'il en existe, à l'aide du tableau tb retourné par distances2.
   [corrigé]

3. *** Dans un graphe, un circuit est une suite de sommets $(s$₁, $s$₂, ..., $s$_n) telle que pour $i=1,\; 2,\; ...,\; n-1$, $(s$_i,s_i+1) est une arête du graphe, et $(s$_n,s₁) également. Un circuit est dit simple si $s$_i et $s$_j sont différents pour tout choix d'incices distincts $i$ et $j$. (On note en particulier que si $(s$₁,s₂) est une arête non orientée du graphe, alors $(s$₁,s₂) est un circuit simple du graphe.) Dans un graphe non orienté connexe, on définit une relation binaire sur les arêtes: on note $e~e\text{'}$ si les arêtes $e$ et $e\text{'}$ sont contenues dans un même circuit simple du graphe.
   1. Montrer que $~$ est une relation d'équivalence sur l'ensemble des arêtes du graphe. On appelle composantes biconnexes ses classes d'équivalences.
   2. Un sommet du graphe est un point d'articulation si sa suppression dans le graphe sépare l'ensemble des sommets en plusieurs composantes connexes. Montrer qu'un sommet est un point d'articulation si, et seulement si il existe deux arêtes $e$ et $e\text{'}$ adjascentes à ce sommet et qui appartiennent à deux composantes biconnexes distinctes.
   3. Etant donné un parcours en profondeur quelconque du graphe à partir d'un sommet $s$, on définit l'arbre du parcours en profondeur: c'est l'arbre de racine $s$ tel que pour tout sommet $u$, l'ensemble des fils de $u$ est l'ensemble des sommets adjascents à $u$ et qui sont visités par un appel récursif à partir de $u$.
      1. Montrer que si $u$ et $v$ sont adjascents, alors l'un des deux sommets est descendant de l'autre dans l'arbre du parcours en profondeur.
      2. Montrer que si $w$ est fils de $v$ et que si $v$ est fils de $u$, alors $(u,v)~(v,w)$ si, et seulement si il existe un descendant de $w$ et un ascendant de $u$ dans l'arbre de parcours qui sont adjascents.
   4. Etant donné un parcours en profondeur du graphe, on note $n(u)$ le numéro du sommet $u$ dans l'ordre du parcours en profondeur. On définit $f(v)$ comme étant le plut petit $n(u)$ pour l'ensemble des ascendants $u$ de $v$ adjascents à un descendant de $v$ par une arête hors de l'arbre du parcours en profondeur et $u=v$.
      1. Soit $v$ un fils de $u$. Montrer que $v$ est un point d'articulation si, et seulement si il existe un fils $w$ de $v$ tel que $f(w)>=n(v)$.
      2. Dans ce cas, montrer que la composante biconnexe de $(v,w)$ n'est composée que d'arêtes adjascentes à deux sommets situés dans le sous-arbre de racine $v$.
   5. Modifier l'algorithme du parcours en profondeur du graphe pour qu'il calcule simultannément les fonctions $n$ et $f$ et qu'il affiche les composantes biconnexes.
   
   [corrigé]