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  et , noté , prend en arguments un grand graphe  et un petit graphe  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  est un bon graphe expanseur, alors le taux d'expansion du graphe résultat  est seulement un peu moins bon que le taux d'expansion de .

De manière informelle, le produit zig-zag  remplace chaque sommet de   par une copie de  (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é  qui possèdent une coloration des arêtes avec seulement  couleurs. Dans une telle coloration, deux arêtes incidentes en un même sommet sont toujours de couleur différente.

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

On procède ainsi pour obtenir le produit zig-zag des graphes   et , noté  :
 Chaque sommet de  est remplacé par une copie du graphe , son « nuage ».
 Deux sommets  et  dans le graphe résultant sont liés lorsqu'il existe deux sommets  et  tels que :
  et  sont liés dans  (le zig) ;
  et  sont de même couleur et font partie de nuages issus de sommets qui sont liés dans  ;
  et  sont liés dans  (le zag).

Le graphe résultant :
 possède  sommets, puisqu'on remplace chacun des  sommets de  par  sommets de  ;
 est de degré , puisque, depuis un sommet donné, il y a  possibilités pour le zig, une seule possibilité pour le trajet intermédiaire, et à nouveau  possibilités pour le zag.

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 à  sommets, on identifie ses sommets à l'ensemble des entiers de  à , et on le note . Un couple  d'entiers peut être employé pour désigner la  arête sortant du sommet . 

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

est l'application définie comme suit : 
  
si la  arête sortant de  mène à  et la  arête sortant de  mène à , autrement dit si l'arête  est la  arête sortant de  et la  arête sortant de .

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 .

Il résulte de la définition que  est une bijection, et de plus que  est l'application identité. En d'autres termes,  est une involution.

Définition du produit zig-zag 

Soit  un graphe -régulier sur l'ensemble de sommets  et d'application de rotation , et soit  un graphe -régulier sur l'ensemble de sommets  et d'application de rotation .

Le produit zig-zag  est le graphe -régulier dont l'ensemble des sommets est  et dont l'application de rotation  est définie par

où  sont construits successivement en posant 
 , le  zig
 ,
 , le zag.

Les sommets du graphe  sont des couples  de . Les arêtes de ce graphe portent des couples d'étiquettes  du graphe -régulier, correspondant aux deux décisions à prendre en partant d'un sommet donné.

Ici encore, le graphe produit comporte  sommets et est -régulier.

Propriétés

Réduction du degré

Par définition, le produit zig-zag transforme un graphe -régulier  en un nouveau graphe qui est -régulier. Ainsi, si le degré de  est nettement plus grand que celui de , le produit zig-zag réduit le degré de .

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  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 .

Formellement, appelons graphe de type  un graphe -régulier sur  sommets dont la deuxième valeur propre est majorée en valeur absolue par . Soient  et  des graphes de type  et  respectivement. Alors  est de type 
, 
avec .

Préservation de la connexité
Le produit zig-zag  opère séparément sur chaque composante connexe de . Plus formellement, soient  un graphe -régulier  sur l'ensemble de sommets  et  un graphe -régulier sur l'ensemble  de sommets. Si  est une composante connexe de , alors on a , où  est le sous-graphe de   induit par  (c'est-à-dire le graphe sur  qui contient les arêtes de  dont les deux extrémités sont dans ).

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 
 .

Articles connexes 
Lexique de la théorie des graphes

Notes et références 

Algorithme de la théorie des graphes
Théorie des graphes
Théorie de la complexité des algorithmes
Opération sur les graphes