En teoría de grafos topológicos , una disciplina matemática, una incrustación sin enlaces de un gráfico no dirigido es una incrustación del gráfico en un espacio euclidiano tridimensional de tal manera que no hay dos ciclos del gráfico vinculados. Una incrustación plana es una incrustación con la propiedad de que cada ciclo es el límite de un disco topológico cuyo interior está separado del gráfico. Un gráfico integrable sin vínculos es un gráfico que tiene una incrustación plana o sin vínculos; Estos gráficos forman un análogo tridimensional de los gráficos planos . [1] De manera complementaria, un gráfico intrínsecamente vinculado es un gráfico que no tiene una incrustación sin vínculos.
Las incrustaciones planas no tienen vínculos automáticamente, pero no al revés. [2] El gráfico completo K 6 , el gráfico de Petersen y los otros cinco gráficos de la familia Petersen no tienen incrustaciones sin enlaces. [1] Cada gráfico menor de un gráfico integrable sin vínculos es nuevamente integrable sin vínculos, [3] al igual que cada gráfico al que se puede llegar desde un gráfico integrable sin vínculos mediante transformaciones YΔ y ΔY . [2] Los gráficos integrables sin enlaces tienen los gráficos de la familia Petersen como sus menores prohibidos , [4] e incluyen los gráficos planos y los gráficos de vértices . [2] Se pueden reconocer y se puede construir una incrustación plana para ellos, en O ( n 2 ) . [5]
When the circle is mapped to three-dimensional Euclidean space by an injective function (a continuous function that does not map two different points of the circle to the same point of space), its image is a closed curve. Two disjoint closed curves that both lie on the same plane are unlinked, and more generally a pair of disjoint closed curves is said to be unlinked when there is a continuous deformation of space that moves them both onto the same plane, without either curve passing through the other or through itself. If there is no such continuous motion, the two curves are said to be linked. For example, the Hopf link is formed by two circles that each pass through the disk spanned by the other. It forms the simplest example of a pair of linked curves, but it is possible for curves to be linked in other more complicated ways. If two curves are not linked, then it is possible to find a topological disk in space, having the first curve as its boundary and disjoint from the second curve. Conversely if such a disk exists then the curves are necessarily unlinked.
The linking number of two closed curves in three-dimensional space is a topological invariant of the curves: it is a number, defined from the curves in any of several equivalent ways, that does not change if the curves are moved continuously without passing through each other. The version of the linking number used for defining linkless embeddings of graphs is found by projecting the embedding onto the plane and counting the number of crossings of the projected embedding in which the first curve passes over the second one, modulo 2.[2] The projection must be "regular", meaning that no two vertices project to the same point, no vertex projects to the interior of an edge, and at every point of the projection where the projections of two edges intersect, they cross transversally; with this restriction, any two projections lead to the same linking number. The linking number of the unlink is zero, and therefore, if a pair of curves has nonzero linking number, the two curves must be linked. However, there are examples of curves that are linked but that have zero linking number, such as the Whitehead link.
Una incrustación de un gráfico en un espacio tridimensional consiste en un mapeo de los vértices del gráfico a puntos en el espacio, y de los bordes del gráfico a curvas en el espacio, de modo que cada punto final de cada borde se mapea a un punto final de la curva correspondiente, y tal que las curvas para dos aristas diferentes no se cruzan excepto en un punto final común de las aristas. Cualquier gráfico finito tiene un número finito (aunque quizás exponencial) de ciclos simples distintos , y si el gráfico está incrustado en un espacio tridimensional, entonces cada uno de estos ciclos forma una curva cerrada simple. Se puede calcular el número de enlace de cada par de curvas disjuntas formadas de esta manera; Si todos los pares de ciclos tienen un número de enlace cero, se dice que la incrustación no tiene enlaces. [6]
En algunos casos, un gráfico puede estar incrustado en el espacio de tal manera que, para cada ciclo del gráfico, se pueda encontrar un disco delimitado por ese ciclo que no cruce ninguna otra característica del gráfico. En este caso, el ciclo debe estar desvinculado de todos los demás ciclos separados de él en el gráfico. Se dice que la incrustación es plana si cada ciclo limita un disco de esta manera. [7] Una incrustación plana no tiene necesariamente vínculos, pero pueden existir incrustaciones sin vínculos que no sean planas: por ejemplo, si G es un gráfico formado por dos ciclos disjuntos y está incrustado para formar el vínculo de Whitehead, entonces la incrustación no tiene vínculos. pero no plano.
Se dice que un grafo está intrínsecamente vinculado si, no importa cómo esté incrustado, la incrustación siempre está vinculada. Aunque las incrustaciones planas y sin vínculos no son lo mismo, los gráficos que tienen incrustaciones sin vínculos son los mismos que los gráficos que tienen incrustaciones planas. [8]
Como demostró Sachs (1983), cada uno de los siete grafos de la familia Petersen está intrínsecamente vinculado: no importa cómo cada uno de estos grafos esté incrustado en el espacio, tienen dos ciclos que están vinculados entre sí. Estos gráficos incluyen el gráfico completo K 6 , el gráfico de Petersen , el gráfico formado eliminando un borde del gráfico bipartito completo K 4,4 y el gráfico tripartito completo K 3,3,1 .
Cada gráfico plano tiene una incrustación plana y sin vínculos: simplemente incruste el gráfico en un plano e incruste el plano en el espacio. Si un gráfico es plano, esta es la única manera de incrustarlo de manera plana y sin vínculos en el espacio: cada incrustación plana se puede deformar continuamente para que quede en un plano. Y a la inversa, cada gráfico sin enlaces no plano tiene múltiples incrustaciones sin enlaces. [2]
Un gráfico de vértices , formado añadiendo un único vértice a un gráfico plano, también tiene una incrustación plana y sin vínculos: incrusta la parte plana del gráfico en un plano, coloca el vértice sobre el plano y dibuja los bordes desde el vértice hasta su vecinos como segmentos de recta. Cualquier curva cerrada dentro del plano limita un disco debajo del plano que no pasa por ninguna otra característica del gráfico, y cualquier curva cerrada a través del vértice limita un disco por encima del plano que no pasa por ninguna otra característica del gráfico. [2]
Si un gráfico tiene una incrustación plana o sin enlaces, entonces modificar el gráfico subdividiendo o dessubdividiendo sus aristas, agregando o eliminando múltiples aristas entre el mismo par de puntos y realizando transformaciones YΔ y ΔY que reemplazan un vértice de grado tres por un El triángulo que conecta a sus tres vecinos o al revés conserva la planitud y la falta de vínculos. [2] En particular, en un gráfico plano cúbico (uno en el que todos los vértices tienen exactamente tres vecinos, como el cubo) es posible hacer duplicados de cualquier conjunto independiente de vértices realizando una transformación YΔ, agregando múltiples copias de los bordes del triángulo resultantes y luego realizar las transformaciones ΔY inversas.
Si un gráfico G tiene una incrustación plana o sin enlaces, entonces cada menor de G (un gráfico formado por la contracción de aristas y la eliminación de aristas y vértices) también tiene una incrustación plana o sin enlaces. Las eliminaciones no pueden destruir la planitud de una incrustación, y se puede realizar una contracción dejando un punto final del borde contraído en su lugar y redirigiendo todos los bordes incidentes al otro punto final a lo largo de la trayectoria del borde contraído. Por lo tanto, según el teorema de Robertson-Seymour , los gráficos integrables sin enlaces tienen una caracterización de gráfico prohibido como los gráficos que no contienen ninguno de un conjunto finito de menores. [3]
Sachs (1983) identificó el conjunto de menores prohibidos para los grafos integrables sin vínculos: los siete grafos de la familia Petersen son todos grafos menores mínimos intrínsecamente vinculados. Sin embargo, Sachs no pudo demostrar que estos fueran los únicos gráficos mínimamente vinculados, y esto finalmente lo lograron Robertson, Seymour y Thomas (1995).
La caracterización menor prohibida de los gráficos sin enlaces conduce a un algoritmo de tiempo polinómico para su reconocimiento, pero no para la construcción real de una incrustación. Kawarabayashi, Kreutzer y Mohar (2010) describieron un algoritmo de tiempo lineal que prueba si un gráfico es integrable sin enlaces y, de ser así, construye una incrustación plana del gráfico. Su algoritmo encuentra subgrafos planos grandes dentro del gráfico dado, de modo que, si existe una incrustación sin enlaces, debe respetar la incrustación plana del subgrafo. Al simplificar repetidamente el gráfico cada vez que se encuentra un subgrafo de este tipo, reducen el problema a uno en el que el gráfico restante tiene un ancho de árbol acotado , momento en el que se puede resolver mediante programación dinámica .
Robertson, Seymour y Thomas (1993a) plantearon el problema de comprobar eficazmente si una determinada incrustación es plana o no tiene enlaces. Sigue sin resolverse y es equivalente en complejidad al problema de desanudar , el problema de comprobar si una sola curva en el espacio está desanudado. [5] Se sabe que la prueba de falta de nudos (y, por lo tanto, también, la prueba de falta de vínculos de una incrustación) se realiza en NP , pero no se sabe que sea NP completa . [9]
El invariante del gráfico de Colin de Verdière es un número entero definido para cualquier gráfico utilizando la teoría de grafos algebraica . Las gráficas con invariante de Colin de Verdière como máximo μ, para cualquier constante fija μ, forman una familia menor-cerrada, y las primeras son bien conocidas: las gráficas con μ ≤ 1 son los bosques lineales (uniones disjuntas de caminos), las gráficas con μ ≤ 2 son las gráficas planas externas y las gráficas con μ ≤ 3 son las gráficas planas . Como conjeturaron Robertson, Seymour y Thomas (1993a) y demostraron Lovász y Schrijver (1998), las gráficas con μ ≤ 4 son exactamente gráficas integrables sin enlaces.
Los gráficos planos y los gráficos de vértices se pueden integrar sin vínculos, al igual que los gráficos obtenidos mediante transformaciones YΔ y ΔY a partir de estos gráficos. [2] Los gráficos reducibles YΔY son los gráficos que se pueden reducir a un solo vértice mediante transformaciones YΔ y ΔY, eliminación de vértices aislados y vértices de grado uno, y compresión de vértices de grado dos; también son cerrados menores e incluyen todos los gráficos planos. Sin embargo, existen gráficos sin enlaces que no son reducibles por YΔY, como el gráfico de vértices formado conectando un vértice a cada vértice de grado tres de un dodecaedro rómbico . [10] También existen gráficos sin vínculos que no se pueden transformar en un gráfico de vértices mediante transformación YΔ y ΔY, eliminación de vértices aislados y vértices de grado uno, y compresión de vértices de grado dos: por ejemplo, la corona de diez vértices El gráfico tiene una incrustación sin enlaces, pero no se puede transformar en un gráfico de vértice de esta manera. [2]
Relacionado con el concepto de incrustación sin enlaces está el concepto de incrustación sin nudos, una incrustación de un gráfico de tal manera que ninguno de sus ciclos simples forme un nudo no trivial . Las gráficas que no tienen incrustaciones sin nudos (es decir, están intrínsecamente anudadas ) incluyen K 7 y K 3,3,1,1 . [11] Sin embargo, también existen menores mínimos prohibidos para incrustaciones sin nudos que no se forman (como estos dos gráficos) agregando un vértice a un gráfico intrínsecamente vinculado, pero se desconoce la lista de estos. [12]
También se pueden definir familias de gráficos por la presencia o ausencia de nudos y vínculos más complejos en sus incrustaciones, [13] o por incrustaciones sin vínculos en variedades tridimensionales distintas del espacio euclidiano. [14] Flapan, Naimi y Pommersheim (2001) definen la incrustación de un gráfico como triplemente enlazada si hay tres ciclos, ninguno de los cuales puede separarse de los otros dos; muestran que K 9 no está intrínsecamente triplemente enlazado, pero K 10 sí lo está. [15] De manera más general, se puede definir una incrustación ligada a n para cualquier n como una incrustación que contiene un enlace de n componentes que no puede separarse mediante una esfera topológica en dos partes separadas; Los gráficos mínimos menores que están intrínsecamente vinculados a n son conocidos para todos los n . [dieciséis]
La cuestión de si K 6 tiene una incrustación plana o sin enlaces fue planteada dentro de la comunidad de investigación de topología a principios de la década de 1970 por Bothe (1973). Horst Sachs (1983) llamó la atención de la comunidad de teoría de grafos sobre las incrustaciones sin enlaces , quien planteó varios problemas relacionados, incluido el problema de encontrar una caracterización de gráficos prohibidos para los gráficos con incrustaciones planas y sin enlaces; Sachs demostró que los siete gráficos de la familia Petersen (incluido K 6 ) no tienen tales incrustaciones. Como observaron Nešetřil y Thomas (1985), los gráficos integrables sin enlaces están cerrados bajo gráficos menores , de lo que se deduce por el teorema de Robertson-Seymour que existe una caracterización de grafo prohibido. La prueba de la existencia de un conjunto finito de grafos de obstrucción no conduce a una descripción explícita de este conjunto de menores prohibidos, pero de los resultados de Sachs se desprende que los siete grafos de la familia Petersen pertenecen a ese conjunto. Estos problemas fueron finalmente resueltos por Robertson, Seymour y Thomas (1995), [17] quienes demostraron que los siete gráficos de la familia Petersen son los únicos menores mínimos prohibidos para estos gráficos. Por lo tanto, los gráficos integrables sin enlaces y los gráficos integrables planos son el mismo conjunto de gráficos y ambos son iguales que los gráficos que no tienen familia Petersen menor.
Sachs (1983) también pidió límites para el número de aristas y el número cromático de gráficos integrables sin enlaces. El número de aristas en un gráfico sin vínculos de n -vértices es como máximo 4 n − 10: los gráficos de vértices máximos con n > 4 tienen exactamente esta cantidad de aristas, [1] y Mader (1968) demostró un límite superior coincidente en la clase más general de K 6 -gráficos libres menores. Nešetřil y Thomas (1985) observaron que la pregunta de Sachs sobre el número cromático se resolvería mediante una prueba de la conjetura de Hadwiger de que cualquier k -gráfico cromático tiene como menor un k -gráfico completo de vértice. La prueba de Robertson, Seymour y Thomas (1993c) del caso k = 6 de la conjetura de Hadwiger es suficiente para resolver la cuestión de Sachs: los gráficos sin enlaces pueden colorearse con un máximo de cinco colores, ya que cualquier gráfico 6 cromático contiene un K 6 menor y no está sin enlaces, y existen gráficos sin enlaces como K 5 que requieren cinco colores. El teorema de snark implica que todo gráfico cúbico integrable sin enlaces es coloreable en 3 aristas .
Las incrustaciones sin enlaces comenzaron a estudiarse dentro de la comunidad de investigación de algoritmos a finales de la década de 1980 a través de los trabajos de Fellows y Langston (1988) y Motwani, Raghunathan y Saran (1988). Algorítmicamente, el problema de reconocer gráficos incrustables planos y sin enlaces se resolvió una vez que se demostró la caracterización del menor prohibido: se puede utilizar un algoritmo de Robertson y Seymour (1995) para probar en tiempo polinomial si un gráfico determinado contiene alguno de los siete menores prohibidos. [18] Este método no construye incrustaciones planas o sin enlaces cuando existen, pero van der Holst (2009) desarrolló un algoritmo que sí construye una incrustación, y Kawarabayashi, Kreutzer y Mohar (2009) encontraron un algoritmo de tiempo lineal más eficiente ( 2010).
Una última pregunta de Sachs (1983) sobre la posibilidad de un análogo del teorema de Fáry para grafos sin enlaces parece no haber sido respondida: ¿cuándo la existencia de una incrustación plana o sin enlaces con bordes lineales curvos o por partes implica la existencia de un gráfico sin enlaces o ¿Incrustación plana en la que los bordes son segmentos de línea recta ?