Produit cartésien (graphe)

Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes $G$ et $G'$ résultant en un graphe $G\square G'$. Parler de produit ou de somme pour cette opération n'est pas une contradiction, mais une explication basée sur deux aspects différents : la construction peut se voir comme un produit, tandis que de nombreuses propriétés sont basées sur la somme.

Construction

Produit cartésien de deux graphes.

Soient deux graphes $G=(V,E)$ et $G'=(V',E')$. Le produit cartésien $H=G\square G'$ est défini comme suit :

• $V(H)=\{(ss')|s\in V,s'\in V'\}$. Autrement dit, l'ensemble résultant des sommets $V(H)$ est le produit cartésien $V(G)\times V(G')$.
• $E(H)=\{e_{uu'-vv'}|(u=v\wedge d(u',v')=1)\vee (u'=v'\wedge d(u,v)=1)\}$. Autrement dit, deux sommets sont voisins si les sommets dont ils sont issus étaient voisins dans l'un des deux graphes.

Propriétés

• Diamètre. Le diamètre $D_{H}$ du produit cartésien de $G$ et $G'$ est $D_{H}=D_{G}+D_{G'}$.
• L'opération $\square$ est commutative et associative.
• Spectre. Le spectre d'un produit cartésien $A\square B$ est $\{\alpha _{i}+\beta _{j}\}$, où $\{\alpha _{i}\}$ est le spectre de $A$ et $\{\beta _{j}\}$ le spectre de $B$; autrement dit, le spectre est la somme de toutes les paires possibles. Un exemple pratique est donné pour déduire le spectre de l'hypercube à partir des graphes dont il est le produit cartésien.
• Sommet-transitivité. Le produit cartésien $A\square B$ est sommet-transitif si et seulement si $A$ et $B$ sont sommet-transitifs.
• Connectivité. Le produit cartésien $A\square B$ est connexe si et seulement si $A$ et $B$ sont connexes.

Utilisation

De nombreux graphes sont définis comme produits cartésiens, et on peut donc utiliser les propriétés de l'opération avec celles des graphes de base pour en déduire les propriétés du graphe obtenu :

• Le graphe de Hamming $H(d,q)$ est le produit cartésien de $d$ graphes complets $K_{q}$. Un cas particulier intéressant est l'hypercube $Q_{d}=H(d,2)$.
• La grille $M(m,n)$ est obtenue par le produit cartésien de chemins $P_{m}\square P_{n}$.
• La grille torique $MT(m,n)$ est obtenue par le produit cartésien de deux graphes cycles $C_{m}\square C_{n}$.
• Le prisme $Y_{m,n}$ est obtenu par le produit cartésien d'un graphe cycle et d'un chemin $C_{m}\square P_{n}$.

Bibliographie

(en) Wilfried Imrich, Sandi Klavžar et Douglas F. Rall - Topics in graph theory : graphs and their cartesian product, Wellesley, Mass. : A K Peters, 2008, (ISBN 9781568814292).