Potencia gráfica
Operación gráfica: vincular todos los pares de nodos con distancia ≤ k
El cuadrado de una gráfica

En 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 gráfico deben distinguirse de los productos de un gráfico consigo mismo, que (a diferencia de las potencias) generalmente tienen muchos más vértices que el gráfico original.

Propiedades

Si un grafo tiene diámetro d , entonces su potencia d -ésima es el grafo completo . [2] Si una familia de grafos tiene un ancho de camarilla acotado , entonces también lo tienen sus potencias d -ésimas para cualquier d fijo . [3]

Colorante

La coloración de gráficos en el cuadrado de un gráfico se puede utilizar para asignar frecuencias a los participantes de las redes de comunicación inalámbrica de modo 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 el límite de degeneración muestra que se puede utilizar 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 distintos 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 plano 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 gráfico es NP-difícil , incluso en el caso planar. [9]

Hamiltonicidad

El cubo de cada grafo conexo contiene necesariamente un ciclo hamiltoniano . [10] No es necesariamente el caso de que el cuadrado de un grafo conexo sea hamiltoniano, y es NP-completo determinar si el cuadrado es hamiltoniano. [11] Sin embargo, por 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 un tiempo O ( mn ) realizando una búsqueda en amplitud comenzando desde 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 grafo, modificada para tener entradas distintas de cero en su diagonal principal, entonces las entradas distintas de cero de Ak dan la matriz de adyacencia de la k -ésima potencia del grafo, [14] de lo que 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 -ésimas de los árboles se pueden reconocer en el tiempo lineal en el tamaño del gráfico 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]

Subgrafos inducidos

K 4 como el medio cuadrado de un gráfico cúbico

El semicuadrado de un grafo bipartito G es el subgrafo de G 2 inducido por un lado de la bipartición de G . Los grafos de mapa son los semicuadrados de los grafos planares , [18] y los grafos cúbicos reducidos a la mitad son los semicuadrados de los grafos de hipercubo . [19]

Las potencias de hojas son los subgrafos de las potencias de los árboles inducidas por las hojas del árbol. Una potencia de k hojas es una potencia de hojas cuyo exponente es k . [20]

Referencias

  1. ^ Bondy, Adrian; Murty, USR (2008), Teoría de grafos, Textos de posgrado en matemáticas, vol. 244, Springer, pág. 82, ISBN 9781846289699.
  2. ^ Weisstein, Eric W. , "Potencia gráfica", MathWorld
  3. ^ Todinca, Ioan (2003), "Coloración de potencias de grafos de ancho de camarilla acotado", 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, MR  2080095.
  4. ^ ab 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. 654-662{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
  5. ^ Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E. ; Woeginger, G. (1993), "Dibujo de gráficos en el plano con alta resolución", SIAM Journal on Computing , 22 (5): 1035–1052, doi :10.1137/0222063, MR  1237161.
  6. ^ Kramer, Florica; Kramer, Horst (2008), "Un estudio sobre la coloración de distancias de gráficos", Discrete Mathematics , 308 (2–3): 422–426, doi : 10.1016/j.disc.2006.11.059 , MR  2378044.
  7. ^ 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.
  8. ^ Alon, Noga ; Mohar, Bojan (2002), "El número cromático de potencias gráficas", Combinatorics, Probability and Computing , 11 (1): 1–10, doi :10.1017/S0963548301004965, MR  1888178, S2CID  2706926.
  9. ^ 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 planares de Ramanathan y Lloyd (1992, 1993).
  10. ^ Bondy y Murty (2008), pág. 105.
  11. ^ Underground, Polly (1978), "Sobre gráficos con cuadrados hamiltonianos", Matemáticas discretas , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR  0522906.
  12. ^ Diestel, Reinhard (2012), "10. Ciclos hamiltonianos", Teoría de grafos (PDF) (4.ª edición electrónica corregida).
  13. ^ Chan, Timothy M. (2012), "Caminos más cortos de todos los pares para gráficos no ponderados y no dirigidos en el tiempo", ACM Transactions on Algorithms , 8 (4): A34:1–A34:17, doi :10.1145/2344422.2344424, MR  2981912, S2CID  1212001 o ( metro norte ) {\displaystyle o(mn)}
  14. ^ 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ág. 94, ISBN 9781439813058.
  15. ^ 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, S2CID  253971732.
  16. ^ Motwani, R.; Sudan, M. (1994), "Calcular raíces de grafos es difícil", Discrete Applied Mathematics , 54 : 81–88, doi : 10.1016/0166-218x(94)00023-9.
  17. ^ Le, Van Bang; Nguyen, Ngoc Tuy (2010), "Resultados de dureza y algoritmos eficientes para potencias de grafos", Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, Francia, 24-26 de junio de 2009, Documentos revisados , Lecture Notes in Computer Science, vol. 5911, Berlín: Springer, págs. 238-249, doi :10.1007/978-3-642-11409-0_21, ISBN 978-3-642-11408-3, Sr.  2587715.
  18. ^ 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.
  19. ^ Shpectorov, SV (1993), "Incorporaciones a escala de gráficos en hipercubos", European Journal of Combinatorics , 14 (2): 117–130, doi : 10.1006/eujc.1993.1016 , MR  1206617.
  20. ^ Nishimura, N.; Ragde, P.; Thilikos, DM (2002), "Sobre potencias gráficas para árboles con hojas etiquetadas", Journal of Algorithms , 42 : 69–108, doi :10.1006/jagm.2001.1195.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Potencia_gráfica&oldid=1235225666"