Producto de grafos

En el campo matemático de la teoría de grafos, el producto de grafos corresponde a una familia de operaciones binarias entre grafos que toma dos grafos G₁ y G_2, y produce el grafo H con las siguientes propiedades:

• El conjunto de vértices de H es el producto cartesiano V(G₁) × V(G₂), donde V(G₁) y V(G₂) son los conjuntos de vértices de G₁ y G₂, respectivamente.
• Dos vértices (u₁, u₂) y (v₁, v₂) de H están conectados por una arista si y solo si los vértices u₁, u₂, v₁, v₂ satisfacen las condiciones para cada tipo de producto (ver más abajo).

Producto cartesiano

El producto cartesiano de G₁ $\square$ G₂ es un grafo en donde dos vértices (a,c) y (b,d) son adyacentes en G₁ $\square$ G₂ si y solo si:

• a = b y c es adyacente con d en G₂, o
• c = d y a es adyacente con b en G₁.

Producto tensor

El producto tensor de G₁ × G₂ también llamado producto directo, producto cardinal, producto de Kronecker o conjunción es un grafo en donde dos vértices (a,c) y (b,d) son adyacentes en G₁ × G₂ si y solo si:

• a es adyacente con b , y
• c es adyacente con d.

Como operación entre grafos fue introducida por Alfred North Whitehead y Bertrand Russell en su libro Principia Mathematica publicado en 1912.

Véase también

• Anexo:Operaciones en grafos

• Datos: Q569347
• Multimedia: Graph products / Q569347