Produit fort (graphe)

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

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

Construction

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

  • l'ensemble de ses sommets est le produit cartésien V ( G ) × V ( H ) {\displaystyle V(G)\times V(H)}  ;
  • ( g , h ) {\displaystyle (g,h)} et ( g ′ , h ′ ) {\displaystyle (g',h')} sont adjacents dans G ⊠ H {\displaystyle G\boxtimes H} si et seulement si l'une de ces conditions est vérifiée :
    • g = g ′ {\displaystyle g=g'} et h {\displaystyle h} est adjacent à h ′ {\displaystyle h'}
    • g {\displaystyle g} est adjacent à g ′ {\displaystyle g'} et h = h ′ {\displaystyle h=h'}
    • g {\displaystyle g} est adjacent à g ′ {\displaystyle g'} et h {\displaystyle h} est adjacent à h ′ {\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 », , 1195 p. (ISBN 9781420011074), Definition 10.6, p. 237
v · m
Opérations en théorie des graphes
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail des mathématiques