Produit fort (graphe)

Le Modèle:Lien, produit tensoriel de deux graphes chemin.

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

Construction

Soient deux graphes $G$ et $H$. Le produit tensoriel $G⊠H$ est défini comme suit :

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

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