En teoría de grafos , el producto tensorial G × H de los grafos G y H es un grafo tal que
El producto tensorial también se denomina producto directo , producto de Kronecker , producto categórico , producto cardinal , producto relacional , producto directo débil o conjunción . Como operación sobre relaciones binarias, el producto tensorial fue introducido por Alfred North Whitehead y Bertrand Russell en sus Principia Mathematica (1912). También es equivalente al producto de Kronecker de las matrices de adyacencia de los grafos. [1]
La notación G × H también se utiliza (y antiguamente se utilizaba normalmente) para representar otra construcción conocida como producto cartesiano de grafos , pero hoy en día se refiere más comúnmente al producto tensorial. El símbolo de la cruz muestra visualmente las dos aristas resultantes del producto tensorial de dos aristas. [2] Este producto no debe confundirse con el producto fuerte de grafos .
El producto tensorial es el producto de la teoría de categorías en la categoría de grafos y homomorfismos de grafos . Es decir, un homomorfismo con G × H corresponde a un par de homomorfismos con G y con H. En particular, un grafo I admite un homomorfismo en G × H si y solo si admite un homomorfismo en G y en H.
Para ver que, en una dirección, observe que un par de homomorfismos f G : I → G y f H : I → H produce un homomorfismo
En la otra dirección, un homomorfismo f : I → G × H puede estar compuesto con los homomorfismos de proyecciones
para producir homomorfismos para G y para H .
La matriz de adyacencia de G × H es el producto Kronecker (tensor) de las matrices de adyacencia de G y H.
Si un grafo puede representarse como un producto tensorial, entonces puede haber múltiples representaciones diferentes (los productos tensoriales no satisfacen la factorización única), pero cada representación tiene el mismo número de factores irreducibles. Imrich (1998) ofrece un algoritmo de tiempo polinomial para reconocer grafos de productos tensoriales y encontrar una factorización de dichos grafos.
Si G o H son bipartitos , entonces también lo es su producto tensorial. G × H es conexo si y solo si ambos factores son conexos y al menos un factor no es bipartito. [3] En particular, la doble cubierta bipartita de G es conexa si y solo si G es conexo y no bipartito.
La conjetura de Hedetniemi , que proporcionó una fórmula para el número cromático de un producto tensorial, fue refutada por Yaroslav Shitov (2019).
El producto tensorial de grafos dota a la categoría de grafos y homomorfismos de grafos de la estructura de una categoría monoidal cerrada simétrica . Sea G 0 el conjunto subyacente de vértices del grafo G . El hom interno [ G , H ] tiene funciones f : G 0 → H 0 como vértices y una arista desde f : G 0 → H 0 hasta f' : G 0 → H 0 siempre que una arista { x , y } en G implique { f ( x ), f ' ( y )} en H . [4]
