Incrustación de gráficos no vinculados

Una incrustación de gráficos no vinculados  es una incrustación de un gráfico no dirigido en el espacio euclidiano, de modo que dos ciclos del gráfico no tienen un coeficiente de enlace distinto de cero . Una incrustación plana  es una incrustación en la que cualquier ciclo es el límite de un círculo topológico cuyo interior no está vinculado al gráfico. Un gráfico incrustable sin enlaces  es un gráfico que tiene una incrustación plana o sin enlaces. Estos gráficos forman un análogo tridimensional de los gráficos planos [1] . Por el contrario, un gráfico esencialmente vinculado  es aquel que no tiene incrustaciones no vinculadas.

Las incrustaciones planas automáticamente no tienen enlaces, pero no viceversa [2] . El gráfico completo , el gráfico de Petersen y los otros cinco gráficos de la familia de gráficos de Petersen no tienen incrustaciones no vinculadas [1] . Los gráficos de incrustación no vinculados se cierran mediante transformaciones de gráficos menores [3] y Y-Δ [2] . Estos grafos tienen como menores prohibidos a los grafos de la familia Petersen [4] e incluyen grafos planos y grafos de vértices [2] . Los gráficos se pueden reconocer (y se puede construir una incrustación plana) en tiempo lineal [5] .

Definiciones

Se dice que dos curvas que no se cortan en el espacio euclidiano están desvinculadas si hay un movimiento continuo de las curvas que las transforma en dos círculos coplanares que no se cortan sin que una curva pase por la otra o por sí misma. Si no hay tal movimiento continuo, se dice que las curvas están enlazadas . El vínculo de Hopf formado por dos círculos que pasan a través de un disco atravesado por estos círculos proporciona el ejemplo más simple de un par de curvas vinculadas, pero las curvas se pueden vincular de formas mucho más complejas. Si las curvas no están vinculadas, uno puede encontrar un disco (topológico) en el espacio delimitado por la primera curva y que no se cruza con la segunda. Por el contrario, si existe tal disco, las curvas no están vinculadas.

El coeficiente de enlace de dos curvas cerradas en el espacio tridimensional es una invariante topológica de la curva: este es un número definido para las curvas en una de las formas equivalentes, que no cambia si las curvas se mueven en el espacio continuamente sin cruzarse entre sí. o ellos mismos. El coeficiente de enganche se obtiene proyectando un empotramiento sobre un plano y contando de cierta manera el número de pasadas de la primera curva sobre la segunda (con signo +1 o −1 según el sentido de paso). La proyección debe ser "correcta", lo que significa que no se proyectan dos vértices en el mismo punto, ningún vértice se proyecta dentro de un borde, y en cualquier punto de la proyección donde los bordes se cruzan, se cruzan transversalmente . Bajo tales restricciones, cualquier proyección conduce al mismo coeficiente de enlace. El coeficiente de enlace de las curvas no enlazadas es cero y, por lo tanto, si un par de curvas tiene un coeficiente de enlace distinto de cero, las dos curvas deben estar enlazadas. Sin embargo, hay ejemplos de curvas vinculadas que tienen un factor de vinculación de cero, como el vínculo de Whitehead .

La incrustación de un gráfico en un espacio tridimensional consiste en asignar vértices del gráfico a puntos en el espacio y asignaciones de aristas a curvas, de modo que cada punto final de una arista se asigna a un punto final de la curva correspondiente y las curvas correspondientes a dos los diferentes bordes no se cruzan (excepto en los puntos finales comunes). Cualquier gráfico finito tiene un número finito (posiblemente exponencial) de ciclos simples diferentes , y si el gráfico está incrustado en un espacio tridimensional, cada ciclo forma una curva cerrada simple. Es posible calcular el coeficiente de enlace de cada par de curvas que no se cortan formadas de esta manera. Si todos los pares de ciclos tienen un coeficiente de enlace cero, se dice que la incrustación no está enlazada [6] [1] [2] .

En algunos casos, un gráfico se puede incrustar en el espacio de tal manera que para cada ciclo del gráfico se puede encontrar un disco delimitado por este ciclo que no se cruza con otros elementos del gráfico. En este caso, el ciclo no debe estar vinculado a otros ciclos del gráfico que no lo intersecan. Se dice que una incrustación es plana si algún ciclo limita el disco de la forma descrita [2] . De manera similar, se da una definición de "buena inversión" en Motwani, Raghunathan, Saran, 1988 . Véase también Saran (1989 ) y Böhme (1990 ). Una incrustación plana es necesariamente desvinculada, pero puede haber incrustaciones desvinculadas que no sean planas. Por ejemplo, si G es un gráfico formado por dos ciclos separados y la incrustación da como resultado un vínculo de Whitehead, la incrustación no está vinculada pero no es plana.

