Grado de conteo

El grado k (escrito G k ) de un grafo no dirigido G es otro grafo que tiene el mismo conjunto de vértices y dos vértices de este grafo son adyacentes si la distancia entre estos vértices en el grafo original G no excede k . Para indicar el grado de un gráfico, se usa una terminología similar a las potencias de los números: G 2 se llama el cuadrado del gráfico G , G 3 se llama el cubo [1] .

El grado de un gráfico no debe confundirse con la multiplicación de un gráfico por sí mismo, que (a diferencia del grado de un gráfico) generalmente tiene muchos más vértices que el gráfico original.

Propiedades

Si el diámetro de un gráfico es d , entonces su grado d -ésimo es un gráfico completo [2] . Si una familia de grafos tiene un ancho de camarilla acotado , entonces lo mismo es cierto para las d -ésimas potencias de los grafos de la familia para cualquier d fija [3] .

Dibujo para colorear

La coloración de cuadrados de gráficos se puede utilizar para asignar frecuencias a los miembros de la red inalámbrica de tal manera que no haya dos miembros que interfieran entre sí y con otros vecinos comunes [4] , así como para encontrar una representación gráfica de gráficos con alta resolución angular [5 ] .

Tanto el número cromático como la degeneración del k-ésimo grado de un gráfico plano con un grado de vértice máximo Δ son iguales a , donde el límite de degeneración muestra que se puede usar el algoritmo de coloración codicioso para colorear el gráfico con ese número de colores [4] . Para el caso de un grafo planar cuadrado, Wegner conjeturó en 1977 que el número cromático de tal grafo no excede , y actualmente se sabe que el número cromático no excede [6] [7] . De manera más general, para cualquier gráfico con degeneración d y grado máximo Δ, la degeneración cuadrada del gráfico es O ( d Δ ), por lo que muchos tipos de gráficos dispersos , distintos de los gráficos planos, también tienen un número cromático cuadrado proporcional a Δ.

Aunque el número cromático de un 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 con gran circunferencia y está limitado a O(Δ 2 /log Δ) [8] en este caso

El problema de determinar el número mínimo de colores para colorear un gráfico cuadrado es NP-difícil incluso para el caso plano [9]

hamiltoniano

El cubo de cualquier gráfico conexo contiene necesariamente un ciclo hamiltoniano [10] . El cuadrado de un gráfico conexo no necesariamente contendrá un ciclo hamiltoniano, y el problema de determinar que dicho ciclo está contenido en un cuadrado es NP-completo [11] . Sin embargo, según el teorema de Fleischner , el cuadrado de un grafo conectado por 2 vértices siempre es hamiltoniano [12] .

Complejidad computacional

El grado k de un gráfico con n vértices y m aristas se puede obtener en un tiempo O( mn ) aplicando la búsqueda en amplitud , que se realiza en cada vértice del gráfico para encontrar las distancias a todos los demás vértices. Alternativamente, si A es la matriz de adyacencia del gráfico modificada de tal manera que no hay elementos cero en la diagonal principal, entonces los elementos distintos de cero de la matriz A k dan la matriz de adyacencia del grado k -ésimo de la gráfico [13] , lo que implica que la construcción del k -ésimo grado del gráfico puede realizarse en un tiempo igual, hasta un factor logarítmico, al tiempo de multiplicación de matrices .

Dado un gráfico, determinar si es un cuadrado de otro gráfico es un problema NP-completo [14] . Además, es un problema NP-completo determinar si una gráfica es la k- ésima potencia de otra gráfica para cualquier número k  ≥ 2, y también si es la k- ésima potencia de una gráfica bipartita para k  > 2 [15] .

Subgrafos generados

Un semicuadrado de un grafo bipartito G es un subgrafo del grafo G 2 generado por una parte del grafo G . Los gráficos de mapa son ​​semicuadrados de gráficos planos [16] , los gráficos de cubo reducido a la mitad son ​​semicuadrados de gráficos de hipercubo [17] .

Los grados de hojas son ​​subgrafos de grados de árboles generados por hojas de árboles [18] .

Notas

  1. ↑ Bondy, Murty, 2008 , pág. 82.
  2. ↑ Weisstein, Eric W. Graph Power  en el sitio web de Wolfram MathWorld .
  3. ↑ Todinca, 2003 , p. 370–382.
  4. ↑ 1 2 Agnarsson, Halldorsson, 2000 , p. 654–662.
  5. ↑ Formann, Hagerup, Haralambides et al., 1993 , p. 1035–1052.
  6. ↑ F. y H. Kramer, 2008 , pág. 422–426.
  7. ↑ Molloy, Salavatipour, 2005 , pág. 189–213.
  8. ↑ Alon, Mohar, 2002 , pág. 1–10.
  9. ↑ Agnarsson y Halldórsson ( Agnarsson, Halldórsson 2000 ) enumeran en su publicación pruebas en papel de dureza NP para el caso de gráficos generales (artículos de McCormick (1983) y artículos de Lin y Skiena (Lin, Skiena, 1995)), y para gráficos planos (artículos de Ramanathan y Lloyd (Ramanathan, Lloyd, 1992-1993)).
  10. ↑ Bondy, Murty, 2008 , pág. 105.
  11. ↑ Subterráneo, 1978 , p. 323.
  12. ↑ Diéstel, 2012 .
  13. ↑ Hammack, Imrich, Klavžar, 2011 .
  14. ↑ Motwani, Sudán, 1994 , p. 81-88.
  15. ↑ Le, Nguyen, 2010 , pág. 238–249.
  16. ↑ Chen, Grigni, Papadimitriou, 2002 , pág. 127–138.
  17. ↑ Shpektorov, 1993 .
  18. ↑ Nishimura, Ragde, Thilikos, 2002 , pág. 69–108.

Literatura