Producto Cartesiano de Grafos
En teoría de grafos, el producto cartesiano G
La operación es asociativa, cuando ya que los grafos (F
H) son grafos naturalmente isomorfos.
La operación es conmutativa como una operación en las clases de isomorfismo de grafos, y más aún, los grafos G
G son naturalmente isomorfos; sin embargo esta no es una operación conmutativa en los grafos etiquetados.
La notación G × H a menudo ha sido utilizado para productos Cartesianos de grafos, pero hoy en día es más generalmente usado para otra construcción, conocida como el producto tensor de grafos.
El símbolo cuadrado es una notación intuitiva e inequívoca para el producto Cartesiano, ya que muestra visualmente las cuatro aristas que resultan del producto Cartesiano de dos aristas.
[1] Si un grafo conectado es un producto Cartesiano, entonces este puede ser factorizado únicamente como producto de factores primos, que son grafos que no pueden ser descompuestos como productos de grafos ellos mismos.
[1] Sin embargo,Imrich y Klavžar (2000) & Klavžar (2000) describen un grafo no conexo que puede ser expresado en dos maneras diferentes como producto Cartesiano de grafos primos: donde el signo de más arriba denota una unión disjunta y los superíndices denotan exponenciación sobre productos Cartesianos.
Más generalmente, el número cromático del producto Cartesiano satisface la ecuación La conjetura de Hedetniemi satisface una igualdad relacionada para el producto tensor de grafos.
[5] El producto cartesiano de grafos puede ser reconocido eficientemente, en tiempo lineal.
[3] La teoría de grafos algebraica puede utilizarse para analizar el producto Cartesiano de grafos.
, entonces la matriz de adyacencia del producto Cartesiano de ambos grafos está dado por Dónde
denota el producto Kronecker de matrices e
Viendo un grafo como una categoría cuyos objetos son los vértices y cuyos morfismos son los caminos en el grafo, el producto Cartesiano de grafos corresponde al producto de tensor gracioso de categorías.
como vértices y "transformaciones antinaturales" entre ellos como aristas.
[4] Según Imrich y Klavžar (2000), los productos Cartesianos de grafos fueron definidos en 1912 por Whitehead y Russell.
Estos fueron repetidamente redescubiertos más tarde, notablemente por Gert Sabidussi (1960).
