De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Construcción de un gráfico trivialmente perfecto a partir de intervalos anidados y de la relación de accesibilidad en un árbol.

En teoría de grafos , un grafo trivialmente perfecto es un grafo con la propiedad de que en cada uno de sus subgrafos inducidos el tamaño del conjunto máximo independiente es igual al número de camarillas máximas . [1] Los gráficos trivialmente perfectos fueron estudiados por primera vez por (Wolk  1962 , 1965 ) pero fueron nombrados por Golumbic (1978) ; Golumbic escribe que "se eligió el nombre porque es trivial demostrar que tal gráfico es perfecto ". Los gráficos trivialmente perfectos también se conocen como gráficos de comparabilidad de árboles , [2] gráficos de comparabilidad arborescentes , [3]y gráficos de cuasi-umbral . [4]

Caracterizaciones equivalentes [ editar ]

Los gráficos trivialmente perfectos tienen otras caracterizaciones equivalentes:

  • Son las gráficas de comparabilidad de árboles teóricos de órdenes . Es decir, sea T un orden parcial tal que para cada t ∈ T , el conjunto { s ∈ T  : s < t } esté bien ordenado por la relación <, y también T posea un elemento mínimo r . Entonces, el gráfico de comparabilidad de T es trivialmente perfecto, y todo gráfico trivialmente perfecto puede formarse de esta manera. [5]
  • Son los gráficos que no tienen un gráfico de trayectoria P 4 o un gráfico de ciclo C 4 como subgráficos inducidos . [6]
  • Son los gráficos en los que cada subgrafo inducido conectado contiene un vértice universal . [7]
  • Son los gráficos que se pueden representar como gráficos de intervalo para un conjunto de intervalos anidados . Un conjunto de intervalos está anidado si, por cada dos intervalos del conjunto, los dos están separados o uno contiene al otro. [8]
  • Son las gráficas que son tanto cordales como cográficas . [9] Esto se desprende de la caracterización de los grafos cordales como los grafos sin ciclos inducidos de longitud mayor a tres, y de los cografos como los grafos sin trayectorias inducidas en cuatro vértices ( P 4 ).
  • Son las gráficas que son a la vez cográficas y gráficas de intervalo. [9]
  • Son los gráficos que se pueden formar, a partir de gráficos de un vértice, mediante dos operaciones: unión disjunta de dos gráficos trivialmente perfectos más pequeños y la adición de un nuevo vértice adyacente a todos los vértices de un gráfico trivialmente perfecto más pequeño. [10] Estas operaciones corresponden, en el bosque subyacente, a formar un nuevo bosque por la unión disjunta de dos bosques más pequeños y formar un árbol conectando un nuevo nodo de raíz a las raíces de todos los árboles en un bosque.
  • Son los gráficos en los que, para cada arista uv , se anidan las vecindades de u y v (incluidos u y v ): una vecindad debe ser un subconjunto de la otra. [11]
  • Son los gráficos de permutación definidos a partir de permutaciones ordenables en pila . [12]
  • Son los gráficos con la propiedad de que en cada uno de sus subgrafos inducidos el número de cobertura de la camarilla es igual al número de camarillas máximas . [13]
  • Son las gráficas con la propiedad de que en cada una de sus subgrafias inducidas el número de camarilla es igual al pseudo-número de Grundy . [13]
  • Son los gráficos con la propiedad de que en cada uno de sus subgrafos inducidos el número cromático es igual al pseudo-número de Grundy . [13]

Clases de gráficos relacionados [ editar ]

De las caracterizaciones equivalentes de gráficas trivialmente perfectas se desprende que toda gráfica trivialmente perfecta es también una cografía , una gráfica cordal , una gráfica ptolemaica , una gráfica de intervalo y una gráfica perfecta .

Los gráficos de umbral son exactamente los gráficos que son trivialmente perfectos y los complementos de los gráficos trivialmente perfectos (gráficos co-trivialmente perfectos). [14]

Los gráficos de molinos de viento son trivialmente perfectos.

Reconocimiento [ editar ]

Chu (2008) describe un algoritmo de tiempo lineal simple para reconocer gráficos trivialmente perfectos, basado en una búsqueda lexicográfica en amplitud . Siempre que el algoritmo LexBFS elimina un vértice v del primer conjunto de su cola, el algoritmo comprueba que todos los vecinos restantes de v pertenecen al mismo conjunto; si no, uno de los subgrafos inducidos prohibidos se puede construir a partir del v . Si esta verificación tiene éxito para cada v , entonces la gráfica es trivialmente perfecta. El algoritmo también se puede modificar para probar si una gráfica es la gráfica complementaria de una gráfica trivialmente perfecta, en tiempo lineal.

