Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/07043.jsonl.gz/711

TD numéro 10 du tronc commun en informatique 1998-99 dirigé
par Serge Vaudenay et
David Pointcheval.
Graphes II
- *
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
qui retourne la matrice d'adjascence d'un graphe.
(On définit
int[][] adjascence(Graphe g)
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
qui retourne la matrice des distances (en nombre minimum de sommets)
entre chaque paire de sommets par l'algorithme de Floyd-Warshall:
int[][] distances(int[][] adj)
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é]
- **
On reprend l'exercice précédent.
Faire une méthode
qui retourne un tableau
int[][][] distances2(int[][] adj)
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
qui affiche en temps linéaire un plus court chemin entre
void plusCourtsChemin(int[][][] tb,int i,int j)
i et
j, s'il en existe, à l'aide du tableau
tb retourné par
distances2.
[corrigé]
- ***
Dans un graphe, un circuit est une suite de sommets
, , ...,
telle que pour ,
est une arête du graphe,
et également.
Un circuit est dit simple si et
sont différents pour tout choix d'incices
distincts et .
(On note en particulier que si est
une arête non orientée du graphe, alors
est un circuit simple du graphe.)
Dans un graphe non orienté connexe, on définit une relation
binaire sur les arêtes:
on note si les arêtes et
sont contenues dans un même circuit simple du graphe.
-
Montrer que est une relation d'équivalence sur
l'ensemble des arêtes du graphe.
On appelle composantes biconnexes ses classes d'équivalences.
-
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 et
adjascentes à ce sommet et qui appartiennent à deux composantes
biconnexes distinctes.
-
Etant donné un parcours en profondeur quelconque du graphe à
partir d'un sommet , on définit
l'arbre du parcours en profondeur:
c'est l'arbre de racine tel que pour tout sommet
, l'ensemble des fils de est l'ensemble des
sommets adjascents à et qui sont visités par
un appel récursif à partir de .
- Montrer que si et sont adjascents, alors
l'un des deux sommets est descendant de l'autre dans l'arbre du parcours en
profondeur.
- Montrer que si est fils de et que si
est fils de , alors
si, et seulement si il existe un descendant de
et un ascendant de dans l'arbre de parcours qui
sont adjascents.
-
Etant donné un parcours en profondeur du graphe, on note
le numéro du sommet dans l'ordre du
parcours en profondeur.
On définit comme étant le plut petit
pour l'ensemble des ascendants de
adjascents à un descendant de par une
arête hors de l'arbre du parcours en profondeur et .
-
Soit un fils de .
Montrer que est un point d'articulation si, et seulement si
il existe un fils de tel que
.
- Dans ce cas, montrer que la composante biconnexe de
n'est composée que d'arêtes adjascentes à deux sommets
situés dans le sous-arbre de racine .
- Modifier l'algorithme du parcours en profondeur du graphe pour qu'il
calcule simultannément les fonctions et
et qu'il affiche les composantes biconnexes.
[corrigé]