En teoría de grafos , un grafo perfectamente ordenable es un grafo cuyos vértices se pueden ordenar de tal manera que un algoritmo de coloración voraz con ese ordenamiento colorea de manera óptima cada subgrafo inducido del grafo dado. Los grafos perfectamente ordenables forman un caso especial de los grafos perfectos e incluyen los grafos cordales , los grafos de comparabilidad y los grafos de distancia-hereditarios . Sin embargo, comprobar si un grafo es perfectamente ordenable es NP-completo .
El algoritmo de coloración voraz, cuando se aplica a un ordenamiento dado de los vértices de un grafo G , considera los vértices del grafo en secuencia y asigna a cada vértice su primer color disponible, el valor mínimo excluido para el conjunto de colores utilizados por sus vecinos. Diferentes ordenamientos de vértices pueden llevar a este algoritmo a utilizar diferentes cantidades de colores. Siempre hay un ordenamiento que conduce a un coloreado óptimo –esto es cierto, por ejemplo, del ordenamiento determinado a partir de un coloreado óptimo al ordenar los vértices por su color– pero puede ser difícil de encontrar. Los grafos perfectamente ordenables se definen como los grafos para los cuales hay un ordenamiento que es óptimo para el algoritmo voraz no solo para el grafo en sí, sino para todos sus subgrafos inducidos .
Más formalmente, se dice que un grafo G es perfectamente ordenable si existe un ordenamiento π de los vértices de G , tal que cada subgrafo inducido de G es coloreado óptimamente por el algoritmo voraz que utiliza la subsecuencia de π inducida por los vértices del subgrafo. Un ordenamiento π tiene esta propiedad exactamente cuando no existen cuatro vértices a , b , c y d para los cuales abcd es un camino inducido, a aparece antes de b en el ordenamiento y c aparece después de d en el ordenamiento. [1]
Los grafos perfectamente ordenables son NP-completos de reconocer. [2] Sin embargo, es fácil comprobar si un orden particular es un orden perfecto de un grafo. En consecuencia, también es NP-difícil encontrar un orden perfecto de un grafo, incluso si ya se sabe que el grafo es perfectamente ordenable.
Todo gráfico perfectamente ordenable es un gráfico perfecto . [1]
Los grafos cordales son perfectamente ordenables; un orden perfecto de un grafo cordal se puede encontrar invirtiendo un orden de eliminación perfecto para el grafo. Por lo tanto, la aplicación de coloración voraz a un orden perfecto proporciona un algoritmo eficiente para colorear de manera óptima los grafos cordales. Los grafos de comparabilidad también son perfectamente ordenables, y un orden perfecto se da mediante un ordenamiento topológico de una orientación transitiva del grafo. [1] Los grafos complementarios de los grafos de tolerancia son perfectamente ordenables. [3]
Otra clase de grafos perfectamente ordenables está dada por los grafos G tales que, en cada subconjunto de cinco vértices de G , al menos uno de los cinco tiene un entorno cerrado que es un subconjunto de (o igual a) el entorno cerrado de otro de los cinco vértices. Equivalentemente, estos son los grafos en los que el orden parcial de los entornos cerrados, ordenados por inclusión de conjuntos, tiene un ancho de como máximo cuatro. El grafo de ciclo de 5 vértices tiene un orden parcial de entorno de ancho cinco, por lo que cuatro es el ancho máximo que asegura una ordenabilidad perfecta. Al igual que con los grafos cordales (y a diferencia de los grafos perfectamente ordenables de manera más general), los grafos con ancho cuatro son reconocibles en tiempo polinomial. [4]
Un concepto intermedio entre el ordenamiento de eliminación perfecto de un grafo cordal y un ordenamiento perfecto es un ordenamiento de eliminación semiperfecto : en un ordenamiento de eliminación, no hay un camino inducido por tres vértices en el que el vértice del medio sea el primero de los tres en eliminarse, y en un ordenamiento de eliminación semiperfecto, no hay un camino inducido por cuatro vértices en el que uno de los dos vértices del medio sea el primero en eliminarse. Por lo tanto, el inverso de este ordenamiento satisface los requisitos de un ordenamiento perfecto, por lo que los grafos con ordenamientos de eliminación semiperfectos son perfectamente ordenables. [5] En particular, el mismo algoritmo de búsqueda lexicográfica en amplitud utilizado para encontrar órdenes de eliminación perfectos de grafos cordales se puede utilizar para encontrar órdenes de eliminación semiperfectos de grafos hereditarios de distancia , que, por lo tanto, también son perfectamente ordenables. [6]
Los grafos para los cuales cada orden de vértices es un orden perfecto son los cografos . Debido a que los cografos son los grafos sin una trayectoria inducida por cuatro vértices, no pueden violar el requisito de orden de trayectoria en una ordenación perfecta.
Se conocen varias clases adicionales de gráficos perfectamente ordenables. [7]