Caracterización por grafos prohibidos

La caracterización de gráficos prohibidos es un método para describir una familia de gráficos o hipergráficos mediante la especificación de subestructuras que tienen prohibido aparecer dentro de cualquier gráfico de la familia.

Gráficos prohibidos

En la teoría de grafos, muchas familias importantes de gráficos pueden describirse mediante un número finito de gráficos individuales que no pertenecen a la familia, y todos los gráficos de la familia que contienen cualquiera de estos gráficos prohibidos como subgrafo (generado) o menor están excluidos. . El prototipo del fenómeno es el teorema de Pontryagin-Kuratovsky , que establece que un grafo es plano (un grafo que se puede dibujar en un plano sin intersecciones) si y solo si el grafo no contiene ninguno de los dos subgrafos prohibidos, un grafo completo . grafo K 5 y un grafo bipartito completo K 3.3 .

En diferentes familias, la naturaleza de lo que está prohibido varía. En general, una estructura G es miembro de la familia si y sólo si la estructura prohibida no está contenida en G. La subestructura prohibida puede ser una de:

El conjunto de estructuras que tienen prohibido pertenecer a una determinada familia de grafos también puede denominarse conjunto de obstrucción de la familia.

La caracterización por gráficos prohibidos se puede utilizar en algoritmos para probar si un gráfico pertenece a una familia determinada. En muchos casos, es posible verificar en tiempo polinomial si un gráfico dado contiene algún miembro del conjunto de obstrucciones y, por lo tanto, si el gráfico pertenece a la familia definida por el conjunto de obstrucciones.

Para que una familia tenga una caracterización por grafos prohibidos con cierto tipo de subestructuras, la familia debe estar cerrada en subestructuras. Es decir, cualquier subestructura (de un tipo dado) de un grafo en una familia debe ser otro grafo en la familia. De manera equivalente, si el gráfico no está en la familia, todos los gráficos grandes que lo contengan como subestructura también deben excluirse de la familia. Si esto es cierto, siempre hay un conjunto de obstrucciones (el conjunto de gráficos no está en la familia, pero todas las subestructuras más pequeñas están en la familia). Sin embargo, con cierta comprensión de lo que se entiende por subestructura, este conjunto de obstrucciones puede resultar infinito. El teorema de Robertson-Seymour prueba que en ciertos casos de menores del grafo , una familia menor-cerrada siempre tiene un conjunto de obstrucciones finito.

Lista de caracterizaciones gráficas prohibidas (para gráficos e hipergráficos)

Esta es una lista incompleta y es posible que nunca cumpla con ciertos estándares de integridad. Puede complementarlo con fuentes acreditadas .
Familia Columnas prohibidas Adiccion Conexión
el bosque bucles, pares de aristas paralelas y ciclos de cualquier longitud subgrafo Definición
loop (para multigraphs) o triángulo K 3 (para gráficos simples) conde menor Definición
Cuenta sin garras estrella k 1.3 subgrafo generado Definición
Gráficos de comparabilidad subgrafo generado
Gráficos sin triángulos triangulo K 3 subgrafo generado Definición
Gráficos planos K5 y K3.3 _ _ subgrafo homeomorfo Teorema de Pontryagin-Kuratovsky
K5 y K3.3 _ _ conde menor teorema de wagner
Gráficos extraplanares K4 y K2.3 _ _ conde menor Distel, 4. Gráficos planos, pág. 115, ej. 23 [1]
Gráficos uniplanares externos cinco menores prohibidos conde menor Auer, Bachmeier y otros [2]
Gráficos de género fijos conjunto de obstrucciones finitas (ya para gráficos toroidales de tamaño mínimo 250815) conde menor Distel, 12. Menores, árboles y preorden completa, p. 387, ej. 53 [1]
Recuento de ápices conjunto finito de obstrucciones conde menor [3]

Gráficos que admiten incrustaciones sin enlaces

Familia de grafos de Petersen conde menor [cuatro]
Gráficos bipartitos ciclos impares subgrafo [5]
Gráficos de cuerdas ciclos de longitud 4 o más subgrafo generado [6]
Gráficos perfectos ciclos impares de longitud 5 o más y sus complementos subgrafo generado [7]
Gráficos de línea para gráficos nueve subgrafos prohibidos (enumerados aquí ) subgrafo generado [ocho]
Uniones de gráficos de cactus diamante formado al eliminar un borde de un gráfico completo K 4 conde menor [9]
escalera K 2,3 y su gráfico dual subgrafo homeomorfo [diez]
Gráficos de arco circular de Helly subgrafo generado [once]
Gráficos divididos subgrafo generado [12]
Gráficos secuenciales paralelos ( treewidth , branchwidth ) K4 _ conde menor Distel, 7. Teoría de grafos extremos, p. 203, ej. 31 [1]
ancho de madera K 5 , octaedro , prisma pentagonal , gráfico de Wagner conde menor [13]
ancho de madera K4 _ conde menor Distel, 12. Menores, árboles y preorden completa, p. 370, Anexo 12.6.2 [1]
Ancho de rama K 5 , octaedro , cubo , gráfica de Wagner conde menor [catorce]
Gráficos reducibles adicionales (cographs) Cuenta P 4 subgrafo generado [quince]
Gráficos trivialmente perfectos Gráfico P 4 y Ciclo C 4 subgrafo generado [dieciséis]
Gráficos de umbral Gráfico P 4 , ciclo C 4 y complemento C 4 subgrafo generado [dieciséis]
Gráficos de líneas de hipergrafías de 3 líneas homogéneas una lista finita de subgrafos generados prohibidos con un grado mínimo de al menos 19 subgrafo generado [17]
Gráficos de línea k - hipergrafías de línea homogénea, k  > 3 una lista finita de subgrafos generados prohibidos con un grado de borde mínimo de al menos 2 k 2  − 3 k  + 1 subgrafo generado [18] [19]
Teoremas básicos
familia definida por la propiedad heredada derivada (no necesariamente finito) conjunto de obstrucciones subgrafo generado
familia definida por una propiedad hereditaria menor conjunto finito de obstrucciones conde menor Teorema de Robertson-Seymour

