Produit zig-zag de graphes

En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers. Le produit de deux graphes $G$ et $H$, noté $G\circ H$, prend en arguments un grand graphe $G$ et un petit graphe $H$ et produit un graphe qui hérite approximativement de la taille du grand graphe et du degré du petit. Une propriété importante du produit zig-zag est que si $H$ est un bon graphe expanseur, alors le taux d'expansion du graphe résultat $G\circ H$ est seulement un peu moins bon que le taux d'expansion de $G$.

De manière informelle, le produit zig-zag $G\circ H$ remplace chaque sommet de $G$ par une copie de $H$ (un « nuage », cloud en anglais) et relie les sommets en trois étapes : une première (le zig) à l'intérieur du nuage, suivi d'une deuxième entre deux nuages, et enfin une troisième (le zag) à l'intérieur du nuage d'arrivée.

Le produit zig-zag a été introduit par Omer Reingold, Salil Vadhan et Avi Wigderson en 2002 et a été utilisé pour la construction explicite d'expanseurs et d'extracteurs de degré constant. Les auteurs ont obtenu le prix Gödel pour ce travail. Ultérieurement le produit zig-zag a été employé en théorie de complexité pour prouver que les classes de complexité SL (espace logarithmique symétrique) et L (espace logarithmique) coïncident.

Définitions

Les graphes considérés ici sont non orientés et réguliers. De plus, le degré du premier correspond au nombre de sommets du second.

Définition simplifiée

En suivant l'exposé des auteurs, on présente d'abord une version simplifiée de la définition du produit zig-zag. Dans cette définition, on se restreint aux graphes réguliers de degré $D$ qui possèdent une coloration des arêtes avec seulement $D$ couleurs. Dans une telle coloration, deux arêtes incidentes en un même sommet sont toujours de couleur différente.

Soient $G$ un graphe $D$-régulier (régulier de degré $D$) sur un ensemble de $N$ sommets et $H$ un graphe $d$-régulier sur un ensemble de $D$ sommets. On note que l'entier $D$ est à la fois le degré de $G$, le nombre de couleurs de $G$ et le nombre de sommets de $H$ : on colore de façon arbitraire les sommets de $H$ avec ces $D$ couleurs.

• 
  Le graphe 4-régulier G à gauche et le graphe 1-régulier H à droite.
• 
  Après remplacement des sommets de G par des nuages issus de H.
• 
  La procédure de remplacement des arêtes en zig-zag.
• 
  Le résultat final $G\circ H$ est 1-régulier.

On procède ainsi pour obtenir le produit zig-zag des graphes $G$ et $H$, noté $G\circ H$ :

• Chaque sommet de $G$ est remplacé par une copie du graphe $H$, son « nuage ».
• Deux sommets $v$ et $w$ dans le graphe résultant sont liés lorsqu'il existe deux sommets $a$ et $b$ tels que :
  • $v$ et $a$ sont liés dans $H$ (le zig) ;
  • $a$ et $b$ sont de même couleur et font partie de nuages issus de sommets qui sont liés dans $G$ ;
  • $b$ et $w$ sont liés dans $H$ (le zag).

Le graphe résultant :

• possède $N.D$ sommets, puisqu'on remplace chacun des $N$ sommets de $G$ par $D$ sommets de $H$ ;
• est de degré $d^{2}$, puisque, depuis un sommet donné, il y a $d$ possibilités pour le zig, une seule possibilité pour le trajet intermédiaire, et à nouveau $d$ possibilités pour le zag.

• 
  Cette fois, H est un graphe 2-régulier.
• 
  Après remplacement des sommets.
• 
  Le zig-zag.
• 
  Le résultat final $G\circ H$ est cette fois 4-régulier.

Application de rotation

Dans le cas général, on ne suppose pas qu'une coloration avec D couleurs existe.

On considère ici que les arêtes issues d'un sommet sont numérotées ; de plus, pour un graphe à $N$ sommets, on identifie ses sommets à l'ensemble des entiers de $1$ à $N$, et on le note $[N]$. Un couple $(v,i)$ d'entiers peut être employé pour désigner la $i$^e arête sortant du sommet $v$.

Soit $G$ un graphe $D$-régulier (régulier de degré $D$). L’application de rotation

$\mathrm {Rot} _{G}:[N]\times [D]\to [N]\times [D]$

est l'application définie comme suit :

$\mathrm {Rot} _{G}(v,i)=(w,j)$

si la $i$^e arête sortant de $v$ mène à $w$ et la $j$^e arête sortant de $w$ mène à $v$, autrement dit si l'arête $[v,w]$ est la $i$^e arête sortant de $v$ et la $j$^e arête sortant de $w$.

L'application de rotation remplace et généralise la coloration de la définition précédente. Si une coloration avec D couleurs existe, alors on peut s'arranger pour numéroter chaque sommet de telle façon que $i=j$.

Il résulte de la définition que $\mathrm {Rot} _{G}$ est une bijection, et de plus que $\mathrm {Rot} _{G}\circ \mathrm {Rot} _{G}$ est l'application identité. En d'autres termes, $\mathrm {Rot} _{G}$ est une involution.

