Gráfico de comparabilidad

En teoría de grafos , un grafo de comparabilidad es un grafo no dirigido que conecta pares de elementos que son comparables entre sí en un orden parcial . Los grafos de comparabilidad también se han llamado grafos transitivamente orientables , grafos parcialmente ordenables , grafos de contención , ^[1] y grafos divisores . ^[2] Un grafo de incomparabilidad es un grafo no dirigido que conecta pares de elementos que no son comparables entre sí en un orden parcial .

Para cualquier conjunto parcialmente ordenado estricto ( S , <) , el grafo de comparabilidad de ( S , <) es el grafo ( S , ⊥) cuyos vértices son los elementos de S y las aristas son aquellos pares { u , v } de elementos tales que u < v . Es decir, para un conjunto parcialmente ordenado, tome el grafo acíclico dirigido , aplique el cierre transitivo y elimine la orientación.

De manera equivalente, un gráfico de comparabilidad es un gráfico que tiene una orientación transitiva , ^[3] una asignación de direcciones a los bordes del gráfico (es decir, una orientación del gráfico) tal que la relación de adyacencia del gráfico dirigido resultante es transitiva : siempre que existan bordes dirigidos ( x , y ) y ( y , z ) , debe existir un borde ( x , z ) .

Cualquier orden parcial finito se puede representar como una familia de conjuntos, de modo que x < y en el orden parcial siempre que el conjunto correspondiente a x sea un subconjunto del conjunto correspondiente a y . De esta manera, se puede demostrar que los grafos de comparabilidad son equivalentes a los grafos de contención de familias de conjuntos; es decir, un grafo con un vértice para cada conjunto de la familia y una arista entre dos conjuntos siempre que uno sea un subconjunto del otro. ^[4] Alternativamente, se puede representar el orden parcial mediante una familia de números enteros , de modo que x < y siempre que el número entero correspondiente a x sea un divisor del número entero correspondiente a y . Debido a esta construcción, los grafos de comparabilidad también se han denominado grafos divisores. ^[2]

Los grafos de comparabilidad pueden caracterizarse como los grafos tales que, para cada ciclo generalizado (ver abajo) de longitud impar, uno puede encontrar un borde ( x , y ) que conecta dos vértices que están a una distancia de dos en el ciclo. Tal borde se llama cuerda triangular . En este contexto, un ciclo generalizado se define como un paseo cerrado que usa cada borde del grafo como máximo una vez en cada dirección. ^[5] Los grafos de comparabilidad también pueden caracterizarse por una lista de subgrafos inducidos prohibidos . ^[6]

Todo grafo completo es un grafo de comparabilidad, el grafo de comparabilidad de un orden total . Todas las orientaciones acíclicas de un grafo completo son transitivas. Todo grafo bipartito es también un grafo de comparabilidad. Orientar los bordes de un grafo bipartito de un lado de la bipartición al otro da como resultado una orientación transitiva, correspondiente a un orden parcial de altura dos. Como observa Seymour (2006), todo grafo de comparabilidad que no sea ni completo ni bipartito tiene una partición sesgada .

El complemento de cualquier gráfico de intervalo es un gráfico de comparabilidad. La relación de comparabilidad se denomina orden de intervalo . Los gráficos de intervalo son exactamente los gráficos que son cordales y que tienen complementos de gráfico de comparabilidad. ^[7]

Un gráfico de permutación es un gráfico de contención en un conjunto de intervalos. ^[8] Por lo tanto, los gráficos de permutación son otra subclase de gráficos de comparabilidad.

Los grafos trivialmente perfectos son los grafos de comparabilidad de árboles enraizados . ^[9] Los cografos pueden caracterizarse como los grafos de comparabilidad de órdenes parciales serie-paralelo ; por lo tanto, los cografos también son grafos de comparabilidad. ^[10]

Los gráficos de umbral son otro tipo especial de gráfico de comparabilidad.

Todo grafo de comparabilidad es perfecto . La perfección de los grafos de comparabilidad es el teorema de Mirsky , y la perfección de sus complementos es el teorema de Dilworth ; estos hechos, junto con el teorema del grafo perfecto, se pueden utilizar para demostrar el teorema de Dilworth a partir del teorema de Mirsky o viceversa. ^[11] Más específicamente, los grafos de comparabilidad son grafos perfectamente ordenables , una subclase de grafos perfectos: un algoritmo de coloración voraz para un ordenamiento topológico de una orientación transitiva del grafo los coloreará de manera óptima. ^[12]

El complemento de cada gráfico de comparabilidad es un gráfico de cadenas . ^[13]

Una orientación transitiva de un gráfico, si existe, se puede encontrar en tiempo lineal. ^[14] Sin embargo, el algoritmo para hacerlo asignará orientaciones a los bordes de cualquier gráfico, por lo que para completar la tarea de probar si un gráfico es un gráfico de comparabilidad, uno debe probar si la orientación resultante es transitiva, un problema demostrablemente equivalente en complejidad a la multiplicación de matrices .

Debido a que los gráficos de comparabilidad son perfectos, muchos problemas que son difíciles para clases más generales de gráficos, incluida la coloración de gráficos y el problema del conjunto independiente , se pueden resolver en tiempo polinomial para gráficos de comparabilidad.

• Gráfico acotado , un gráfico diferente definido a partir de un orden parcial