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 editar
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 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 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 editar
Datos: Q569347
Multimedia: Graph products / Q569347