Véase también

Notas

  1. ↑ 1 2 3 4 Reinhard Diestel. Teoría de grafos. Archivado el 9 de abril de 2011 en Wayback Machine GTM 173, 5.ª edición 2016/17. Springer-Verlag, Heidelberg. Textos de posgrado en matemáticas, volumen 173. ISBN 978-3-662-53621-6
  2. ↑ Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21.er Simposio Internacional, GD 2013, Burdeos, Francia, 23-25 ​​de septiembre de 2013, Documentos seleccionados revisados ​​/ Stephen Wismath, Alexander Wolff,. - 2013. - T. 8242. - S. 107-118. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-319-03841-4_10 . .
  3. ↑ A. Gupta, R. Impagliazzo. proc. 32º Simposio IEEE sobre Fundamentos de Ciencias de la Computación (FOCS '91) . - IEEE Computer Society, 1991. - S. 802-811. -doi : 10.1109/ SFCS.1991.185452 . .
  4. ↑ Neil Robertson, PD Seymour, Robin Thomas. Incrustaciones sin enlaces de gráficos en 3 espacios // Boletín de la Sociedad Matemática Estadounidense. - 1993. - T. 28 , núm. 1 . — págs. 84–89 . -doi : 10.1090/ S0273-0979-1993-00335-5 . -arXiv : matemáticas / 9301216 . .
  5. ↑ Béla Bollobas Teoría de grafos moderna. - Springer, 1998. - ISBN 0-387-98488-7 .
  6. ↑ Toshinobu Kashiwabara. Teoría de grafos y algoritmos, 17º Simposio del Instituto de Investigación de Comunicación Eléctrica, Universidad de Tohoku, Sendai, Japón, 24 y 25 de octubre de 1980, Actas / Nobuji Saito, Takao Nishizeki. - Springer-Verlag, 1981. - T. 108. - S. 171-181. — (Apuntes de clase en informática). -doi : 10.1007 / 3-540-10704-5\_15 . .
  7. ↑ María Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. El teorema del gráfico perfecto fuerte // Annals of Mathematics . - 2006. - T. 164 , núm. 1 . — S. 51–229 . doi : 10.4007 / annals.2006.164.51 . -arXiv : matemáticas / 0212070v1 . .
  8. ↑ LW Beineke. Beiträge zur Graphentheorie / H. Sachs, H.-J. Voss, HJ walter - Leipzig: Teubner, 1968. - S. 17-33. .
  9. ↑ Ehab El Mallah, Charles Colbourn. La complejidad de algunos problemas de eliminación de bordes // Transacciones IEEE en circuitos y sistemas. - 1988. - T. 35 , núm. 3 . — S. 354–362 . -doi : 10.1109/ 31.1748 . .
  10. ↑ K. Takamizawa, Takao Nishizeki, Nobuji Saito. Problemas combinatorios sobre grafos serie-paralelo // Matemática Aplicada Discreta. - 1981. - T. 3 , núm. 1 . — S. 75–76 . - doi : 10.1016/0166-218X(81)90031-7 . .
  11. ↑ Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Reconocimiento de tiempo lineal de modelos y gráficos de arco circular de Helly // Algorithmica. - 2009. - T. 59 , núm. 2 . — S. 215–239 ​​. -doi : 10.1007/ s00453-009-9304-5 .
  12. ↑ Stephane Földes, Peter L. Peter Hammer. Actas de la Octava Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad del Estado de Luisiana, Baton Rouge, Luisiana, 1977). - Winnipeg: Utilitas Math., 1977a. - T. XIX. — S. 311–315. — (Congressus Numerantium).
  13. ↑ Hans L. Bodlaender. Un k -arboretum parcial de gráficos con ancho de árbol acotado // Ciencias de la computación teórica. - 1998. - T. 209 , núm. 1–2 . — Pág. 1–45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
  14. ↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Gráficos con ancho de rama como máximo tres // Journal of Algorithms. - 1999. - T. 32 , núm. 2 . — S. 167–194 . -doi : 10.1006/ jagm.1999.1011 . .
  15. ↑ D. Seinsche. Sobre una propiedad de la clase de grafos n -colorables // Journal of Combinatorial Theory, Serie B. - 1974. - Vol. 16 , no. 2 . — S. 191–193 . -doi : 10.1016 / 0095-8956(74)90063-X .
  16. ↑ 12 Martín Charles Golumbic . Gráficos trivialmente perfectos // Matemáticas discretas. - 1978. - T. 24 , núm. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
  17. ↑ Yury Metelsky, Regina Tyshkevich. Gráficos en línea de hipergrafías lineales de 3 uniformes // Journal of Graph Theory. - 1997. - vol. 25.- Emisión. 4 . — S. 243–251 . - doi : 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K .
  18. ↑ MS Jacobson, Andre E. Kézdy, Jeno Lehel. Reconocimiento de grafos de intersección de hipergrafos lineales uniformes  // Grafos y Combinatoria . - 1997. - T. 13 . — S. 359–367 . -doi : 10.1007/ BF03353014 .
  19. ↑ Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Gráficos de intersección de k -hipergrafías uniformes // European J. Combinatorics. - 1982. - T. 3 . — S. 159–172 . - doi : 10.1016/s0195-6698(82)80029-2 .