Produit fort (graphe)

Le produit fort est une opération sur deux graphes ${\displaystyle G}$ et ${\displaystyle H}$ résultant en un graphe ${\displaystyle G\boxtimes H}$. Il est également appelé produit normal.

Le graphe du roi (en), produit tensoriel de deux graphes chemin.

Construction

Soient deux graphes ${\displaystyle G}$ et ${\displaystyle H}$. Le produit tensoriel ${\displaystyle G\boxtimes H}$ est défini comme suit^[1] :

• l'ensemble de ses sommets est le produit cartésien ${\displaystyle V(G)\times V(H)}$ ;
• ${\displaystyle (g,h)}$ et ${\displaystyle (g',h')}$ sont adjacents dans ${\displaystyle G\boxtimes H}$ si et seulement si l'une de ces conditions est vérifiée :
  • ${\displaystyle g=g'}$ et ${\displaystyle h}$ est adjacent à ${\displaystyle h'}$
  • ${\displaystyle g}$ est adjacent à ${\displaystyle g'}$ et ${\displaystyle h=h'}$
  • ${\displaystyle g}$ est adjacent à ${\displaystyle g'}$ et ${\displaystyle h}$ est adjacent à ${\displaystyle h'}$.

Le produit fort est l'union du produit cartésien et du produit tensoriel.