Définition du produit zig-zag

Principe du produit zig-zag dans le cas général.

Soit $G$ un graphe $D$-régulier sur l'ensemble de sommets $[N]$ et d'application de rotation $\mathrm {Rot} _{G}$, et soit $H$ un graphe $d$-régulier sur l'ensemble de sommets $[D]$ et d'application de rotation $\mathrm {Rot} _{H}$.

Le produit zig-zag $G\circ H$ est le graphe $d^{2}$-régulier dont l'ensemble des sommets est $[N]\times [D]$ et dont l'application de rotation $\mathrm {Rot} _{G\circ H}$ est définie par

$\mathrm {Rot} _{G\circ H}((v,a),(i,j))=((w,b),(j',i'))$

où $((w,b),(j',i'))$ sont construits successivement en posant

1. $(a',i')=\mathrm {Rot} _{H}(a,i)$, le zig
2. $(w,b')=\mathrm {Rot} _{G}(v,a')$,
3. $(b,j')=\mathrm {Rot} _{H}(b',j)$, le zag.

Les sommets du graphe $G\circ H$ sont des couples $(v,a)$ de $[N]\times [D]$. Les arêtes de ce graphe portent des couples d'étiquettes $(i,j)$ du graphe $d$-régulier, correspondant aux deux décisions à prendre en partant d'un sommet donné.

Ici encore, le graphe produit comporte $N.D$ sommets et est $d^{2}$-régulier.

Propriétés

Réduction du degré

Par définition, le produit zig-zag transforme un graphe $D$-régulier $G$ en un nouveau graphe qui est $d^{2}$-régulier. Ainsi, si le degré de $G$ est nettement plus grand que celui de $H$, le produit zig-zag réduit le degré de $G$.

Préservation du trou spectral

Le taux d'expansion d'un graphe peut être mesuré par son trou spectral, qui est la différence entre la plus grande et la deuxième plus grande valeur propre de sa matrice d'adjacence. Une propriété importante du produit zig-zag est qu'il préserve le trou spectral, en ce sens que si $H$ est un graphe expanseur « assez bon » (avec un grand trou spectral), alors le taux d'expansion du produit zig-zag est proche de celui du graphe original $G$.

Formellement, appelons graphe de type $(N,D,\lambda )$ un graphe $D$-régulier sur $N$ sommets dont la deuxième valeur propre est majorée en valeur absolue par $\lambda$. Soient $G_{1}$ et $G_{2}$ des graphes de type $(N_{1},D_{1},\lambda _{1})$ et $(D_{1},D_{2},\lambda _{2})$ respectivement. Alors $G_{1}\circ G_{2}$ est de type

$(N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))$,

avec $f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2}$.

Préservation de la connexité

Le produit zig-zag $G\circ H$ opère séparément sur chaque composante connexe de $G$. Plus formellement, soient $G$ un graphe $D$-régulier sur l'ensemble de sommets $[N]$ et $H$ un graphe $d$-régulier sur l'ensemble $[D]$ de sommets. Si $S\subseteq [N]$ est une composante connexe de $G$, alors on a $G|_{S}\circ H=G\circ H|_{S\times D}$, où $G|_{S}$ est le sous-graphe de $G$ induit par $S$ (c'est-à-dire le graphe sur $S$ qui contient les arêtes de $G$ dont les deux extrémités sont dans $S$).

Applications

Construction d'un expanseur de degré constant

Dans leur article de 2002, Reingold, Vadhan, et Wigderson donnent une construction combinatoire explicite et simple de graphes expanseurs de degré constant. La construction est itérative. La bloc de base est un expanseur unique de taille fixe. À chaque itération, le produit zig-zag sert à construire un autre graphe dont la taille augmente, mais dont le degré et le taux d'expansion restent inchangés. Ce processus peut être répété et donne des expanseurs de taille arbitrairement grande.

Solution du problème de connexité en espace logarithmique

En 2008, Reingold présente un algorithme qui résout le problème dit de la st-connexité en espace logarithmique. Il s'agit du problème de déterminer si, dans un graphe non orienté, deux sommets s et t donnés sont dans la même composante connexe. L'algorithme repose de manière essentielle sur le produit zig-zag.

De manière informelle, pour résoudre le problème de la st-connexité en espace logarithmique, le graphe d'entrée est transformé, en utilisant une combinaison d'exponentiations et de produits zig-zag, en un graphe régulier de degré constant avec un diamètre logarithmique. L'élévation à la puissance accroît le taux d'expansion (et donc réduit le diamètre) au prix de l'accroissement du degré, et le produit zig-zag est utilisé pour réduire le degré tout en préservant le taux d'expansion.

Voir aussi

Bibliographie

• Omer Reingold, Luca Trevisan et Salil Vadhan, « Pseudorandom walks on regular digraphs and the RL vs. L problem », dans Proc. 38th ACM Symposium on Theory of Computing Proc. (STOC), 2006 (DOI 10.1145/1132516.1132583), p. 457–466.

Articles connexes

• Lexique de la théorie des graphes

Notes et références

• (en) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « zig-zag product » (voir la liste des auteurs) et « rotation map » (voir la liste des auteurs).