En teoría de grafos , el producto cartesiano G H de las gráficas G y H es una gráfica tal que
- el conjunto de vértices de G H es el producto cartesiano V ( G ) × V ( H ); y
- dos vértices ( u, u ' ) y ( v, v' ) son adyacentes en G H si y solo si
- u = v y u ' es adyacente a v' en H , o
- u ' = v' y u es adyacente a v en G .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/77/Graph-Cartesian-product.svg/300px-Graph-Cartesian-product.svg.png)
El producto cartesiano de las gráficas a veces se denomina producto de caja de las gráficas [Harary 1969].
La operación es asociativa , ya que las gráficas ( F G ) H y F ( G H ) son naturalmente isomorfos. La operación es conmutativa como una operación en clases de isomorfismo de gráficos, y más fuertemente los gráficos G H y H G son naturalmente isomórficos , pero no son conmutativos como una operación en gráficos etiquetados.
La notación G × H se ha utilizado a menudo para los productos cartesianos de los gráficos, pero ahora se utiliza más comúnmente para otra construcción conocida como el producto tensorial de los gráficos . El símbolo del cuadrado es una notación intuitiva e inequívoca para el producto cartesiano, ya que muestra visualmente los cuatro bordes resultantes del producto cartesiano de dos bordes. [1]
Ejemplos de
- El producto cartesiano de dos aristas es un ciclo de cuatro vértices: K 2 K 2 = C 4 .
- El producto cartesiano de K 2 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:
- Por lo tanto, el producto cartesiano de dos gráficos de hipercubo es otro hipercubo: Q iQ j = Q i + j .
- El producto cartesiano de dos gráficas medianas es otra gráfica mediana.
- La gráfica de vértices y aristas de un prisma es la gráfica de producto cartesiano K 2 C n .
- La gráfica de la torre es el producto cartesiano de dos gráficas completas.
Propiedades
Si una gráfica conectada es un producto cartesiano, se puede factorizar únicamente como un producto de factores primos, gráficas que no pueden descomponerse en sí mismas como productos de gráficas. [2] Sin embargo, Imrich y Klavžar (2000) describen un gráfico desconectado que se puede expresar de dos formas diferentes como un producto cartesiano de gráficos primos:
- (K 1 + K 2 + K 2 2 ) (K 1 + K 2 3 ) = (K 1 + K 2 2 + K 2 4 ) (K 1 + K 2 ),
donde el signo más denota unión disjunta y los superíndices denotan exponenciación sobre productos cartesianos.
Un producto cartesiano es transitivo de vértice si y solo 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
- χ (G H) = máximo {χ (G), χ (H)}. [4]
La conjetura de Hedetniemi establece una igualdad relacionada para el producto tensorial de las gráficas . El número de independencia de un producto cartesiano no se calcula tan fácilmente, pero, como demostró Vizing (1963) , satisface las desigualdades
- α ( G ) α ( H ) + min {| V ( G ) | -α ( G ), | V ( H ) | -α ( H )} ≤ α ( GH ) ≤ mínimo {α ( G ) | V ( H ) |, α ( H ) | V ( G ) |}.
La conjetura de Vizing establece que el número de dominación de un producto cartesiano satisface la desigualdad
- γ ( GH ) ≥ γ ( G ) γ ( H ).
El producto cartesiano de los gráficos de unidad de distancia es otro gráfico de unidad de distancia. [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 gráfico posee vértices y el matriz de adyacencia y el gráfico posee vértices y el matriz de adyacencia , entonces la matriz de adyacencia del producto cartesiano de ambas gráficas viene dada por
- ,
dónde denota el producto de Kronecker de matrices y denota el matriz de 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.
Teoría de categorías
Al ver un gráfico como una categoría cuyos objetos son los vértices y cuyos morfismos son los caminos en el gráfico, el producto cartesiano de los gráficos corresponde al producto tensorial divertido de las categorías. El producto cartesiano de las gráficas es uno de los dos productos de gráficas que convierten la categoría de gráficas y los homomorfismos de gráficas en una categoría monoidal cerrada simétrica (en oposición a monoidal simétrica meramente), siendo la otra el producto tensorial de las gráficas . [8] El hogar interno porque el producto cartesiano de las gráficas tiene homomorfismos de gráficas de a como vértices y " transformaciones no naturales " entre ellos como aristas. [8]
Historia
Según Imrich y Klavžar (2000) , los productos cartesianos de los gráficos fueron definidos en 1912 por Whitehead y Russell . Posteriormente fueron redescubiertos repetidamente, en particular por Gert Sabidussi ( 1960 ).
Notas
- ^ Hahn y Sabidussi (1997) .
- ^ Sabidussi (1960) ; Vizing (1963) .
- ^ Imrich y Klavžar (2000) , Teorema 4.19.
- ^ Sabidussi (1957) .
- ^ Horvat y Pisanski (2010) .
- ^ Imrich y Peterin (2007) . Paraalgoritmos de tiempo polinomial anteriores, consulte Feigenbaum, Hershberger & Schäffer (1985) y Aurenhammer, Hagauer & Imrich (1992) .
- ^ Kaveh y Rahami (2005) .
- ↑ a b Weber, 2013 .
Referencias
- Aurenhammer, F .; Hagauer, J .; Imrich, W. (1992), "Factorización de gráficos cartesianos a costo logarítmico por borde", 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 encontrar los factores primos de gráficas de productos cartesianos", Matemáticas aplicadas discretas , 12 (2): 123-138, doi : 10.1016 / 0166-218X (85) 90066 -6 , MR 0808453.
- Hahn, Geňa; Sabidussi, Gert (1997), Simetría gráfica: métodos y aplicaciones algebraicos , Serie de Institutos de Ciencias Avanzadas de la OTAN, 497 , Springer, p. 116, ISBN 978-0-7923-4668-5.
- Horvat, Boris; Pisanski, Tomaž (2010), "Productos de gráficos de distancia unitaria", Matemáticas discretas , 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), "Recognizing Cartesian products in linear time", Discrete Mathematics , 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", Comunicaciones en métodos numéricos en ingeniería con aplicaciones biomédicas , 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 gráficos dadas", Canadian Journal of Mathematics , 9 : 515–525, doi : 10.4153 / CJM-1957-060-7 , MR 0094810.
- Sabidussi, G. (1960), "Graph multiplication", Mathematische Zeitschrift , 72 : 446–457, doi : 10.1007 / BF01162967 , hdl : 10338.dmlcz / 102459 , MR 0209177.
- Vizing, VG (1963), "El producto cartesiano de los gráficos", 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. "Graph Cartesian Product" . MathWorld .