![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Graph-Cartesian-product.svg/langes-640px-Graph-Cartesian-product.svg.png&w=640&q=50)
Producto Cartesiano de Grafos
De Wikipedia, la enciclopedia encyclopedia
En teoría de grafos, el producto cartesiano GH de los grafos G y H es un grafo tal que
- El conjunto de vértices de G
H es el producto Cartesiano V(G) × V(H); y
- Dos vértices (u,u' ) y (v,v' ) son adyacentes en G
H sí y sólo si alguna de las siguientes condiciones se cumple
- u = v, y u' es adyacente a v' en H, o
- u' = v' , y u es adyacente a v en G.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Graph-Cartesian-product.svg/640px-Graph-Cartesian-product.svg.png)
El producto Cartesiano de grafos es a veces llamado el producto caja de grafos [Harary 1969].
La operación es asociativa, cuando ya que los grafos (F G)
H y F
(G
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
H y H
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]