Producto de grafos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 (u1u2) y (v1v2) 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[editar]

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

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

Graph-Cartesian-product.svg

Producto tensor[editar]

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 operacion entre grafos fue introducida por Alfred North Whitehead y Bertrand Russell en su libro Principia Mathematica publicado en 1912.

Graph-tensor-product.svg

Véase también[editar]