Se dice que un gráfico está esencialmente vinculado si cualquier incrustación da como resultado una incrustación siempre vinculada. Aunque las incrustaciones no vinculadas y planas no son lo mismo, los gráficos que tienen incrustaciones no vinculadas resultan ser los mismos gráficos que los gráficos que tienen incrustaciones planas [7] .

Ejemplos y contraejemplos

Como mostró Sacks [1] , los siete gráficos de una familia de Petersen están esencialmente vinculados, y no importa cómo estos gráficos estén incrustados en el espacio, para cualquier incrustación tienen dos ciclos vinculados. Estos gráficos incluyen el gráfico completo , el gráfico de Petersen , el gráfico formado al eliminar un borde de un gráfico bipartito completo y el gráfico tripartito completo .

Cualquier gráfico plano tiene una incrustación plana y no vinculada: simplemente incruste el gráfico en un plano ubicado en el espacio (tridimensional). Si el gráfico es plano, esta es la única forma de incrustar el gráfico plano y desvinculado: cualquier incrustación plana puede deformarse continuamente en una incrustación en el plano. Por el contrario, cualquier gráfico desvinculado no plano tiene múltiples incrustaciones desvinculadas [2] .

El gráfico de vértice , formado al agregar un vértice al gráfico plano, también tiene una incrustación plana y no encadenada: incrustamos la parte plana del gráfico en el plano, colocamos el vértice del gráfico (el vértice que viola la planaridad) sobre el plano, y luego dibuja bordes desde el vértice hasta los vértices adyacentes en forma de segmentos. Toda curva cerrada en el plano delimita un disco que no pasa por otro elemento del gráfico, y toda curva cerrada en el vértice delimita un disco por encima del plano que no pasa por ningún otro elemento del gráfico [2] .

Si el gráfico tiene una incrustación plana o no vinculada, modificar el gráfico dividiendo o fusionando sus bordes, agregando o eliminando múltiples bordes entre un par de vértices, o realizando transformaciones Y-Δ , en las que un vértice de grado tres se reemplaza por un triángulo que conecta tres vecinos, o viceversa, conduce a la preservación de la existencia de una incrustación plana o no enlazada [2] . En particular, en un gráfico plano cúbico (en el que todos los vértices tienen exactamente tres vecinos, como un cubo), uno puede hacer copias de cualquier conjunto independiente de vértices realizando una transformación Y-Δ, agregando múltiples copias de los bordes en el resultado triángulos, y luego haciendo las transformadas inversas Δ -Y.

Caracterización y reconocimiento

Si un gráfico tiene una incrustación plana o no vinculada, entonces cualquier gráfico menor (el gráfico formado al contraer los bordes y eliminar bordes y vértices) también tiene una incrustación plana o no vinculada. La eliminación no puede interrumpir la posibilidad de anidamiento no vinculado o plano, y la contracción se puede realizar dejando un extremo del borde que se contrae en su lugar y cambiando todos los bordes que inciden en el vértice opuesto. Por lo tanto, según el teorema de Robertson-Seymour , los gráficos que tienen una incrustación no vinculada se caracterizan como gráficos prohibidos como gráficos que no contienen ninguno de un conjunto finito de menores [3] .

Sacks [1] descubrió el conjunto de menores prohibidos para gráficos que admiten incrustaciones no vinculadas : siete  gráficos de la familia Petersen son gráficos esencialmente vinculados mínimos menores. Sin embargo, Sachs no pudo demostrar que solo estos gráficos son gráficos enlazados menor-mínimo, y esto fue hecho por Robertson, Seymour y Thomas [4] .

La caracterización por menores prohibidos de grafos que admiten incrustaciones no enlazadas conduce a un algoritmo con tiempo de ejecución polinomial para su reconocimiento, pero este algoritmo no construye una incrustación real. Karavabaishi, Kreutzer y Mohar [5] describieron un algoritmo de tiempo lineal que verifica si un gráfico es integrable sin un enlace y, si es integrable, construye una incrustación plana del gráfico. Su algoritmo encuentra grandes subgrafos planos dentro de un gráfico dado de tal manera que, si hay una incrustación no vinculada, representan una incrustación plana del subgrafo. Al volver a simplificar el gráfico cuando se encuentra un subgráfico de este tipo, reducen el problema a uno en el que el gráfico restante está restringido por el ancho del árbol , momento en el que el problema se puede resolver mediante programación dinámica .

