Produit zig-zag de graphes

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.

En suivant l'exposé des auteurs^[2], 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é ${\displaystyle D}$ qui possèdent une coloration des arêtes avec seulement ${\displaystyle D}$ couleurs^[5]. Dans une telle coloration, deux arêtes incidentes en un même sommet sont toujours de couleur différente.

Soient ${\displaystyle G}$ un graphe ${\displaystyle D}$-régulier (régulier de degré ${\displaystyle D}$) sur un ensemble de ${\displaystyle N}$ sommets et ${\displaystyle H}$ un graphe ${\displaystyle d}$-régulier sur un ensemble de ${\displaystyle D}$ sommets. On note que l'entier ${\displaystyle D}$ est à la fois le degré de ${\displaystyle G}$, l'index chromatique de ${\displaystyle G}$ et le nombre de sommets de ${\displaystyle H}$ : on colore de façon arbitraire les sommets de ${\displaystyle H}$ avec ces ${\displaystyle 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 ${\displaystyle G\circ H}$ est 1-régulier.

On procède ainsi pour obtenir le produit zig-zag des graphes ${\displaystyle G}$ et ${\displaystyle H}$, noté ${\displaystyle G\circ H}$^[1] :

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

Le graphe résultant :

• possède ${\displaystyle N.D}$ sommets, puisqu'on remplace chacun des ${\displaystyle N}$ sommets de ${\displaystyle G}$ par ${\displaystyle D}$ sommets de ${\displaystyle H}$ ;
• est de degré ${\displaystyle d^{2}}$, puisque, depuis un sommet donné, il y a ${\displaystyle d}$ possibilités pour le zig, une seule possibilité pour le trajet intermédiaire, et à nouveau ${\displaystyle 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 ${\displaystyle G\circ H}$ est cette fois 4-régulier.

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 à ${\displaystyle N}$ sommets, on identifie ses sommets à l'ensemble des entiers de ${\displaystyle 1}$ à ${\displaystyle N}$, et on le note ${\displaystyle [N]}$. Un couple ${\displaystyle (v,i)}$ d'entiers peut être employé pour désigner la ${\displaystyle i}$^e arête sortant du sommet ${\displaystyle v}$.

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

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

est l'application définie comme suit :

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

si la ${\displaystyle i}$^e arête sortant de ${\displaystyle v}$ mène à ${\displaystyle w}$ et la ${\displaystyle j}$^e arête sortant de ${\displaystyle w}$ mène à ${\displaystyle v}$, autrement dit si l'arête ${\displaystyle [v,w]}$ est la ${\displaystyle i}$^e arête sortant de ${\displaystyle v}$ et la ${\displaystyle j}$^e arête sortant de ${\displaystyle 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 ${\displaystyle i=j}$.

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

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

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

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

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

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

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

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

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

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 ${\displaystyle 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 ${\displaystyle G}$.

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

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

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

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