Hispanopedia Wiki
En la teoría de grafos , una rama de las matemáticas, la k -ésima potencia G k de un grafo no dirigido G es otro grafo que tiene el mismo conjunto de vértices , pero en el que dos vértices son adyacentes cuando su distancia en G es como máximo k . Las potencias de grafos se denominan utilizando una terminología similar a la de la exponenciación de números: G 2 se llama el cuadrado de G , G 3 se llama el cubo de G , etc. [ 1 ]
Las potencias de un grafo deben distinguirse de los productos de un grafo consigo mismo, que (a diferencia de las potencias) generalmente tienen muchos más vértices que el grafo original.
Propiedades
Si un grafo tiene diámetro d , entonces su d -ésima potencia es el grafo completo . [ 2 ] Si una familia de grafos tiene ancho de clique acotado , entonces sus d -ésimas potencias también lo tienen para cualquier d fijo . [ 3 ]
Colorante
El coloreado de gráficos en el cuadrado de un gráfico puede utilizarse para asignar frecuencias a los participantes de redes de comunicación inalámbricas de manera que ningún par de participantes interfiera entre sí en ninguno de sus vecinos comunes, [ 4 ] y para encontrar dibujos de gráficos con alta resolución angular . [ 5 ]
Tanto el número cromático como la degeneración de la k -ésima potencia de un grafo planar de grado máximo Δ son O (Δ ⌊ k /2⌋ ) , donde la cota de degeneración muestra que se puede usar un algoritmo de coloración voraz para colorear el grafo con esta cantidad de colores. [ 4 ] Para el caso especial de un cuadrado de un grafo planar, Wegner conjeturó en 1977 que el número cromático del cuadrado de un grafo planar es como máximo max(Δ + 5, 3Δ / 2 + 1) , y se sabe que el número cromático es como máximo 5Δ / 3 + O (1) . [ 6 ] [ 7 ] De manera más general, para cualquier grafo con degeneración d y grado máximo Δ , la degeneración del cuadrado del grafo es O ( d Δ) , por lo que muchos tipos de grafos dispersos, además de los grafos planares, también tienen cuadrados cuyo número cromático es proporcional a Δ .
Aunque el número cromático del cuadrado de un grafo no planar con grado máximo Δ puede ser proporcional a Δ 2 en el peor de los casos, es menor para grafos de gran circunferencia , estando acotado por O (Δ 2 / log Δ) en este caso. [ 8 ]
Determinar el número mínimo de colores necesarios para colorear el cuadrado de un grafo es NP-difícil , incluso en el caso planar. [ 9 ]
Hamiltonicidad
El cubo de todo grafo conexo contiene necesariamente un ciclo hamiltoniano . [ 10 ] No es necesariamente cierto que el cuadrado de un grafo conexo sea hamiltoniano, y determinar si el cuadrado es hamiltoniano es un problema NP-completo . [ 11 ] Sin embargo, según el teorema de Fleischner , el cuadrado de un grafo conexo de 2 vértices es siempre hamiltoniano. [ 12 ]
Complejidad computacional
La k -ésima potencia de un grafo con n vértices y m aristas se puede calcular en tiempo O ( mn ) realizando una búsqueda en anchura comenzando desde cada vértice para determinar las distancias a todos los demás vértices, o ligeramente más rápido utilizando algoritmos más sofisticados. [ 13 ] Alternativamente, si A es una matriz de adyacencia para el grafo, modificada para tener entradas no nulas en su diagonal principal, entonces las entradas no nulas de A k dan la matriz de adyacencia de la k -ésima potencia del grafo, [ 14 ] de lo cual se deduce que la construcción de k -ésimas potencias se puede realizar en una cantidad de tiempo que está dentro de un factor logarítmico del tiempo para la multiplicación de matrices .
Las potencias k de los árboles se pueden reconocer en un tiempo lineal en el tamaño del grafo de entrada. [ 15 ]
Dado un grafo, decidir si es el cuadrado de otro grafo es NP-completo . [ 16 ] Además, es NP-completo determinar si un grafo es una k -ésima potencia de otro grafo, para un número dado k ≥ 2 , o si es una k -ésima potencia de un grafo bipartito , para k > 2. [ 17 ]
En grafos dirigidos
En el cuadrado de un grafo dirigido (o digrafo), cada par de vértices conectados por un camino dirigido de longitud dos se conectan mediante un camino en la misma dirección de longitud uno. Por lo tanto, los pares de puntos que apuntan al mismo vértice no generan una conexión entre ellos en el cuadrado de un grafo dirigido.
El segundo problema de vecindad se puede plantear en términos del cuadrado de un digrafo, preguntando si existe un vértice en cada grafo orientado cuyo grado aumenta al menos en un factor de dos cuando el grafo se eleva al cuadrado. [ 18 ]
subgrafos inducidos
El semicasqueño de un grafo bipartito G es el subgrafo de G2 inducido por un lado de la bipartición de G. Los grafos de mapas son los semicasqueños de grafos planares , [ 19 ] y los grafos de cubos divididos por la mitad son los semicasqueños de grafos hipercubos . [ 20 ]
Las potencias de las hojas son los subgrafos de potencias de árboles inducidos por las hojas del árbol. Una potencia de k hojas es una potencia de hoja cuyo exponente es k . [ 21 ]
Referencias
- ↑ Bondy, Adrian; Murty, USR (2008), Teoría de grafos , Textos de posgrado en matemáticas, vol. 244, Springer, pág. 82, ISBN 9781846289699.
- ↑ Weisstein, Eric W. , "Graph Power" , MathWorld
- ↑ Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Graph-theoretic concepts in computer science , Lecture Notes in Comput. Sci., vol. 2880, Springer, Berlín, pp. 370–382 , doi : 10.1007/978-3-540-39890-5_32 , ISBN 978-3-540-20452-7, MR 2080095 .
- 1 2 Agnarsson, Geir; Halldórsson, Magnús M. (2000), "Coloring powers of planar Graphs", Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos (SODA '00) , San Francisco, California, EE. UU ., págs .
{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace ) . - ↑ Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E .; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing , 22 (5): 1035–1052 , doi : 10.1137/0222063 , MR 1237161 .
- ↑ Kramer, Florica; Kramer, Horst (2008), "Un estudio sobre la coloración de distancias de grafos", Matemáticas Discretas , 308 ( 2–3 ): 422–426 , doi : 10.1016/j.disc.2006.11.059 , MR 2378044 .
- ↑ Molloy, Michael; Salavatipour, Mohammad R. (2005), "Una cota para el número cromático del cuadrado de un grafo planar", Journal of Combinatorial Theory , Serie B, 94 (2): 189–213 , doi : 10.1016/j.jctb.2004.12.005 , hdl : 1807/9473 , MR 2145512 .
- ↑ Alon, Noga ; Mohar, Bojan (2002), "El número cromático de potencias de grafos", Combinatorics, Probability and Computing , 11 (1): 1–10 , doi : 10.1017/S0963548301004965 , MR 1888178 , S2CID 2706926 .
- ↑ Agnarsson y Halldórsson (2000) enumeran publicaciones que demuestran la NP-dureza para grafos generales por McCormick (1983) y Lin y Skiena (1995), y para grafos planares por Ramanathan y Lloyd (1992, 1993).
- ↑ Bondy y Murty (2008) , pág. 105.
- ↑ Underground, Polly (1978), "Sobre grafos con cuadrados hamiltonianos", Matemáticas Discretas , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR 0522906 .
- ↑ Diestel, Reinhard (2012), "10. Ciclos hamiltonianos", Teoría de grafos (PDF) (4.ª edición electrónica corregida) .
- ↑ Chan, Timothy M. (2012), "Caminos más cortos entre todos los pares de grafos no dirigidos no ponderados entiempo", ACM Transactions on Algorithms , 8 (4): A34:1–A34:17, doi : 10.1145/2344422.2344424 , MR 2981912 , S2CID 1212001
- ↑ Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi (2011), Handbook of Product Graphs , Discrete Mathematics and Its Applications (2.ª ed.), CRC Press, p. 94, ISBN 9781439813058.
- ↑ Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I (2015), "Algoritmos de tiempo lineal para problemas de raíz de árbol", Algorithmica , 71 (2): 471– 495, doi : 10.1007/s00453-013-9815-y , S2CID 253971732 .
- ↑ Motwani, R.; Sudan, M. (1994), "Calcular raíces de grafos es difícil", Matemáticas Aplicadas Discretas , 54 : 81–88 , doi : 10.1016/0166-218x(94)00023-9.
- ↑ Le, Van Bang; Nguyen, Ngoc Tuy (2010), "Resultados de dureza y algoritmos eficientes para potencias de grafos", Conceptos de teoría de grafos en informática: 35.º taller internacional, WG 2009, Montpellier, Francia, 24-26 de junio de 2009, Artículos revisados , Lecture Notes in Computer Science, vol. 5911, Berlín: Springer, pp. 238–249 , doi : 10.1007/978-3-642-11409-0_21 , ISBN 978-3-642-11408-3, MR 2587715 .
- ↑ Dean, Nathaniel; Latka, Brenda J. (1995), "Squaring the tournament—an open problem", Actas de la Vigésimo Sexta Conferencia Internacional del Sudeste sobre Combinatoria, Teoría de Grafos y Computación (Boca Ratón, FL, 1995), Congressus Numerantium , 109 : 73–80 , MR 1369296
- ^ Chen, Zhi-Zhong; Grigni, Miguel Ángel; Papadimitriou, Christos H. (2002), "Gráficos de mapas", Journal of the ACM , 49 (2): 127– 138, arXiv : cs/9910013 , doi : 10.1145/506147.506148 , MR 2147819 , S2CID 2657838 .
- ↑ Shpectorov, SV (1993), "Sobre incrustaciones a escala de grafos en hipercubos", European Journal of Combinatorics , 14 (2): 117–130 , doi : 10.1006/eujc.1993.1016 , MR 1206617 .
- ↑ Nishimura, N.; Ragde, P.; Thilikos, DM (2002), "Sobre potencias de grafos para árboles con etiquetas de hojas", Journal of Algorithms , 42 : 69–108 , doi : 10.1006/jagm.2001.1195.
- operaciones gráficas
