Produit fort (graphe)

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

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.

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.

Références

1. (en) Krishnaiyan Thulasiraman, Subramanian Arumugam, Andreas Brandstädt et Takao Nishizeki, Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, CRC Press, coll. « Chapman & Hall/CRC Computer and Information Science Series », 2016, 1195 p. (ISBN 9781420011074), Definition 10.6, p. 237