En teoría de grafos , un gráfico de comparabilidad es un gráfico no dirigido que conecta pares de elementos que son comparables entre sí en un orden parcial . Los gráficos de comparabilidad también han sido llamados gráficos transitivamente orientables , gráficos parcialmente ordenables , gráficos de contención , [1] y gráficos de divisores . [2] Un gráfico de incomparabilidad es un gráfico no dirigido que conecta pares de elementos que no son comparables entre sí en un orden parcial .
Para cualquier conjunto estricto parcialmente ordenado ( S ,<) , el gráfico de comparabilidad de ( S , <) es el gráfico ( S , ⊥ ) del cual los 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 gráfico acíclico dirigido , aplique 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 haya Si existen aristas dirigidas ( x , y ) y ( y , z ) , debe existir una arista ( x , z ) .
Se puede representar cualquier orden parcial finito 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 gráficos de comparabilidad son equivalentes a los gráficos de contención de familias de conjuntos; es decir, un gráfico 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 , tal que x < y siempre que el número entero correspondiente a x sea divisor del número entero correspondiente a y . Debido a esta construcción, las gráficas de comparabilidad también se denominan gráficas de divisores. [2]
Los gráficos de comparabilidad se pueden caracterizar como gráficos tales que, para cada ciclo generalizado (ver más abajo) de longitud impar, se puede encontrar un borde ( x , y ) que conecta dos vértices que están a una distancia dos en el ciclo. Tal arista se llama cuerda triangular . En este contexto, un ciclo generalizado se define como un recorrido cerrado que utiliza cada borde del gráfico como máximo una vez en cada dirección. [5] Los gráficos de comparabilidad también se pueden caracterizar por una lista de subgrafos inducidos prohibidos . [6]
Cada gráfico completo es un gráfico de comparabilidad, el gráfico de comparabilidad de un pedido total . Todas las orientaciones acíclicas de un gráfico completo son transitivas. Todo gráfico bipartito es también un gráfico de comparabilidad. Orientar los bordes de un gráfico 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 gráfico de comparabilidad que no sea 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 llama orden de intervalo . Las gráficas de intervalos son exactamente las gráficas que son cordales y que tienen complementos de gráficas 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 los gráficos de comparabilidad.
Las gráficas trivialmente perfectas son las gráficas de comparabilidad de árboles enraizados . [9] Los cografos se pueden caracterizar como gráficos de comparabilidad de órdenes parciales en series paralelas ; por tanto, las cografías también son gráficas de comparabilidad. [10]
Los gráficos de umbral son otro tipo especial de gráfico de comparabilidad.
Cada gráfico de comparabilidad es perfecto . La perfección de las gráficas 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 gráficos de comparabilidad son gráficos perfectamente ordenables , una subclase de gráficos perfectos: un algoritmo de coloración codicioso para un ordenamiento topológico de una orientación transitiva del gráfico los coloreará de manera óptima. [12]
El complemento de todo 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 en clases de gráficos más generales, incluida la coloración de gráficos y el problema de conjuntos independientes , se pueden resolver en tiempo polinomial para gráficos de comparabilidad.