1 Composantes connexes d'un graphe

Soit G=(V,E) un graphe non-orienté: V est un ensemble de noeuds et E Í V × V est l'ensemble d'arêtes du graphe G (en tant que relation, on supposera E symmétrique). On rappelle qu'un noeud x est voisin immédiat de y dans G si et seulement si x E y. Deux noeuds x et y sont reliés si et seulement si il existe une suite finie (x₀,···,x_n) de noeuds de G, avec x₀=x, x_n=y et (x_i,x_i+1) immédiatement voisins (pour i=0,···,n-1). La relation ``être relié à'' est une relation d'équivalence sur les noeuds de G. On appelle ensemble de composantes connexes de G l'ensemble des classes d'équivalence de noeuds de G pour cette relation d'équivalence. On dira qu'un noeud v de G appartient à la composante n de G si sa classe d'équivalence est la nième parmi les composantes connexes de G.

.2cm

.2cm

Question 1

Soit u le nombre de noeuds d'un graphe G et v son nombre d'arêtes. Quelle est la complexité asymptotique, au pire, de l'algorithme séquentiel décrit précédemment (on ne cherchera pas à prouver ce résultat)?

.2cm

On appelle pseudo-forêt tout graphe orienté (c'est-à-dire que les arêtes ont maintenant une direction: la relation de voisinage n'est plus forcément symétrique) tel que tout noeud ait au plus un voisin immédiat. Dit de façon plus formelle, pour tout noeud n de la pseudo-forêt G=(V,E), le cardinal de {n' | (n,n') Î E} est inférieur ou égal à un: le nombre d'arcs sortant de tout noeud est au plus un. A la figure 1 est donné un exemple de pseudo-forêt, à la figure 2 on trouvera un graphe qui n'est pas une pseudo-forêt.

On appelle arbre tout graphe orienté avec une seule racine (c'est-à-dire un seul point qui n'a pas de voisin immédiat), et un unique chemin entre tout noeud du graphe et cette racine. Remarquez bien que l'on définit les arbres avec une convention d'orientation des arcs exactement à l'envers de ce que l'on a fait par exemple en tronc-commun. On dit qu'un arbre est étoilé si chacun de ses noeuds est directement relié à la racine.

Un pseudo-arbre est un arbre auquel on a rajouté un arc allant de la racine à un autre noeud (par exemple à la figure 1). Un pseudo-arbre étoilé est un arbre étoilé auquel on a rajouté une boucle de la racine vers elle-même (on appelera encore ce noeud, la racine du pseudo-arbre étoilé). On appelle graphe fonctionnel G tout graphe fabriqué à partir d'une fonction f: V ® V, où V est un ensemble fini, de la façon suivante: G=(V,E) (le même V) où E={(v,f(v)) | v Î V}.

.2cm

file=fig1.eps,width=3cm,clip=

Figure 1:

file=fig2.eps,width=3cm,clip=

Figure 2:

Question 2

Est-ce que tous les graphes sont des graphes fonctionnels ¹ ? Montrer que les graphes fonctionnels sont des pseudo-forêts, que les pseudo-forêts sont des unions disjointes d'arbres et de pseudo-arbres et que les pseudo-forêts qui sont des graphes fonctionnels sont des unions de pseudo-arbres. .2cm

On va maintenant pouvoir définir un algorithme parallèle de recherche de composantes connexes sur une machine PRAM, dont on ne spécifie pas pour le moment le type (EREW, CREW ou CRCW). On suppose disposer au début de l'algorithme, d'une représentation d'un graphe G=(V,E) par une matrice d'adjacence A, c'est-à-dire si on suppose V={1,···,n}, A est une matrice n × n telle que A_i,j=1 si (i,j) Î E (et 0 sinon).

On définit maintenant la fonction C: V ® V avec

C(v)=

ì
í
î

v	si v est un noeud isolé
min{u \| A_u,v=1}	sinon

.2cm

Question 3

Indiquer, selon le type de la PRAM utilisée, à quelle complexité on peut arriver pour le procédé qui, étant donné A, calcule le tableau qui à l'entrée v associe C(v).

.2cm

Question 4

Soit G_C le graphe fonctionnel de C. On sait par la question 2 que G_C est une union de pseudo-arbres G_i=(V_i,E_i) (i=1,···,s). Montrer que tous les noeuds de chaque V_i sont dans la même composante connexe du graphe G de départ.

.2cm

On peut prouver de plus (mais on ne demande pas de le faire) que tout cycle de G_C est soit une boucle triviale (de la forme (v,v) pour un noeud v) soit contient exactement deux arcs. On sait aussi par la question 2 que chaque cycle des pseudo-arbres G_i contient la racine de G_i.

.2cm

Question 5

On cherche à transformer les pseudo-arbres G_i de la pseudo-forêt G_C de la question 4 en pseudo-arbres étoilés T_i ou en points isolés.

Programmer un algorithme PRAM (on le simulera par un programme JAVA multi-threadé) en O(é log(n) ù) (où n est le nombre de noeuds du pseudo-arbre considéré) effectuant cette transformation.

.2cm

Remarquez que les T_i forment une pseudo-forêt qui est le graphe fonctionnel d'une fonction D: V ® V.

Soient r_i les racines des pseudo-arbres étoilés T_i (i=1,···,s).

Grâce à la question 4, on sait que les r_i définissent un sur-ensemble des composantes connexes du graphe G de départ. Mais en fait, certains des r_i sont reliés par un chemin dans le graphe G à d'autres r_j. On acceptera sans démonstration le fait que r_i est relié par un chemin à r_j dans G si et seulement si il existe v Î V_i, w Î V_j tels que (v,w) Î E.

.2cm

Question 6

En utilisant la fonction D définissant les pseudo-arbres étoilés T_i, programmer une machine PRAM CRCW (en mode consistant) qui calcule efficacement le graphe des ``super-noeuds'' r_i par une matrice d'adjacence A', dans la mémoire partagée, tel que r_i est relié à r_j si il existe un chemin dans G qui relie r_i à r_j.

.2cm

Question 7

Indiquer sans programmer quelle serait a priori la complexité du calcul de la question 6 si on avait une machine PRAM CREW, et si on avait une machine PRAM EREW.

.2cm

On définit un algorithme qui, partant de k=0, A₀=A de taille n₀ × n₀, fait les étapes suivantes, tant que n_k>0 (n_k étant la taille de A_k):

calculer G_C et les T_i par la méthode de la question 4 et 5,
calculer A_k=(A_k-1)' de taille n_k × n_k par la méthode de la question 6.

Programmer cet algorithme.

.2cm

Question 8

Prouver que n_k £ n_k-1/2. On pourrait prouver, mais on ne le demande pas ici, que l'algorithme sur une machine PRAM CRCW en mode consistant prendrait un temps O(log²(n)) pour un total de O(n²) opérations, où n est le nombre de noeuds dans le graphe G de départ. Quelle est l'efficacité de l'algorithme?

1: On pourra soit donner une preuve si oui, soit donner un contrexemple, si non.

This document was translated from L^AT_EX by H^EV^EA.