Hispanopedia Wiki
Articulo de referencia

Gráfico trivialmente perfecto

Construcción de un grafo trivialmente perfecto a partir de intervalos anidados y de la relación de alcanzabilidad en un árbol. En teoría de grafos , un grafo trivialmente perfec...

Hispanopedia WikiContenido en espanolLectura gratuita
Construcción de un grafo trivialmente perfecto a partir de intervalos anidados y de la relación de alcanzabilidad 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 independiente máximo es igual al número de cliques máximos . [ 1 ] Los grafos trivialmente perfectos fueron estudiados por primera vez por (Wolk  1962 , 1965 ) pero fueron nombrados por Golumbic (1978) ; Golumbic escribe que "el nombre fue elegido porque es trivial demostrar que tal grafo es perfecto ". Los grafos trivialmente perfectos también se conocen como grafos de comparabilidad de árboles , [ 2 ] grafos de comparabilidad arborescentes , [ 3 ] y grafos cuasi-umbral . [ 4 ]

Caracterizaciones equivalentes

Los grafos trivialmente perfectos tienen otras caracterizaciones equivalentes:

  • Son los grafos de comparabilidad de árboles de teoría de orden . 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 además T posee un elemento mínimo r . Entonces el grafo de comparabilidad de T es trivialmente perfecto, y todo grafo trivialmente perfecto puede formarse de esta manera. [ 5 ]
  • Son los grafos que no tienen un grafo de camino P 4 ni un grafo de ciclo C 4 como subgrafos inducidos . [ 6 ]
  • Son los grafos en los que cada subgrafo inducido conexo contiene un vértice universal . [ 7 ]
  • Son los gráficos que pueden representarse como gráficos de intervalos para un conjunto de intervalos anidados . Un conjunto de intervalos está anidado si, para cada par de intervalos del conjunto, o bien son disjuntos o uno contiene al otro. [ 8 ]
  • Son los grafos que son a la vez cordales y cografos . [ 9 ] Esto se deduce de la caracterización de los grafos cordales como los grafos sin ciclos inducidos de longitud mayor que tres, y de los cografos como los grafos sin caminos inducidos en cuatro vértices ( P 4 ).
  • Son las gráficas que son a la vez cográficas y gráficas de intervalos. [ 9 ]
  • Son los grafos que se pueden formar, a partir de grafos de un vértice, mediante dos operaciones: la unión disjunta de dos grafos trivialmente perfectos más pequeños y la adición de un nuevo vértice adyacente a todos los vértices de un grafo trivialmente perfecto más pequeño. [ 10 ] Estas operaciones corresponden, en el bosque subyacente, a la formación de un nuevo bosque mediante la unión disjunta de dos bosques más pequeños y a la formación de un árbol mediante la conexión de un nuevo nodo raíz a las raíces de todos los árboles de un bosque.
  • Son los grafos en los que, para cada arista uv , los vecindarios de u y v (incluidos u y v mismos) están anidados: un vecindario debe ser un subconjunto del otro. [ 11 ]
  • Son los grafos de permutación definidos a partir de permutaciones ordenables por pila . [ 12 ]
  • Son los grafos con la propiedad de que en cada uno de sus subgrafos inducidos el número de cobertura de clique es igual al número de cliques maximales . [ 13 ]
  • Son los grafos con la propiedad de que en cada uno de sus subgrafos inducidos el número de clique es igual al número de pseudo-Grundy . [ 13 ]
  • Son los grafos con la propiedad de que en cada uno de sus subgrafos inducidos el número cromático es igual al número pseudo-Grundy . [ 13 ]

De las caracterizaciones equivalentes de los grafos trivialmente perfectos se deduce que todo grafo trivialmente perfecto es también un cografo , un grafo cordal , un grafo ptolemaico , un grafo de intervalos y un grafo perfecto .

Los grafos umbral son precisamente los grafos que son a la vez trivialmente perfectos y complementos de grafos trivialmente perfectos (grafos cotrivialmente perfectos). [ 14 ]

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

Reconocimiento

Chu (2008) describe un algoritmo sencillo de tiempo lineal para reconocer grafos trivialmente perfectos, basado en la búsqueda en anchura lexicográfica . Cada vez que el algoritmo LexBFS elimina un vértice v del primer conjunto de su cola, comprueba que todos los vecinos restantes de v pertenezcan al mismo conjunto; si no es así, se puede construir uno de los subgrafos inducidos prohibidos a partir de v . Si esta comprobación tiene éxito para cada v , entonces el grafo es trivialmente perfecto. El algoritmo también puede modificarse para comprobar, en tiempo lineal, si un grafo es el complemento de un grafo trivialmente perfecto.

