Produit cartésien (graphe)

Produit cartésien de deux graphes.

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

• ${\displaystyle V(H)=\{(ss')|s\in V,s'\in V'\}}$. Autrement dit, l'ensemble résultant des sommets ${\displaystyle V(H)}$ est le produit cartésien ${\displaystyle V(G)\times V(G')}$.
• ${\displaystyle 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.

• Diamètre. Le diamètre ${\displaystyle D_{H}}$ du produit cartésien de ${\displaystyle G}$ et ${\displaystyle G'}$ est ${\displaystyle D_{H}=D_{G}+D_{G'}}$.
• L'opération ${\displaystyle \square }$ est commutative et associative.
• Spectre. Le spectre d'un produit cartésien ${\displaystyle A\square B}$ est ${\displaystyle \{\alpha _{i}+\beta _{j}\}}$, où ${\displaystyle \{\alpha _{i}\}}$ est le spectre de ${\displaystyle A}$ et ${\displaystyle \{\beta _{j}\}}$ le spectre de ${\displaystyle B}$; autrement dit, le spectre est la somme de toutes les paires possibles[1]. 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 ${\displaystyle A\square B}$ est sommet-transitif si et seulement si ${\displaystyle A}$ et ${\displaystyle B}$ sont sommet-transitifs[2].
• Connectivité. Le produit cartésien ${\displaystyle A\square B}$ est connexe si et seulement si ${\displaystyle A}$ et ${\displaystyle B}$ sont connexes[2].

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

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

• Portail de l'informatique théorique
• Portail des mathématiques