PRODUCTO CARTESIANO DE DOS GRAFOS

Producto cartesiano de dos grafos G1xG2

La operación de "producto" (cartesiano) entre dos grafos,G1xG2 , está definida como , y dos vértices,

y están relacionados si se cumple:

Ejemplo 9: El grafo de la fig. 2.11, representa el producto entre dos grafos G1 y G2.

Ejemplo 10:

Ejemplo 11: La fig. 2.13 muestra la construcción de un

.

tiene vértices , donde cada es 0 ó 1. Dos vértices de están relacionados, si sus n-tuplas difieren en exactamente un lugar, como se puede ver en fig. 2.12 y fig. 2.13.

Nota:

El grafo hipercubo de dimensión n, Qn se define (de manera recurrente) como