Poder gráfico - Graph power
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 . 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.
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 . Si una familia de grafos tiene un ancho de camarilla acotado , entonces también lo tienen sus d -ésimas potencias para cualquier d fijo .
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 de modo que dos participantes no interfieran entre sí en ninguno de sus vecinos comunes y para encontrar dibujos de gráficos con alta resolución angular .
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 usar un algoritmo de coloración codicioso para colorear el gráfico con tantos colores. 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 . 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 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.
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.
Hamiltonicidad
El cubo de cada gráfico conectado contiene necesariamente un ciclo hamiltoniano . 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. Sin embargo, según el teorema de Fleischner , el cuadrado de un gráfico conectado a dos vértices es siempre hamiltoniano.
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. Alternativamente, si A es una matriz de adyacencia para la gráfica, 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 de la gráfica, de la cual se sigue que la construcción de k- ésima las potencias se pueden 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.
Dado un gráfico, decidir si es el cuadrado de otro gráfico es NP-completo . 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.
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 y los gráficos de cubo divididos por la mitad son los medios cuadrados de los gráficos de hipercubo .
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 .