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 . Se hace referencia a las potencias de las gráficas utilizando una terminología similar a la de 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 gráficas deben distinguirse de los productos de una gráfica consigo misma, que (a diferencia de las potencias) generalmente tienen muchos más vértices que la gráfica original.
Propiedades
Si una gráfica tiene un diámetro d , entonces su d -ésima potencia es la gráfica completa . [2] Si una familia de grafos tiene un ancho de camarilla acotado , entonces también lo tienen sus d -ésimas potencias para cualquier d fijo . [3]
Colorante
La coloración del gráfico en el cuadrado de un gráfico se puede utilizar para asignar frecuencias a los participantes de las redes de comunicación inalámbrica para que dos participantes no interfieran 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 gráfico plano de grado máximo Δ son, donde el límite de degeneración muestra que se puede utilizar un algoritmo de coloración codicioso para colorear el gráfico con tantos colores. [4] Para el caso especial de un cuadrado de un gráfico plano, Wegner conjeturó en 1977 que el número cromático del cuadrado de un gráfico plano es como máximo, y se sabe que el número cromático es como máximo . [6] [7] De manera más general, para cualquier gráfico con degeneración d y grado máximo Δ, la degeneración del cuadrado del gráfico es O ( d Δ), por lo que muchos tipos de gráficos dispersos distintos de los gráficos planos también tienen cuadrados cuyo el número cromático es proporcional a Δ.
Aunque el número cromático del cuadrado de un gráfico no plano con grado máximo Δ puede ser proporcional a Δ 2 en el peor de los casos, es menor para gráficos de gran circunferencia , estando delimitado por O (Δ 2 / log Δ) en este caso. [8]
Determinar el número mínimo de colores necesarios para colorear el cuadrado de un gráfico es NP-difícil , incluso en el caso plano. [9]
Hamiltonicidad
El cubo de cada gráfico conectado contiene necesariamente un ciclo hamiltoniano . [10] No es necesariamente el caso de que el cuadrado de una gráfica conectada sea hamiltoniano, y es NP-completo determinar si el cuadrado es hamiltoniano. [11] Sin embargo, según el teorema de Fleischner , el cuadrado de un gráfico conectado a 2 vértices es siempre hamiltoniano. [12]
Complejidad computacional
La k- ésima potencia de un gráfico con n vértices y m aristas puede calcularse en el tiempo O ( mn ) realizando una primera búsqueda de amplitud a partir de cada vértice para determinar las distancias a todos los demás vértices, o un poco más rápido utilizando algoritmos más sofisticados. [13] Alternativamente, si A es una matriz de adyacencia para el gráfico, modificada para tener entradas distintas de cero en su diagonal principal, entonces las entradas distintas de cero de A k dan la matriz de adyacencia de la k- ésima potencia del gráfico, [14] a partir de la 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 k- ésimas potencias de los árboles se pueden reconocer en el tiempo lineal en el tamaño del gráfico de entrada. [15]
Dado un gráfico, decidir si es el cuadrado de otro gráfico es NP-completo . [16] Además, es NP-completo determinar si una gráfica es una k- ésima potencia de otra gráfica, para un número dado k ≥ 2, o si es una k- ésima potencia de una gráfica bipartita , para k > 2. [17]
Subgrafos inducidos
El medio-cuadrado de un gráfico bipartito G es el subgrafo de G 2 inducida por un lado de la bipartición de G . Los gráficos de mapa son los medios cuadrados de los gráficos planos , [18] y los gráficos de cubo a la mitad son los medios cuadrados de los gráficos de hipercubo . [19]
Los poderes de las hojas son los subgrafos de los poderes de los árboles inducidos por las hojas del árbol. Una potencia de hoja k es una potencia de hoja cuyo exponente es k . [20]
Referencias
- ↑ Bondy, Adrian; Murty, USR (2008), Teoría de grafos , Textos de posgrado en matemáticas, 244 , Springer, p. 82, ISBN 9781846289699.
- ^ Weisstein, Eric W. "Graph Power" . MathWorld .
- ^ Todinca, Ioan (2003), "Los poderes de coloración de gráficos de ancho de camarilla acotado", Conceptos teóricos de gráficos en informática , Lecture Notes in Comput. Sci., 2880 , Springer, Berlín, págs. 370–382, doi : 10.1007 / 978-3-540-39890-5_32 , MR 2080095.
- ^ a b Agnarsson, Geir; Halldórsson, Magnús M. (2000), "Los poderes de coloración de los gráficos planos", Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos (SODA '00) , San Francisco, California, EE. UU., Págs. 654–662.
- ^ Formann, M .; Hagerup, T .; Haralambides, J .; Kaufmann, M .; Leighton, FT ; Symvonis, A .; Welzl, E .; Woeginger, G. (1993), "Dibujar gráficos en el plano con alta resolución", SIAM Journal on Computing , 22 (5): 1035–1052, doi : 10.1137 / 0222063 , MR 1237161.
- ^ Kramer, Florica; Kramer, Horst (2008), "Una encuesta sobre la coloración a distancia de los gráficos", Matemáticas discretas , 308 (2–3): 422–426, doi : 10.1016 / j.disc.2006.11.059 , MR 2378044.
- ^ Molloy, Michael; Salavatipour, Mohammad R. (2005), "Un límite en el número cromático del cuadrado de un gráfico plano", 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 gráficas", Combinatoria, probabilidad y computación , 11 (1): 1–10, doi : 10.1017 / S0963548301004965 , MR 1888178.
- ↑ Agnarsson y Halldórsson (2000) enumeran publicaciones que prueban la dureza NP para gráficos generales de McCormick (1983) y Lin y Skiena (1995), y para gráficos planos de Ramanathan y Lloyd (1992, 1993).
- ^ Bondy y Murty (2008) , p. 105.
- ^ Underground, Polly (1978), "Sobre gráficas 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), "Todos los pares de caminos más cortos para gráficos no ponderados no dirigidos en time ", ACM Transactions on Algorithms , 8 (4): A34: 1 – A34: 17, doi : 10.1145 / 2344422.2344424 , MR 2981912
- ^ Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi (2011), Manual de gráficos de productos , Matemáticas discretas y sus aplicaciones (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íces de árboles", Algorithmica , 71 (2): 471–495, doi : 10.1007 / s00453-013-9815-y.
- ^ Motwani, R .; Sudán, M. (1994), "Calcular raíces de gráficos 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 gráficos", Conceptos teóricos de gráficos en informática: 35th International Workshop, WG 2009, Montpellier, Francia, 24-26 de junio de 2009, Revised Papers , Lecture Notes en Ciencias de la Computación, 5911 , Berlín: Springer, págs. 238–249, doi : 10.1007 / 978-3-642-11409-0_21 , ISBN 978-3-642-11408-3, MR 2587715.
- ^ Chen, Zhi-Zhong; Grigni, Miguel Ángel; Papadimitriou, Christos H. (2002), "Gráficos de mapa", Journal of the ACM , 49 (2): 127-138, arXiv : cs / 9910013 , doi : 10.1145 / 506147.506148 , MR 2147819.
- ^ Shpectorov, SV (1993), "Incrustaciones a escala de gráficos 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 gráficas para árboles etiquetados con hojas", Journal of Algorithms , 42 : 69–108, doi : 10.1006 / jagm.2001.1195.