PRODUCTO TENSORIAL DE DOS GRAFOS

El producto tensorial de dos grafos

La operación del producto tensorial (conjunción) entre dos grafos,

, está definida como y dos vértices y están relacionados si se cumple:

Ejemplo 13:

OBSERVACION 2.1.4: Por considerar sólo grafos simples, no existen las líneas llamadas bucles. Es por esto que al hacer el producto cartesiano entre los vértices de los grafos G1 y G2, no existe relación R entre los vértices que poseen alguna de sus componentes iguales. Por ejemplo, en aun cuando v1 R v2 en G2, y tampoco entre y aunque u1 R u2 en G1.


Ejemplo 14: Hallar el producto cartesiano entre un y un .

El siguiente teorema es una consecuencia directa de las definiciones de producto y composición de funciones y la demostración la dejamos como ejercicio para el lector.

TEOREMA 2.4 Sean G1 y G2 dos grafos disjuntos, entonces se cumple:

a) .
b)
c)
d)
e)