En la teoría de grafos , un gráfico perfectamente ordenable es un gráfico cuyos vértices se pueden ordenar de tal manera que un algoritmo de coloración codicioso con ese orden colorea de manera óptima cada subgrafo inducido del gráfico dado. Perfectamente gráficos que pueden pedirse forman un caso especial de los gráficos perfectos , y que incluyen los gráficos de cuerdas , gráficos de comparabilidad , y gráficos de distancia hereditaria . Sin embargo, probar si un gráfico es perfectamente ordenable es NP-completo .
El algoritmo de coloración codicioso, cuando se aplica a un orden dado de los vértices de un gráfico G , considera los vértices del gráfico 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 ordenaciones de vértices pueden llevar a este algoritmo a utilizar diferentes números de colores. Siempre hay un orden que conduce a una coloración óptima; esto es cierto, por ejemplo, para la ordenación determinada a partir de una coloración óptima al ordenar los vértices por su color, pero puede ser difícil de encontrar. Los gráficos perfectamente ordenables se definen como los gráficos para los que existe un orden óptimo para el algoritmo codicioso, no solo para el gráfico en sí, sino para todos sus subgrafos inducidos..
Más formalmente, se dice que un gráfico G es perfectamente ordenable si existe un orden π de los vértices de G , de modo que cada subgrafo inducido de G es coloreado de manera óptima por el algoritmo codicioso usando la subsecuencia de π inducida por los vértices del subgrafo. . Un ordenamiento π tiene esta propiedad exactamente cuando no existen cuatro vértices de un , b , c , y d para el cual abcd es un camino inducida, un aparece antes de b en la ordenación, y c aparece después de d en la ordenación. [1]
Las gráficas perfectamente ordenables son NP-completas de reconocer. [2] Sin embargo, es fácil probar si un orden en particular es un orden perfecto de un gráfico. En consecuencia, también es NP-difícil encontrar un orden perfecto de un gráfico, incluso si ya se sabe que el gráfico es perfectamente ordenable.
Los gráficos de cuerdas se pueden ordenar perfectamente; se puede encontrar un orden perfecto de un gráfico de cuerdas invirtiendo un orden de eliminación perfecto para el gráfico. Por lo tanto, la aplicación de colores codiciosos a un orden perfecto proporciona un algoritmo eficiente para colorear gráficos de cuerdas de manera óptima. Los gráficos de comparabilidad también se pueden ordenar perfectamente, con un orden perfecto dado por un ordenamiento topológico de una orientación transitiva del gráfico. [1] Los gráficos de complemento de los gráficos de tolerancia se pueden ordenar perfectamente. [3]
Otra clase de gráficas perfectamente ordenables viene dada por las gráficas G tales que, en cada subconjunto de cinco vértices de G , al menos uno de los cinco tiene una vecindad cerrada que es un subconjunto de (o igual a) la vecindad cerrada de otro de los cinco vértices. De manera equivalente, estos son los gráficos en los que el orden parcial de los vecindarios cerrados, ordenados por inclusión de conjuntos, tiene un ancho como máximo de cuatro. El gráfico de ciclo de 5 vértices tiene un orden parcial de vecindad de ancho cinco, por lo que cuatro es el ancho máximo que asegura una ordenabilidad perfecta. Al igual que con los gráficos cordales (y a diferencia de los gráficos perfectamente ordenables de manera más general), los gráficos con un ancho de cuatro son reconocibles en tiempo polinomial.[4]