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 G1 y G2, y produce el grafo H con las siguientes propiedades:

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


Producto cartesiano

El producto cartesiano de G1 G2 es un grafo en donde dos vértices (a,c) y (b,d) son adyacentes en G1 G2 si y solo si:

  • a = b y c es adyacente con d en G2, o
  • c = d y a es adyacente con b en G1.

Producto tensor

El producto tensor de G1 × G2 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 G1 × G2 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
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.