Determinar si un grafo general está a k eliminaciones de aristas de un grafo trivialmente perfecto es NP-completo , [ 15 ] tratable con parámetros fijos [ 16 ] y se puede resolver en tiempo O (2,45k ( m + n ) ) . [ 17 ]

Notas

  1. ^ Brandstädt, Le & Spinrad (1999) , definición 2.6.2, p.34; Golúmbico (1978) .
  2. ^ Wolk (1962) ; Wolk (1965) .
  3. ^ Donnelly & Isaak (1999) .
  4. ^ Yan, Chen y Chang (1996) .
  5. ^ Brandstädt, Le y Spinrad (1999) , teorema 6.6.1, p. 99; Golumbic (1978) , corolario 4.
  6. ^ Brandstädt, Le y Spinrad (1999) , teorema 6.6.1, pág. 99; Golumbic (1978) , teorema 2. Wolk (1962) y Wolk (1965) demostraron esto para grafos de comparabilidad de bosques con raíz.
  7. ^ Wolk (1962) .
  8. ^ Brandstädt, Le y Spinrad (1999) , pág. 51.
  9. ^ Brandstädt , Le y Spinrad (1999) , pág. 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 y Spinrad (1999) , teorema 6.6.3, p. 100; Golumbic (1978) , corolario 5.
  15. ^ Sharan (2002) .
  16. ^ Cai (1996) .
  17. ^ Nastos y Gao (2010) .

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.
  • Cai, L. (1996), "Tratabilidad con parámetros fijos de problemas de modificación de grafos para propiedades hereditarias", Information Processing Letters , 58 (4): 171–176 , doi : 10.1016/0020-0190(96)00050-6.
  • Chu, Frank Pok Man (2008), "Un algoritmo simple de tiempo lineal basado en LBFS para la certificación de grafos 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), "Potencias hamiltonianas en grafos de comparabilidad umbral y arborescente", Matemáticas Discretas , 202 ( 1–3 ): 33–44 , doi : 10.1016/S0012-365X(98)00346-X
  • Golumbic, Martin Charles (1978), "Grafos trivialmente perfectos", Matemáticas Discretas , 24 (1): 105– 107, doi : 10.1016/0012-365X(78)90178-4.
  • Gurski, Frank (2006), "Caracterizaciones para cografos definidos por operaciones de ancho NLC restringido o ancho de clique", 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 grafos parametrizados", en Wu, Weili ; Daescu, Ovidiu (eds.), Optimización combinatoria y aplicaciones – 4.ª Conferencia Internacional, COCOA 2010, Kailua-Kona, HI, EE. UU., 18-20 de diciembre de 2010, Actas, Parte II , Lecture Notes in Computer Science, vol. 6509, Springer, pp.  332-346 , arXiv : 1006.3020 , doi : 10.1007/978-3-642-17461-2_27 , ISBN 978-3-642-17460-5
  • Rotem, D. (1981), "Permutaciones ordenables por 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 grafos trivialmente perfectos", Electronic Journal of Graph Theory and Applications , 3 (1): 22– 26, doi : 10.5614/ejgta.2015.3.1.3.
  • Sharan, Roded (2002), "Problemas de modificación de grafos y sus aplicaciones a la investigación genómica", Tesis doctoral, Universidad de Tel Aviv.
  • Wolk, ES (1962), "El grafo de comparabilidad de un árbol", Actas de la Sociedad Matemática Americana , 13 (5) (5.ª ed.): 789–795 , doi : 10.1090/S0002-9939-1962-0172273-0.
  • Wolk, ES (1965), "Una nota sobre el grafo de comparabilidad de un árbol", Actas de la Sociedad Matemática Americana , 16 (1.ª ed.): 17–20 , doi : 10.1090/S0002-9939-1965-0172274-5.
  • Yan, Jing-Ho; Chen, Jer-Jeong; Chang, Gerard J. (1996), "Gráficos cuasi-umbral", Matemáticas Aplicadas Discretas , 69 (3): 247– 255, doi : 10.1016/0166-218X(96)00094-7.
  • "Grafos trivialmente perfectos" , Sistema de información sobre clases de grafos y sus inclusiones
Obtenido de " https://en.wikipedia.org/w/index.php?title=Trivially_perfect_graph&oldid=1317724108 "