Producto cartesiano de gráficos

Operación en teoría de grafos

Un producto cartesiano de dos gráficos

En teoría de grafos , el producto cartesiano G □ H de los grafos G y H es un grafo tal que:

• el conjunto de vértices de G □ H es el producto cartesiano V ( G ) × V ( H ) ; y
• dos vértices ( u , v ) y ( u' , v' ) son adyacentes en G □ H si y solo si
  • u = u' y v es adyacente a v' en H , o
  • v = v' y u es adyacente a u' en G .

El producto cartesiano de gráficos a veces se denomina producto de caja de gráficos [Harary 1969].

La operación es asociativa , ya que los grafos ( F □ G ) □ H y F □ ( G □ H ) son naturalmente isomorfos . La operación es conmutativa como operación sobre clases de isomorfismo de grafos, y más fuertemente los grafos G □ H y H □ G son naturalmente isomorfos , pero no es conmutativa como operación sobre grafos etiquetados .

La notación G × H se ha utilizado a menudo para productos cartesianos de grafos, pero ahora se utiliza más comúnmente para otra construcción conocida como producto tensorial de grafos . El símbolo del cuadrado pretende ser una notación intuitiva e inequívoca para el producto cartesiano, ya que muestra visualmente las cuatro aristas resultantes del producto cartesiano de dos aristas. ^[1]

Ejemplos

• El producto cartesiano de dos aristas es un ciclo en cuatro vértices: K ₂ □ K ₂ = C ₄ .
• El producto cartesiano de K ₂ y un gráfico de trayectoria es un gráfico de escalera .
• El producto cartesiano de dos gráficos de trayectoria es un gráfico de cuadrícula .
• El producto cartesiano de n aristas es un hipercubo:

${\displaystyle (K_{2})^{\square n}=Q_{n}.}$

Por lo tanto, el producto cartesiano de dos grafos hipercubos es otro hipercubo: Q _i □ Q _j = Q _i+j .

• El producto cartesiano de dos gráficos medianos es otro gráfico mediano.
• El gráfico de vértices y aristas de un prisma n es el gráfico del producto cartesiano K ₂ □ C _n .
• El gráfico de la torre es el producto cartesiano de dos gráficos completos.

Propiedades

Si un grafo conexo es un producto cartesiano, puede factorizarse únicamente como un producto de factores primos, grafos que no pueden descomponerse como productos de grafos. ^[2] Sin embargo, Imrich y Klavžar (2000) describen un grafo desconectado que puede expresarse de dos maneras diferentes como un producto cartesiano de grafos primos:

${\displaystyle (K_{1}+K_{2}+K_{2}^{2})\mathbin {\square } (K_{1}+K_{2}^{3})=(K_{1}+K_{2}^{2}+K_{2}^{4})\mathbin {\square } (K_{1}+K_{2}),}$

donde el signo más denota unión disjunta y los superíndices denotan exponenciación sobre productos cartesianos. Esto está relacionado con la identidad que

${\displaystyle {\begin{aligned}(1+x+x^{2})(1+x^{3})&=(1+x^{2}+x^{4})(1+x)\\&=1+x+x^{2}+x^{3}+x^{4}+x^{5}\\&=(1+x)(1+x+x^{2})(1-x+x^{2})\end{aligned}}}$

Ambos factores y no son polinomios irreducibles , pero sus factores incluyen coeficientes negativos y, por lo tanto, los grafos correspondientes no se pueden descomponer. En este sentido, el fallo de la factorización única en grafos (posiblemente desconectados) es similar a la afirmación de que los polinomios con coeficientes enteros no negativos son un semianillo que no cumple la propiedad de factorización única . ${\displaystyle 1+x^{3}}$ ${\displaystyle 1+x^{2}+x^{4}}$

Un producto cartesiano es transitivo en sus vértices si y sólo si cada uno de sus factores lo es. ^[3]

Un producto cartesiano es bipartito si y solo si cada uno de sus factores lo es. De manera más general, el número cromático del producto cartesiano satisface la ecuación

${\displaystyle \chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.}$ ^[4]

La conjetura de Hedetniemi establece una igualdad relacionada para el producto tensorial de grafos . El número de independencia de un producto cartesiano no se calcula tan fácilmente, pero como demostró Vizing (1963) satisface las desigualdades