Determinar si un gráfico general está a k eliminaciones de bordes de un gráfico trivialmente perfecto es NP-completo, [15] manejable con parámetros fijos [16] y puede resolverse en O (2.45 k ( m  +  n )) tiempo. [17]

Notas [ editar ]

  1. ^ Brandstädt, Le & Spinrad (1999) , definición 2.6.2, p.34; Golumbic (1978) .
  2. ^ Wolk (1962) ; Wolk (1965) .
  3. ^ Donnelly e Isaak (1999) .
  4. ^ Yan, Chen y Chang (1996) .
  5. ^ Brandstädt, Le & Spinrad (1999) , teorema 6.6.1, p. 99; Golumbic (1978) , corolario 4.
  6. ^ Brandstädt, Le & Spinrad (1999) , teorema 6.6.1, p. 99; Golumbic (1978) , teorema 2. Wolk (1962) y Wolk (1965) demostraron esto para gráficos de comparabilidad de bosques enraizados.
  7. ^ Wolk (1962) .
  8. ^ Brandstädt, Le y Spinrad (1999) , p. 51.
  9. ↑ a b Brandstädt, Le & Spinrad (1999) , p. 248; Yan, Chen y Chang (1996) , teorema 3.
  10. ^ Yan, Chen y Chang (1996) ; Gurski (2006) .
  11. ^ Yan, Chen y Chang (1996) , teorema 3.
  12. ^ Rotem (1981) .
  13. ↑ a b c Rubio-Montiel (2015) .
  14. ^ Brandstädt, Le & Spinrad (1999) , teorema 6.6.3, p. 100; Golumbic (1978) , corolario 5.
  15. ^ Sharan (2002) .
  16. ^ Cai (1996) .
  17. ^ Nastos y Gao (2010) .

Referencias [ editar ]

  • 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.
  • Cai, L. (1996), "Tractabilidad de parámetros fijos de problemas de modificación de gráficos para propiedades hereditarias", Information Processing Letters , 58 (4): 171-176, doi : 10.1016 / 0020-0190 (96) 00050-6.
  • Chu, Frank Pok Man (2008), "Un tiempo lineal simple que certifica un algoritmo basado en LBFS para reconocer gráficos trivialmente perfectos y sus complementos", Information Processing Letters , 107 (1): 7–12, doi : 10.1016 / j.ipl. 2007.12.009.
  • Donnelly, Sam; Isaak, Garth (1999), "Poderes hamiltonianos en gráficos de comparabilidad arborescente y umbral", Matemáticas discretas , 202 (1-3): 33-44, doi : 10.1016 / S0012-365X (98) 00346-X
  • Golumbic, Martin Charles (1978), "Gráficos trivialmente perfectos", Matemáticas discretas , 24 (1): 105-107, doi : 10.1016 / 0012-365X (78) 90178-4 CS1 maint: parámetro desalentado ( enlace ).
  • Gurski, Frank (2006), "Caracterizaciones para co-gráficos definidos por operaciones restringidas de ancho NLC o ancho de camarilla", Matemáticas discretas , 306 (2): 271-277, doi : 10.1016 / j.disc.2005.11.014.
  • Nastos, James; Gao, Yong (2010), "Una nueva estrategia de ramificación para problemas de modificación de gráficos parametrizados", Lecture Notes in Computer Science , 6509 : 332–346, arXiv : 1006.3020.
  • Rotem, D. (1981), "Permutaciones ordenables en pila", Matemáticas discretas , 33 (2): 185-196, doi : 10.1016 / 0012-365X (81) 90165-5 , MR  0599081.
  • Rubio-Montiel, C. (2015), "Una nueva caracterización de gráficos trivialmente perfectos", Revista Electrónica de Teoría y Aplicaciones de Gráficos , 3 (1): 22-26, doi : 10.5614 / ejgta.2015.3.1.3.
  • Sharan, Roded (2002), "Problemas de modificación de gráficos y sus aplicaciones a la investigación genómica", Tesis doctoral, Universidad de Tel Aviv.
  • Wolk, ES (1962), "El gráfico de comparabilidad de un árbol", Proceedings of the American Mathematical Society (5 ed.), 13 : 789–795, doi : 10.1090 / S0002-9939-1962-0172273-0.
  • Wolk, ES (1965), "Una nota sobre el gráfico de comparabilidad de un árbol", Proceedings of the American Mathematical Society (1 ed.), 16 : 17-20, doi : 10.1090 / S0002-9939-1965-0172274-5.
  • Yan, Jing-Ho; Chen, Jer-Jeong; Chang, Gerard J. (1996), "Gráficos de cuasi-umbral", Matemáticas aplicadas discretas , 69 (3): 247-255, doi : 10.1016 / 0166-218X (96) 00094-7.

Enlaces externos [ editar ]

  • "Gráficos trivialmente perfectos" , Sistema de información sobre clases de gráficos y sus inclusiones