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]
Cuando el círculo se asigna al espacio euclidiano tridimensional mediante una función inyectiva (una función continua que no asigna dos puntos diferentes del círculo al mismo punto del espacio), su imagen es una curva cerrada . Dos curvas cerradas disjuntas que se encuentran en el mismo plano están desvinculadas y, de manera más general, se dice que un par de curvas cerradas disjuntas están desvinculadas cuando hay una deformación continua del espacio que las mueve a ambas hacia el mismo plano, sin que ninguna de las curvas pase por ellas. el otro o a través de sí mismo. Si no existe tal movimiento continuo, se dice que las dos curvas están unidas . Por ejemplo, el enlace de Hopf está formado por dos círculos que pasan cada uno a través del disco abarcado por el otro. Constituye el ejemplo más simple de un par de curvas vinculadas, pero es posible vincular las curvas de otras formas más complicadas. Si dos curvas no están vinculadas, entonces es posible encontrar un disco topológico en el espacio, que tenga la primera curva como límite y esté separado de la segunda curva. Por el contrario, si existe un disco de este tipo, las curvas necesariamente están desvinculadas.
El número de enlace de dos curvas cerradas en un espacio tridimensional es una invariante topológica de las curvas: es un número, definido a partir de las curvas en cualquiera de varias formas equivalentes, que no cambia si las curvas se mueven continuamente sin pasar por una de ellas. otro. La versión del número de enlace utilizado para definir incrustaciones de gráficos sin enlaces se encuentra proyectando la incrustación en el plano y contando el número de cruces de la incrustación proyectada en los que la primera curva pasa sobre la segunda, módulo 2. [2] La la proyección debe ser "regular", lo que significa que no hay dos vértices que se proyecten al mismo punto, ningún vértice se proyecte al interior de un borde, y en cada punto de la proyección donde se cruzan las proyecciones de dos bordes, se cruzan transversalmente ; con esta restricción, dos proyecciones cualesquiera conducen al mismo número de enlace. El número de enlace de la desvinculación es cero y, por lo tanto, si un par de curvas tiene un número de enlace distinto de cero, las dos curvas deben estar enlazadas. Sin embargo, hay ejemplos de curvas que están vinculadas pero que tienen un número de enlace cero, como el vínculo de Whitehead .
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 limitado 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 necesariamente tiene vínculos, pero pueden existir incrustaciones sin vínculos que no son 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 enlaces: 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 no plano sin vínculos tiene múltiples incrustaciones sin vínculos. [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 única curva en el espacio está desanudada. [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 grafos menores , de lo que se deduce por el teorema de Robertson-Seymour que existe una caracterización de grafos prohibidos. 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 polinómico si un gráfico dado 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 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 vínculos parece no haber sido respondida: ¿cuándo la existencia de una incrustación plana o sin vínculos con bordes lineales curvos o por tramos implica la existencia de un gráfico sin vínculos o ¿Incrustación plana en la que los bordes son segmentos de línea recta ?