Robertson, Seymour y Thomas [2] plantearon el problema de verificar de manera efectiva si una incrustación determinada es plana o no está vinculada . El problema sigue sin resolverse y es equivalente en complejidad al problema de desenredar nudos , el problema de verificar si una curva en el espacio no está anudada [5] . Se sabe que la comprobación de desanudamiento (y por lo tanto también de anidamiento desvinculado) pertenece a la clase NP , pero no se sabe si pertenece a la clase de problemas NP-completos [8] .

Familias de grafos relacionadas

El invariante de Colin de Verdière  es un número definido para cualquier gráfico basado en la teoría algebraica de gráficos . Un gráfico con un invariante de Colin de Verdière que no exceda μ para cualquier constante fija μ forma una familia cerrada menor, y las primeras familias de este tipo son bien conocidas: los gráficos con μ ≤ 1 son bosques lineales (una unión disjunta de caminos), gráficos con μ ≤ 2 son gráficos planos exteriores , y los gráficos con μ ≤ 3 son gráficos planos . Como sugieren Robertson, Seymour y Thomas [2] y lo demuestran Lowash y Schreiver [9] , los gráficos con μ ≤ 4 son exactamente gráficos con incrustaciones no vinculadas.

Los gráficos planos y los gráficos de vértices permiten la incrustación no vinculada, al igual que los gráficos obtenidos mediante transformaciones Y-Δ a partir de ellos [2] . Los gráficos reducibles YΔY  son gráficos que se pueden reducir a un solo vértice mediante una transformación Y-Δ, eliminando vértices aislados y vértices colgantes (vértices de grado 1) y reemplazando arcos en un vértice con grado dos con un solo arco. Estas gráficas también se cierran en menores. Sin embargo, hay gráficos YΔY-irreducibles no vinculados, como el gráfico de vértice formado al conectar un vértice (un vértice que viola la planaridad) a todos los vértices de grado tres de un dodecaedro rómbico [10] . También hay gráficos no vinculados que no se pueden transformar mediante transformaciones Y-Δ, eliminando vértices aislados y colgantes y reemplazando arcos en un vértice con grado dos con un arco en un gráfico de vértice. Por ejemplo, una corona con diez vértices tiene una incrustación no vinculada, pero no se puede convertir en un gráfico de vértices de la manera descrita anteriormente [2] .

Relacionada con la noción de una incrustación no vinculada está la noción de una incrustación no anudada. Es una incrustación de gráfico tal que ningún ciclo simple forma un nudo no trivial . Los gráficos que no tienen una incrustación no anudada incluyen K 7 y K 3,3,1,1 [6] [11] . Sin embargo, hay menores prohibidos mínimos para incrustaciones no anudadas que no se forman (a diferencia de los dos gráficos anteriores) agregando un vértice a un gráfico esencialmente vinculado [12] .

Se pueden definir familias de grafos por la presencia o ausencia de nudos y enlaces más complejos en su incrustación [3] [13] , o por una incrustación no vinculada en una variedad tridimensional distinta del espacio euclidiano [14] . Flapan, Naimi y Pommersheim [15] definieron la incrustación de un grafo como triple enlace si hay tres ciclos, ninguno de los cuales puede separarse de los otros dos. Demostraron que K 9 no está esencialmente enlazado tres veces, mientras que K 10 está enlazado [16] . De manera más general, se puede definir una incrustación con enlace n para any como una incrustación que contiene un enlace de componente que no puede dividirse por una esfera topológica en dos partes separadas. Los grafos de enlace esencial menor-mínimo son conocidos para todos [17] .

Historia

