En la teoría de grafos , una rama de las matemáticas, un gráfico dividido es un gráfico en el que los vértices se pueden dividir en una camarilla y un conjunto independiente . Los gráficos divididos fueron estudiados por primera vez por Földes y Hammer ( 1977a , 1977b ), e introducidos de forma independiente por Tyshkevich y Chernyak ( 1979 ). [1]
Un gráfico dividido puede tener más de una partición en una camarilla y un conjunto independiente; por ejemplo, la ruta a - b - c es un gráfico dividido, cuyos vértices se pueden dividir de tres formas diferentes:
- la camarilla { a , b } y el conjunto independiente { c }
- la camarilla { b , c } y el conjunto independiente { a }
- la camarilla { b } y el conjunto independiente { a , c }
Los gráficos divididos se pueden caracterizar en términos de sus subgrafos inducidos prohibidos : un gráfico se divide si y solo si ningún subgrafo inducido es un ciclo en cuatro o cinco vértices, o un par de aristas disjuntas (el complemento de un ciclo de 4). [2]
Relación con otras familias de gráficos
A partir de la definición, los gráficos divididos están claramente cerrados bajo complementación . [3] Otra caracterización de gráficos de división implica la complementación: son gráficos de cuerdas los complementos de que también son cordal. [4] Así como los gráficos cordales son los gráficos de intersección de subárboles de árboles, los gráficos divididos son los gráficos de intersección de distintos subestados de gráficos de estrellas . [5] Casi todos los gráficos de cuerdas son gráficos divididos; es decir, en el límite cuando n llega al infinito, la fracción de los gráficos cordales de n -vértices que se dividen se aproxima a uno. [6]
Debido a que los gráficos de cuerdas son perfectos , también lo son los gráficos divididos. Los gráficos de división doble , una familia de gráficos derivados de gráficos divididos al duplicar cada vértice (por lo que la camarilla llega a inducir un antimatching y el conjunto independiente llega a inducir una coincidencia), figuran de manera prominente como una de las cinco clases básicas de gráficos perfectos a partir de los cuales todos los demás pueden formarse en la prueba de Chudnovsky et al. (2006) del teorema del gráfico perfecto fuerte .
Si un gráfico es tanto un gráfico dividido como un gráfico de intervalo , entonces su complemento es un gráfico dividido y un gráfico de comparabilidad , y viceversa. Los gráficos de comparabilidad divididos y, por lo tanto, también los gráficos de intervalo dividido, se pueden caracterizar en términos de un conjunto de tres subgráficos inducidos prohibidos. [7] Los gráficos divididos son exactamente los gráficos de umbral . Los gráficos de permutación dividida son exactamente los gráficos de intervalo que tienen complementos de gráfico de intervalo; [8] estos son los gráficos de permutación de permutaciones fusionadas sesgadas . [9] Los gráficos divididos tienen el número cocromático 2.
Problemas algorítmicos
Deje G un grafo split, dividida en una camarilla C y un conjunto independiente I . Entonces, cada camarilla máxima en un gráfico de división es o bien C sí mismo, o la zona de un vértice en I . Por lo tanto, es fácil identificar la camarilla máxima y, de manera complementaria, el conjunto independiente máximo en un gráfico dividido. En cualquier gráfico dividido, una de las siguientes tres posibilidades debe ser cierta: [10]
- Existe un vértice x en I tal que C ∪ { x } está completo. En este caso, C ∪ { x } es una camarilla máxima e I es un conjunto independiente máximo.
- Existe un vértice x en C tal que I ∪ { x } es independiente. En este caso, I ∪ { x } es un conjunto independiente máximo y C es una camarilla máxima.
- C es una camarilla máxima e I es un conjunto independiente máximo. En este caso, G tiene una partición única ( C , I ) en una camarilla y un conjunto independiente, C es la camarilla máxima e I es el conjunto independiente máximo.
Algunos otros problemas de optimización que son NP-completos en familias de gráficos más generales, incluida la coloración de gráficos , son igualmente sencillos en los gráficos divididos. Encontrar un ciclo hamiltoniano sigue siendo NP-completo incluso para gráficos divididos que son gráficos fuertemente cordales . [11] También es bien sabido que el problema del Conjunto Mínimo Dominante sigue siendo NP-completo para gráficos divididos. [12]
Secuencias de grados
Una propiedad notable de los gráficos divididos es que pueden reconocerse únicamente a partir de sus secuencias de grados . Deje que la secuencia de grado de un gráfico G sea d 1 ≥ d 2 ≥ ... ≥ d n , y dejar que m sea el mayor valor de i tal que d i ≥ i - 1. Entonces G es un gráfico de división si y sólo si
Si este es el caso, entonces los m vértices con los grados más grandes forman una camarilla máxima en G , y los vértices restantes constituyen un conjunto independiente. [13]
Contando gráficos divididos
Royle (2000) mostró que los gráficos divididos en n -vértices con n están en correspondencia uno a uno con ciertas familias de Sperner . Usando este hecho, determinó una fórmula para el número de gráficas divididas no isomórficas en n vértices. Para valores pequeños de n , a partir de n = 1, estos números son
- 1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (secuencia A048194 en la OEIS ).
Este resultado enumerativo también fue probado anteriormente por Tyshkevich y Chernyak (1990) .
Notas
- ^ Földes y Hammer (1977a) tenían una definición más general, en la que los gráficos que llamaron gráficos divididos también incluían gráficos bipartitos (es decir, gráficos que se dividían en dos conjuntos independientes) y los complementos de los gráficos bipartitos (es decir, gráficos que puede dividirse en dos camarillas). Földes y Hammer (1977b) utilizan la definición dada aquí, que se ha seguido en la literatura posterior; por ejemplo, es Brandstädt, Le & Spinrad (1999) , Definición 3.2.3, p.41.
- ^ Földes y Hammer (1977a) ; Golumbic (1980) , Teorema 6.3, pág. 151.
- ^ Golumbic (1980) , Teorema 6.1, p. 150.
- ^ Földes y Hammer (1977a) ; Golumbic (1980) , Teorema 6.3, pág. 151; Brandstädt, Le y Spinrad (1999) , Teorema 3.2.3, pág. 41.
- ^ McMorris y Shier (1983) ; Voss (1985) ; Brandstädt, Le y Spinrad (1999) , Teorema 4.4.2, pág. 52.
- ^ Bender, Richmond y Wormald (1985) .
- ^ Földes y Hammer (1977b) ; Golumbic (1980) , Teorema 9.7, página 212.
- ^ Brandstädt, Le y Spinrad (1999) , Corolario 7.1.1, p. 106 y Teorema 7.1.2, pág. 107.
- ^ Kézdy, Snefully y Wang (1996) .
- ^ Hammer y Simeone (1981) ; Golumbic (1980) , Teorema 6.2, pág. 150.
- ↑ Müller (1996)
- ↑ Bertossi (1984)
- ^ Hammer y Simeone (1981) ; Tyshkevich (1980) ; Tyshkevich, Melnikow y Kotov (1981) ; Golumbic (1980) , Teorema 6.7 y Corolario 6.8, pág. 154; Brandstädt, Le y Spinrad (1999) , Teorema 13.3.2, pág. 203. Merris (2003) investiga más a fondo las secuencias de grados de los gráficos divididos.
Referencias
- Bender, EA; Richmond, LB; Wormald, NC (1985), "Casi todos los grafos cordales se dividen", J. Austral. Matemáticas. Soc. , A, 38 (2): 214–221, doi : 10.1017 / S1446788700023077 , MR 0770128.
- Bertossi, Alan A. (1984), "Conjuntos dominantes para gráficos divididos y bipartitos", Information Processing Letters , 19 : 37–40, doi : 10.1016 / 0020-0190 (84) 90126-1.
- 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.
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del gráfico fuerte perfecto", Annals of Mathematics , 164 (1): 51-229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51 , MR 2233847.
- Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Gráficos divididos", Actas de la Octava Conferencia Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Univ. Del Estado de Louisiana, Baton Rouge, La., 1977) , Congressus Numerantium, XIX , Winnipeg: Utilitas Math ., págs. 311–315, MR 0505860.
- Földes, Stéphane; Hammer, Peter Ladislaw (1977b), "Gráficos divididos con Dilworth número dos", Canadian Journal of Mathematics , 29 (3): 666–672, doi : 10.4153 / CJM-1977-069-1 , MR 0463041.
- Golumbic, Martin Charles (1980), Teoría algorítmica de gráficos y gráficos perfectos , Academic Press, ISBN 0-12-289260-7, MR 0562306.
- Hammer, Peter Ladislaw ; Simeone, Bruno (1981), "The splittance of a graph", Combinatorica , 1 (3): 275-284, doi : 10.1007 / BF02579333 , MR 0637832.
- Kézdy, André E .; Desdeñosamente, Hunter S .; Wang, Chi (1996), "Partición de permutaciones en subsecuencias crecientes y decrecientes", Journal of Combinatorial Theory , Serie A , 73 (2): 353–359, doi : 10.1016 / S0097-3165 (96) 80012-4 , MR 1370138.
- McMorris, FR; Shier, DR (1983), "Representación de grafos cordales en K 1, n ", Commentationes Mathematicae Universitatis Carolinae , 24 : 489–494, MR 0730144.
- Merris, Russell (2003), "Gráficos divididos", European Journal of Combinatorics , 24 (4): 413–430, doi : 10.1016 / S0195-6698 (03) 00030-1 , MR 1975945.
- Müller, Haiko (1996), "Circuitos hamiltonianos en gráficos bipartitos cordales", Matemáticas discretas , 156 : 291-298, doi : 10.1016 / 0012-365x (95) 00057-4.
- Royle, Gordon F. (2000), "Conteo de portadas de conjuntos y gráficos divididos" (PDF) , Journal of Integer Sequences , 3 (2): 00.2.6, MR 1778996.
- Tyshkevich, Regina I. (1980), "[La descomposición canónica de un gráfico]", Doklady Akademii Nauk SSSR (en ruso), 24 : 677–679, MR 0587712
- Tyshkevich, Regina I .; Chernyak, AA (1979), "Partición canónica de un gráfico definido por los grados de sus vértices", Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk (en ruso), 5 : 14-26, MR 0554162.
- Tyshkevich, Regina I .; Chernyak, AA (1990),Еще один метод перечисления непомеченных комбинаторных объектов, Mat. Zametki (en ruso), 48 (6): 98–105, MR 1102626. Traducido como "Otro método más para enumerar objetos combinatorios sin marcar" (1990), Notas matemáticas de la Academia de Ciencias de la URSS 48 (6): 1239-1245, doi : 10.1007 / BF01240267 .
- Tyshkevich, Regina I .; Melnikow, OI; Kotov, VM (1981), "Sobre gráficos y secuencias de grados: la descomposición canónica", Kibernetika (en ruso), 6 : 5–8, MR 0689420.
- Voss, H.-J. (1985), "Nota sobre un artículo de McMorris y Shier", Commentationes Mathematicae Universitatis Carolinae , 26 : 319–322, MR 0803929.
Otras lecturas
- Un capítulo sobre gráficos divididos aparece en el libro de Martin Charles Golumbic , "Teoría de gráficos algorítmicos y gráficos perfectos".