Producto gráfico

Operación binaria sobre gráficos

En teoría de grafos , un producto de grafos es una operación binaria sobre grafos . En concreto, es una operación que toma dos grafos G ₁ y G ₂ y produce un 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 ( a ₁ , a ₂ ) y ( b ₁ , b ₂ ) de H están conectados por una arista , si y solo si se cumple una condición sobre a ₁ , b ₁ en G ₁ y a ₂ , b ₂ en G ₂ .

Los productos de grafos difieren en qué es exactamente esta condición. Siempre se trata de si los vértices a _n , b _n en G _n son iguales o están conectados por una arista.

La terminología y la notación para productos gráficos específicos en la literatura varían bastante; aunque lo siguiente puede considerarse algo estándar, se recomienda a los lectores verificar qué definición utiliza un autor en particular para un producto gráfico, especialmente en textos más antiguos.

Incluso para las definiciones más estándar, no siempre es consistente en la literatura cómo manejar los bucles propios . Las fórmulas a continuación para la cantidad de aristas en un producto también pueden fallar al incluir bucles propios. Por ejemplo, el producto tensorial de un bucle propio de un solo vértice consigo mismo es otro bucle propio de un solo vértice con , y no como sugeriría la fórmula . ${\displaystyle E=1}$ ${\displaystyle E=2}$ ${\displaystyle E_{G\times H}=2E_{G}E_{H}}$

Tabla de descripción general

La siguiente tabla muestra los productos de grafos más comunes, con la expresión "está conectado por una arista a" y la expresión "no adyacente". Si bien permite la igualdad, significa que deben ser distintos y no adyacentes. Los símbolos de operador que se enumeran aquí no son estándar, especialmente en artículos antiguos. ${\displaystyle \sim }$ ${\displaystyle \not \sim }$ ${\displaystyle \not \sim }$ ${\displaystyle \not \simeq }$

En general, un producto gráfico está determinado por cualquier condición que pueda expresarse en términos de y . ${\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}$ ${\displaystyle a_{n}=b_{n}}$ ${\displaystyle a_{n}\sim b_{n}}$

Mnemotécnico

Sea el gráfico completo en dos vértices (es decir, una sola arista). Los gráficos del producto , y se ven exactamente como el gráfico que representa al operador. Por ejemplo, es un ciclo de cuatro (un cuadrado) y es el gráfico completo en cuatro vértices. ${\displaystyle K_{2}}$ ${\displaystyle K_{2}\square K_{2}}$ ${\displaystyle K_{2}\times K_{2}}$ ${\displaystyle K_{2}\boxtimes K_{2}}$ ${\displaystyle K_{2}\square K_{2}}$ ${\displaystyle K_{2}\boxtimes K_{2}}$

La notación del producto lexicográfico sirve para recordar que este producto no es conmutativo. El gráfico resultante parece sustituir una copia de por cada vértice de . ${\displaystyle G_{1}[G_{2}]}$ ${\displaystyle G_{2}}$ ${\displaystyle G_{1}}$

Véase también

• Operaciones gráficas

Notas

1. Roberson, David E.; Mancinska, Laura (2012). "Homomorfismos de grafos para jugadores cuánticos". Journal of Combinatorial Theory, Serie B. 118 : 228–267. arXiv : 1212.1724 . doi : 10.1016/j.jctb.2015.12.009.
2. Bačík, R.; Mahajan, S. (1995). "Programación semidefinida y sus aplicaciones a problemas NP". Computing and Combinatorics . Apuntes de clase en informática. Vol. 959. pág. 566. doi :10.1007/BFb0030878. ISBN 978-3-540-60216-3.
3. El hom-producto de ^[2] es el complemento gráfico del producto homomórfico de. ^[1]

Referencias

• Imrich, Wilfried; Klavžar, Sandi (2000). Gráficos de productos: estructura y reconocimiento . Wiley. ISBN 978-0-471-37039-0.