La cuestión de si una incrustación tiene un vínculo o un plano fue planteada en la comunidad de investigación topológica a principios de la década de 1970 por Bothe [18] . La incrustación no vinculada atrajo la atención de los teóricos de grafos Sacks [1] , quienes propusieron varios problemas relacionados, incluido el problema de encontrar una caracterización mediante gráficos prohibidos de gráficos con incrustaciones no vinculadas o planas. Sachs mostró que siete gráficos de la familia Petersen (incluido ) no tienen tales incrustaciones. Como señalaron Nexetril y Thomas [3] , los grafos de incrustación no vinculados están cerrados en los menores del grafo , lo que implica, por el teorema de Robertson-Seymour , que existe una caracterización por grafos prohibidos. La prueba de la existencia de un número finito de grafos obstructivos no conduce a una descripción explícita de este conjunto de menores prohibidos, pero de los resultados de Sacks se sigue que siete grafos de la familia Petersen pertenecen al conjunto. Estos problemas fueron finalmente resueltos por Robertson, Seymour y Thomas [4] [7] quienes demostraron que estos siete gráficos de la familia Petersen son los únicos menores mínimos prohibidos para dichos gráficos. Por lo tanto, los gráficos incrustables no vinculados y los gráficos incrustables planos son el mismo conjunto de gráficos, y ambas familias pueden definirse como gráficos que no contienen elementos de la familia Petersen como menores.

Sacks [1] también preguntó sobre los límites en el número de aristas y el número cromático de gráficos incrustables sin enlace. El número de aristas en un gráfico de vértice incrustable sin un enlace no excede  : los gráficos de vértice máximo c tienen exactamente este número de aristas [1] , y Mader [19] demostró el límite superior para una clase más general de gráfico libre de K 6 menores de edad En 1985, se demostró que la pregunta de Sachs sobre el número cromático se resolvería si se probara la conjetura de Hadwiger de que cualquier grafo -cromático tiene un grafo completo con vértices menores [3] . La demostración de Robertson, Seymour y Thomas [20] del caso de la conjetura de Hadwiger es suficiente para resolver la pregunta de Sachs: los gráficos sin enlaces se pueden colorear con cinco colores como máximo, ya que cualquier gráfico de 6 cromáticas contiene un menor y no está desvinculado. , y hay gráficos no vinculados como , que requieren cinco colores. Del teorema de Snark se deduce que cualquier gráfico incrustable cúbico sin un enlace es coloreable en 3 aristas .

El estudio de incrustaciones sin enlaces comenzó con el estudio de algoritmos a fines de la década de 1980 [21] [22] . Algorítmicamente, el problema de reconocer grafos empotrables planos y empotrables sin enlaces se resolvió cuando se probó la caracterización por menores prohibidos: el algoritmo de Robertson y Seymour [23] se puede usar para verificar en tiempo polinomial si un gráfico dado contiene alguno de los siete menores prohibidos. [24] . Este método no crea una incrustación plana o no vinculada si existe, sino un algoritmo que crea una incrustación [25] y luego encontró un algoritmo más eficiente que se ejecuta en tiempo lineal [5] .

La última pregunta de Sachs [1] sobre la posibilidad de una analogía del teorema de Fari para grafos no enlazados aún no ha sido respondida. La pregunta se plantea de la siguiente manera: ¿cuándo la existencia de un empotramiento desligado o plano con aristas curvas o lineales a trozos implica la existencia de un empotramiento desligado o plano en el que las aristas son segmentos ?

Notas

  1. ↑ 1 2 3 4 5 6 7 8 9 Sachs, 1983 .
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 5 Nešetřil, Thomas, 1985 .
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1995 .
  5. ↑ 1 2 3 4 Kawarabayashi, Kreutzer, Mohar, 2010 .
  6. ↑ 1 2 Conway, Gordon, 1983 .
  7. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  8. ↑ Hass, Lagarias, Pippenger, 1999 .
  9. ↑ Lovász, Schrijver, 1998 .
  10. ↑ Truemper, 1992 .
  11. ↑ Foisy, 2002 .
  12. ↑ Foisy, 2003 .
  13. ↑ Fleming, Diesel, 2005 .
  14. ↑ Flapan, Howards, Lawrence, Mellor, 2006 .
  15. ↑ Flapan, Naimi, Pommersheim, 2001 .
  16. ↑ Para ver otros ejemplos de gráficos no vinculados tres veces, consulte Bowlin y Foisy 2004 .
  17. ↑ Flapan, Pommersheim, Foisy, Naimi, 2001 .
  18. ↑ Ambos, 1973 .
  19. ↑ Mader, 1968 .
  20. ↑ Robertson, Seymour, Thomas, 1993c .
  21. ↑ Becarios, Langston, 1988 .
  22. ↑ Motwani, Raghunathan, Saran, 1988 .
  23. ↑ Robertson, Seymour, 1995 .
  24. ↑ Fellows y Langston ( Fellows, Langston, 1988 ) notaron la aplicabilidad del algoritmo de Robertson-Seymour a este problema .
  25. ↑ van der Holst, 2009 .

Literatura