En la 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 . Gráficos de comparabilidad también se han llamado gráficos transitivamente orientables , parcialmente gráficos que pueden pedirse , gráficos de contención , [1] y gráficos divisor . [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 .
Definiciones y caracterización
Para cualquier conjunto estricto parcialmente ordenado ( S , <), la gráfica de comparabilidad de ( S , <) es la gráfica ( S , ⊥) cuyos vértices son los elementos de S y las aristas son esos 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) de modo que la relación de adyacencia del gráfico dirigido resultante es transitiva : siempre que haya existen aristas dirigidas ( x , y ) e ( 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 ax es un subconjunto del conjunto correspondiente ay . De esta forma, 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 un borde 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 manera que x < y siempre que el número entero correspondiente ax es un divisor del número entero correspondiente ay . Debido a esta construcción, las gráficas de comparabilidad también se han denominado gráficas de divisores. [2]
Los gráficos de comparabilidad se pueden caracterizar como los gráficos tales que, para cada ciclo generalizado de longitud impar, se puede encontrar una arista ( x , y ) que conecta dos vértices que están a una distancia dos en el ciclo. Tal borde se llama cuerda triangular . En este contexto, un ciclo generalizado se define como un paseo 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]
Relación con otras familias de gráficos
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. Cada gráfico bipartito es también un gráfico de comparabilidad. La orientación de 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 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 . Las gráficas de intervalo 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 gráficos de comparabilidad.
Los gráficos trivialmente perfectos son los gráficos de comparabilidad de árboles enraizados . [9] Los cografos se pueden caracterizar como los gráficos de comparabilidad de órdenes parciales en serie-paralelo ; por lo 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 los gráficos 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 de la gráfica perfecta, 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 cada gráfico de comparabilidad es un gráfico de cadena . [13]
Algoritmos
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 las gráficas de comparabilidad son perfectas, muchos problemas que son difíciles en clases de gráficas más generales, incluido el color de las gráficas y el problema de conjuntos independientes , se pueden calcular en tiempo polinómico para gráficas de comparabilidad.
Notas
- ^ Golumbic (1980) , p. 105; Brandstädt, Le y Spinrad (1999) , pág. 94.
- ^ a b Chartrand y col. (2001) .
- ↑ Ghouila-Houri (1962) ; véase Brandstädt, Le & Spinrad (1999) , teorema 1.4.1, p. 12. Si bien las orientaciones provenientes de órdenes parciales son acíclicas , no es necesario incluir la aciclicidad como condición de esta caracterización.
- ^ Urrutia (1989) ; Trotter (1992) ; Brandstädt, Le & Spinrad (1999) , sección 6.3, págs. 94–96.
- ^ Ghouila-Houri (1962) y Gilmore y Hoffman (1964) . Véase también Brandstädt, Le & Spinrad (1999) , teorema 6.1.1, p. 91.
- ^ Gallai (1967) ; Trotter (1992) ; Brandstädt, Le y Spinrad (1999) , pág. 91 y p. 112.
- ^ Ghouila-Houri (1962) demostró la orientabilidad transitiva de los complementos de los gráficos de intervalo; la caracterización de los gráficos de intervalo se debe a Gilmore y Hoffman (1964) . Véase también Golumbic (1980) , prop. 1.3, págs. 15-16.
- ^ Dushnik y Miller (1941) . Brandstädt, Le & Spinrad (1999) , teorema 6.3.1, p. 95.
- ^ Brandstädt, Le & Spinrad (1999) , teorema 6.6.1, p. 99.
- ^ Brandstädt, Le & Spinrad (1999) , corolario 6.4.1, p. 96; Jung (1978) .
- ^ Golumbic (1980) , teoremas 5.34 y 5.35, p. 133.
- ^ Maffray (2003) .
- ^ Golumbic, Rotem & Urrutia (1983) y Lovász (1983) . Véase también Fox y Pach (2012) .
- ^ McConnell y Spinrad (1997) ; véase Brandstädt, Le & Spinrad (1999) , p. 91.
Referencias
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
- Chartrand, Gary ; Muntean, Raluca; Saenpholphat, Varaporn; Zhang, Ping (2001), "Which graphs are divisor graphs?", Actas de la trigésima segunda Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Baton Rouge, LA, 2001), Congressus Numerantium , 151 : 189-200, Señor 1887439
- Dushnik, Ben; Miller, EW (1941), "Conjuntos ordenados parcialmente", American Journal of Mathematics , The Johns Hopkins University Press, 63 (3): 600–610, doi : 10.2307 / 2371374 , hdl : 10338.dmlcz / 100377 , JSTOR 2371374 , Señor 0004862.
- Fox, Jacob; Pach, Jànos (2012), "String graphs and incomparability graphs" (PDF) , Advances in Mathematics , 230 (3): 1381–1401, doi : 10.1016 / j.aim.2012.03.011.
- Gallai, Tibor (1967), "Transitiv orientierbare Graphen", Acta Math. Acad. Sci. Colgado. , 18 (1–2): 25–66, doi : 10.1007 / BF02020961 , MR 0221974 , S2CID 119485995.
- Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relationship d'ordre", Les Comptes rendus de l'Académie des sciences , 254 : 1370– 1371, MR 0172275.
- Gilmore, PC; Hoffman, AJ (1964), "Una caracterización de gráficos de comparabilidad y de gráficos de intervalo", Canadian Journal of Mathematics , 16 : 539–548, doi : 10.4153 / CJM-1964-055-5 , MR 0175811.
- Golumbic, Martin Charles (1980), Teoría algorítmica de gráficos y gráficos perfectos , Academic Press, ISBN 0-12-289260-7.
- Golumbic, M .; Rotem, D .; Urrutia, J. (1983), "Gráficos de comparabilidad y gráficos de intersección", Matemáticas discretas , 43 (1): 37–46, doi : 10.1016 / 0012-365X (83) 90019-5.
- Jung, HA (1978), "Sobre una clase de posets y los gráficos de comparabilidad correspondientes", Journal of Combinatorial Theory, Serie B , 24 (2): 125-133, doi : 10.1016 / 0095-8956 (78) 90013-8 , MR 0491356.
- Lovász, L. (1983), "Gráficos perfectos", Temas seleccionados en teoría de gráficos , 2 , Londres: Academic Press, págs. 55–87.
- Maffray, Frédéric (2003), "Sobre la coloración de gráficos perfectos", en Reed, Bruce A .; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics , CMS Books in Mathematics, 11 , Springer-Verlag, págs. 65–84, doi : 10.1007 / 0-387-22444-0_3.
- McConnell, RM; Spinrad, J. (1997), "Orientación transitiva en tiempo lineal", 8º Simposio ACM-SIAM sobre algoritmos discretos , págs. 19-25.
- Seymour, Paul (2006), "Cómo se encontró la prueba de la conjetura de gráfico perfecto fuerte" (PDF) , Gazette des Mathématiciens (109): 69–83, MR 2245898.
- Trotter, William T. (1992), Combinatoria y conjuntos parcialmente ordenados - Teoría de la dimensión , Johns Hopkins University Press.
- Urrutia, Jorge (1989), Rival, I. (ed.), Órdenes parciales y geometría euclidiana , Kluwer Academic Publishers, págs. 327–436 Parámetro desconocido
|book-title=
ignorado ( ayuda ) .