${\displaystyle \alpha (G)\alpha (H)+\min\{|V(G)|-\alpha (G),|V(H)|-\alpha (H)\}\leq \alpha (G\mathbin {\square } H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.}$

La conjetura de Vizing establece que el número de dominación de un producto cartesiano satisface la desigualdad

${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (H).}$

El producto cartesiano de gráficos de distancias unitarias es otro gráfico de distancias unitarias. ^[5]

Los gráficos de productos cartesianos se pueden reconocer de manera eficiente, en tiempo lineal . ^[6]

Teoría de grafos algebraicos

La teoría de grafos algebraicos se puede utilizar para analizar el producto de grafos cartesianos. Si el grafo tiene vértices y la matriz de adyacencia , y el grafo tiene vértices y la matriz de adyacencia , entonces la matriz de adyacencia del producto cartesiano de ambos grafos está dada por ${\displaystyle G_{1}}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{1}\times n_{1}}$ ${\displaystyle \mathbf {A} _{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle n_{2}}$ ${\displaystyle n_{2}\times n_{2}}$ ${\displaystyle \mathbf {A} _{2}}$

${\displaystyle \mathbf {A} _{1\mathbin {\square } 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}}$,

donde denota el producto de Kronecker de matrices y denota la matriz identidad . ^[7] La ​​matriz de adyacencia del producto gráfico cartesiano es, por lo tanto, la suma de Kronecker de las matrices de adyacencia de los factores. ${\displaystyle \otimes }$ ${\displaystyle \mathbf {I} _{n}}$ ${\displaystyle n\times n}$

Teoría de categorías

Si consideramos un grafo como una categoría cuyos objetos son los vértices y cuyos morfismos son los caminos en el grafo, el producto cartesiano de grafos corresponde al curioso producto tensorial de categorías. El producto cartesiano de grafos es uno de los dos productos de grafos que convierten la categoría de grafos y los homomorfismos de grafos en una categoría monoidal cerrada simétrica (en oposición a una categoría monoidal meramente simétrica), siendo el otro el producto tensorial de grafos . ^[8] El hom interno para el producto cartesiano de grafos tiene homomorfismos de grafos de a como vértices y "transformaciones no naturales" entre ellos como aristas. ^[8] ${\displaystyle [G,H]}$ ${\displaystyle G}$ ${\displaystyle H}$

Historia

Según Imrich y Klavžar (2000), los productos cartesianos de grafos fueron definidos en 1912 por Whitehead y Russell . Posteriormente fueron redescubiertos en varias ocasiones, en particular por Gert Sabidussi  (1960).

Notas

1. Hahn y Sabidussi (1997).
2. Sabidussi (1960); Vizing (1963).
3. Imrich y Klavžar (2000), Teorema 4.19.
4. Sabiduría (1957).
5. Horvat y Pisanski (2010).
6. Imrich y Peterin (2007). Para algoritmos de tiempo polinomial anteriores , consulte Feigenbaum, Hershberger & Schäffer (1985) y Aurenhammer, Hagauer & Imrich (1992).
7. Kaveh y Rahami (2005).
8. Weber 2013.

Referencias

• Aurenhammer, F. ; Hagauer, J.; Imrich, W. (1992), "Factorización de grafos cartesianos a un coste logarítmico por arista", Computational Complexity , 2 (4): 331–349, doi :10.1007/BF01200428, MR  1215316.
• Feigenbaum, Joan ; Hershberger, John ; Schäffer, Alejandro A. (1985), "Un algoritmo de tiempo polinomial para hallar los factores primos de gráficos de productos cartesianos", Discrete Applied Mathematics , 12 (2): 123–138, doi : 10.1016/0166-218X(85)90066-6 , MR  0808453.
• Hahn, Geňa; Sabidussi, Gert (1997), Simetría de grafos: métodos algebraicos y aplicaciones, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, ISBN 978-0-7923-4668-5.
• Horvat, Boris; Pisanski, Tomaž (2010), "Productos de gráficos de distancia unitaria", Discrete Mathematics , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR  2610282.
• Imrich, Wilfried ; Klavžar, Sandi (2000), Gráficos de productos: estructura y reconocimiento , Wiley, ISBN 0-471-37039-8.
• Imrich, Wilfried ; Klavžar, Sandi; Rall, Douglas F. (2008), Gráficos y sus productos cartesianos , AK Peters, ISBN 1-56881-429-1.
• Imrich, Wilfried ; Peterin, Iztok (2007), "Reconocimiento de productos cartesianos en tiempo lineal", Matemáticas discretas , 307 (3–5): 472–483, doi : 10.1016/j.disc.2005.09.038 , MR  2287488.
• Kaveh, A.; Rahami, H. (2005), "Un método unificado para la descomposición propia de productos gráficos", Communications in Numerical Methods in Engineering with Biomedical Applications , 21 (7): 377–388, doi :10.1002/cnm.753, MR  2151527.
• Sabidussi, G. (1957), "Gráficos con un grupo dado y propiedades teóricas de grafos dadas", Canadian Journal of Mathematics , 9 : 515–525, doi :10.4153/CJM-1957-060-7, MR  0094810.
• Sabidussi, G. (1960), "Multiplicación de gráficos", Mathematische Zeitschrift , 72 : 446–457, doi : 10.1007/BF01162967, hdl : 10338.dmlcz/102459 , MR  0209177.
• Vizing, VG (1963), "El producto cartesiano de grafos", Vycisl. Sistemy , 9 : 30–43, MR  0209178.
• Weber, Mark (2013), "Productos libres de álgebras operadas superiores", TAC , 28 (2): 24–65.

Enlaces externos

• Weisstein, Eric W. "Producto cartesiano gráfico". MathWorld .