Produit tensoriel (graphe)
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Cet article concerne le produit tensoriel de graphes. Pour le produit tensoriel en algèbre, voir produit tensoriel.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Graph-tensor-product.svg/310px-Graph-tensor-product.svg.png)
Le produit tensoriel est une opération sur deux graphes et résultant en un graphe . Il est également appelé produit direct, produit de Kronecker ou produit catégorique.
Construction
Soient deux graphes et . Le produit tensoriel est défini comme suit[1] :
- l'ensemble de ses sommets est le produit cartésien ;
- et sont adjacents dans si et seulement si et sont adjacents dans et et sont adjacents dans . Autrement dit, deux sommets sont voisins si les sommets dont ils sont issus étaient voisins dans les deux graphes.
Propriétés
- La matrice d'adjacence de est le produit de Kronecker des matrices d'adjacence de et .
- La conjecture d'Hedetniemi (en) concernait le nombre chromatique du produit tensoriel de deux graphes : . Elle est cependant réfutée en 2019 par Yaroslav Shitov qui montre qu'il est possible d'avoir [2].
Références
- ↑ (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.5, p. 237
- ↑ (en) Yaroslav Shitov, « Counterexamples to Hedetniemi's conjecture », Annals of Mathematics, vol. 190, no 2, , p. 663–667 (ISSN 0003-486X et 1939-8980, DOI 10.4007/annals.2019.190.2.6, lire en ligne, consulté le )
v · m Opérations en théorie des graphes | |
---|---|
|
Portail de l'informatique théorique
Portail des mathématiques