producto gráfico

En teoría de grafos , un producto de grafos es una operación binaria sobre grafos . Específicamente, 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 _{2 .}

Los productos de grafos difieren en cuál 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 varían bastante en la literatura; aunque lo siguiente pueda considerarse algo estándar, se recomienda a los lectores que verifiquen qué definición utiliza un autor en particular para un producto gráfico, especialmente en textos más antiguos.

Incluso para 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 el número de aristas en un producto también pueden fallar cuando se incluyen 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${\displaystyle E=1}$y no${\displaystyle E=2}$como la fórmula${\displaystyle E_{G\times H}=2E_{G}E_{H}}$sugeriría.

La siguiente tabla muestra los productos gráficos más comunes, con${\displaystyle \sim }$que denota "está conectado por una arista a", y${\displaystyle \not \sim }$que denota no adyacencia. Mientras${\displaystyle \not \sim }$permite la igualdad,${\displaystyle \not \simeq }$Esto significa que deben ser distintos y no adyacentes. Los símbolos de operadores que se enumeran aquí no son en absoluto estándar, especialmente en documentos antiguos.

En general, un producto gráfico se determina por cualquier condición para${\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}$que se puede expresar en términos de${\displaystyle a_{n}=b_{n}}$y${\displaystyle a_{n}\sim b_{n}}$.

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

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

• operaciones gráficas

• Weisstein, Eric W. "Producto gráfico" . MathWorld .
• Weisstein, Eric W. "Producto cartesiano de grafos" . MathWorld .
• Weisstein, Eric W. "Producto tensorial gráfico" . MathWorld .
• Weisstein, Eric W. "Producto fuerte de grafos" . MathWorld .
• Weisstein, Eric W. "Producto lexicográfico de grafos" . MathWorld .