En 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 coloree de manera óptima cada subgrafo inducido del gráfico dado. Los gráficos perfectamente ordenables forman un caso especial de los gráficos perfectos e incluyen los gráficos cordales , los gráficos de comparabilidad y los gráficos hereditarios de distancia . Sin embargo, probar si un gráfico es perfectamente ordenable es NP-completo .
El algoritmo de coloración codiciosa, 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 ordenamientos de vértices pueden llevar a que este algoritmo utilice diferentes números de colores. Siempre hay un orden que conduce a una coloración óptima (esto es cierto, por ejemplo, en el caso del orden determinado a partir de una coloración óptima clasificando los vértices por su color), pero puede ser difícil de encontrar. Los gráficos perfectamente ordenables se definen como aquellos para los cuales 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 ordenamiento π de los vértices de G , tal que cada subgrafo inducido de G esté coloreado de manera óptima por el algoritmo codicioso 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 gráficos perfectamente ordenables son NP-completos para reconocer. [2] Sin embargo, es fácil probar si un orden 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.
Todo gráfico perfectamente ordenable es un gráfico perfecto . [1]
Los gráficos cordales se pueden ordenar perfectamente; Se puede encontrar un orden perfecto de un gráfico cordal invirtiendo un orden de eliminación perfecto para el gráfico. Por lo tanto, aplicar coloración voraz a un orden perfecto proporciona un algoritmo eficiente para colorear de manera óptima gráficos de cuerdas. Los gráficos de comparabilidad también se pueden ordenar perfectamente, y el ordenamiento perfecto viene 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 son perfectamente ordenables. [3]
Otra clase de gráficos perfectamente ordenables está dada por los gráficos 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 las vecindades cerradas, 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 garantiza una ordenabilidad perfecta. Al igual que con los gráficos cordales (y a diferencia de los gráficos perfectamente ordenables en general), los gráficos con ancho cuatro son reconocibles en tiempo polinomial. [4]
Un concepto intermedio entre el orden de eliminación perfecto de un grafo cordal y un orden perfecto es un orden de eliminación semiperfecto : en un orden de eliminación, no existe un camino inducido por tres vértices en el que el vértice medio sea el primero de los tres en ser eliminado. y en un orden de eliminación semiperfecto, no existe un camino inducido por cuatro vértices en el que uno de los dos vértices intermedios sea el primero en ser eliminado. Por lo tanto, el reverso de este orden satisface los requisitos de un orden perfecto, por lo que los gráficos con ordenamiento de eliminación semiperfecto son perfectamente ordenables. [5] En particular, el mismo algoritmo de búsqueda lexicográfica de amplitud primero utilizado para encontrar órdenes de eliminación perfectos de gráficos cordales se puede utilizar para encontrar órdenes de eliminación semiperfectos de gráficos hereditarios a distancia , que por lo tanto también son perfectamente ordenables. [6]
Los gráficos para los cuales el orden de cada vértice es un orden perfecto son los cografos . Debido a que los cografos son gráficos sin una ruta inducida por cuatro vértices, no pueden violar el requisito de ordenamiento de rutas en un orden perfecto.
Se conocen varias clases adicionales de gráficos perfectamente ordenables. [7]