En la teoría de grafos topológicos , una disciplina matemática, una incrustación sin enlaces de un grafo no dirigido es una incrustación del grafo en un espacio euclidiano tridimensional de tal manera que no hay dos ciclos del grafo 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 es disjunto del grafo. Un grafo incrustable sin enlaces es un grafo que tiene una incrustación sin enlaces o plana; estos grafos forman un análogo tridimensional de los grafos planares . [1] Complementariamente, un grafo intrínsecamente vinculado es un grafo que no tiene una incrustación sin enlaces.
Las incrustaciones planas son automáticamente sin enlaces, pero no al revés. [2] El grafo completo K 6 , el grafo de Petersen y los otros cinco grafos de la familia Petersen no tienen incrustaciones sin enlaces. [1] Todo grafo menor de un grafo sin enlaces incrustable es a su vez sin enlaces incrustable, [3] al igual que todo grafo al que se puede llegar desde un grafo sin enlaces incrustable mediante transformaciones YΔ y ΔY . [2] Los grafos sin enlaces incrustables tienen a los grafos de la familia Petersen como sus menores prohibidos , [4] e incluyen los grafos planares y los grafos de vértice . [2] Se pueden reconocer, y se puede construir una incrustación plana para ellos, en O ( n 2 ) . [5]
Cuando el círculo se mapea al espacio euclidiano tridimensional por una función inyectiva (una función continua que no mapea dos puntos diferentes del círculo al mismo punto del espacio), su imagen es una curva cerrada . Dos curvas cerradas disjuntas que se encuentran ambas en el mismo plano están desvinculadas y, de manera más general, se dice que un par de curvas cerradas disjuntas está desvinculado cuando hay una deformación continua del espacio que las mueve a ambas sobre el mismo plano, sin que ninguna de las curvas pase por la otra o por sí misma. Si no hay tal movimiento continuo, se dice que las dos curvas están vinculadas . Por ejemplo, el vínculo de Hopf está formado por dos círculos que pasan cada uno por el disco abarcado por el otro. Forma el ejemplo más simple de un par de curvas vinculadas, pero es posible que las curvas estén vinculadas 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 su límite y disjunto de la segunda curva. Por el contrario, si tal disco existe, las curvas están necesariamente desvinculadas.
El número de enlace de dos curvas cerradas en el espacio tridimensional es un invariante topológico de las curvas: es un número, definido a partir de las curvas de varias maneras equivalentes, que no cambia si las curvas se mueven continuamente sin pasar una a través de la otra. La versión del número de enlace utilizado para definir incrustaciones sin enlace de grafos se encuentra proyectando la incrustación sobre el plano y contando el número de cruces de la incrustación proyectada en la que la primera curva pasa sobre la segunda, módulo 2. [2] 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 proyecta al interior de una arista, y en cada punto de la proyección donde las proyecciones de dos aristas se intersecan, se cruzan transversalmente ; con esta restricción, dos proyecciones cualesquiera conducen al mismo número de enlace. El número de enlace del desvío 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 enlace de Whitehead .
La incrustación de un gráfico en un espacio tridimensional consiste en una aplicación 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 asigna a un punto final de la curva correspondiente, y de modo que las curvas de dos bordes diferentes no se intersecan excepto en un punto final común de los bordes. 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 grafo puede estar incrustado en el espacio de tal manera que, para cada ciclo en el grafo, se puede encontrar un disco limitado por ese ciclo que no cruza ninguna otra característica del grafo. En este caso, el ciclo debe estar desvinculado de todos los demás ciclos disjuntos de él en el grafo. Se dice que la incrustación es plana si cada ciclo limita un disco de esta manera. [7] Una incrustación plana es necesariamente sin vínculos, pero pueden existir incrustaciones sin vínculos que no sean planas: por ejemplo, si G es un grafo formado por dos ciclos disjuntos, y está incrustado para formar el vínculo de Whitehead, entonces la incrustación es sin vínculos pero no plana.
Se dice que un grafo está intrínsecamente vinculado si, sin importar cómo esté incrustado, la incrustación siempre está vinculada. Aunque las incrustaciones sin vínculos y las incrustaciones planas no son lo mismo, los grafos que tienen incrustaciones sin vínculos son los mismos que los grafos 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 se inserte cada uno de estos grafos en el espacio, tienen dos ciclos que están vinculados entre sí. Estos grafos incluyen el grafo completo K 6 , el grafo de Petersen , el grafo formado al eliminar una arista del grafo bipartito completo K 4,4 , y el grafo tripartito completo K 3,3,1 .
Todo grafo plano tiene una incrustación plana y sin enlaces: basta con incrustar el grafo en un plano e incrustar el plano en el espacio. Si un grafo es plano, esta es la única forma de incrustarlo de manera plana y sin enlaces en el espacio: cada incrustación plana se puede deformar continuamente para que se encuentre en un plano. Y, a la inversa, todo grafo no plano sin enlaces tiene múltiples incrustaciones sin enlaces. [2]
Un gráfico de vértice , formado mediante la adición de 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 sus vecinos como segmentos de línea. 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 sobre el plano que no pasa por ninguna otra característica del gráfico. [2]
Si un gráfico tiene una incrustación plana o sin vínculos, entonces modificar el gráfico subdividiendo o anulando la subdivisión de 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 triángulo que conecta a sus tres vecinos o lo inverso, todo preserva 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 las aristas del triángulo resultante y luego realizando las transformaciones ΔY inversas.
Si un grafo G tiene una incrustación sin enlaces o plana, entonces cada menor de G (un grafo formado por contracción de aristas y eliminación de aristas y vértices) también tiene una incrustación sin enlaces o plana. Las eliminaciones no pueden destruir la planicidad de una incrustación, y una contracción se puede realizar dejando un punto final de la arista contraída en su lugar y redireccionando todas las aristas incidentes al otro punto final a lo largo del camino de la arista contraída. Por lo tanto, por el teorema de Robertson-Seymour , los grafos incrustables sin enlaces tienen una caracterización de grafo prohibido como los grafos que no contienen ninguno de un conjunto finito de menores. [3]
El conjunto de menores prohibidos para los grafos incrustables sin enlaces fue identificado por Sachs (1983): los siete grafos de la familia Petersen son todos grafos menores-minimalistas intrínsecamente enlazados. Sin embargo, Sachs no pudo demostrar que estos fueran los únicos grafos minimales enlazados, y esto fue finalmente logrado por Robertson, Seymour y Thomas (1995).
La caracterización menor prohibida de los grafos sin enlaces conduce a un algoritmo de tiempo polinomial para su reconocimiento, pero no para construir realmente una incrustación. Kawarabayashi, Kreutzer y Mohar (2010) describieron un algoritmo de tiempo lineal que prueba si un grafo es incrustable sin enlaces y, si es así, construye una incrustación plana del grafo. Su algoritmo encuentra subgrafos planos grandes dentro del grafo dado de modo que, si existe una incrustación sin enlaces, tiene que respetar la incrustación plana del subgrafo. Al simplificar repetidamente el grafo cada vez que se encuentra un subgrafo de este tipo, reducen el problema a uno en el que el grafo restante tiene un ancho de árbol acotado , en cuyo punto se puede resolver mediante programación dinámica .
El problema de comprobar de manera eficiente si una incrustación dada es plana o sin enlaces fue planteado por Robertson, Seymour y Thomas (1993a). Sigue sin resolverse y es equivalente en complejidad al problema de desanudación , el problema de comprobar si una única curva en el espacio está desanudada. [5] Se sabe que comprobar la desanudación (y, por lo tanto, también comprobar la ausencia de enlaces de una incrustación) está en NP , pero no se sabe que sea NP-completo . [9]
El invariante del grafo de Colin de Verdière es un entero definido para cualquier grafo usando la teoría de grafos algebraicos . Los grafos con un invariante del grafo de Colin de Verdière como máximo μ, para cualquier constante fija μ, forman una familia cerrada menor, y los primeros de estos son bien conocidos: los grafos con μ ≤ 1 son los bosques lineales (uniones disjuntas de caminos), los grafos con μ ≤ 2 son los grafos planos exteriores y los grafos con μ ≤ 3 son los grafos planos . Como Robertson, Seymour y Thomas (1993a) conjeturaron y Lovász y Schrijver (1998) demostraron, los grafos con μ ≤ 4 son exactamente los grafos integrables sin enlaces.
Los grafos planares y los grafos de vértice son integrables sin enlaces, al igual que los grafos obtenidos por transformaciones YΔ y ΔY a partir de estos grafos. [2] Los grafos reducibles YΔY son los grafos 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 menores cerrados e incluyen todos los grafos planares. Sin embargo, existen grafos sin enlaces que no son reducibles YΔY, como el grafo de vértice formado conectando un vértice de vértice a cada vértice de grado tres de un dodecaedro rómbico . [10] También existen grafos sin enlaces que no se pueden transformar en un grafo de vértice mediante la transformación YΔ y ΔY, la eliminación de vértices aislados y vértices de grado uno, y la compresión de vértices de grado dos: por ejemplo, el grafo de corona de diez vértices tiene una incrustación sin enlaces, pero no se puede transformar en un grafo 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 grafo de tal manera que ninguno de sus ciclos simples forme un nudo no trivial . Los grafos que no tienen incrustaciones sin nudos (es decir, que están intrínsecamente anudados ) 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 grafos) añadiendo un vértice a un grafo intrínsecamente enlazado, pero la lista de estos es desconocida. [12]
También se pueden definir familias de grafos por la presencia o ausencia de nudos y enlaces más complejos en sus incrustaciones, [13] o por incrustaciones sin enlaces en variedades tridimensionales distintas del espacio euclidiano. [14] Flapan, Naimi y Pommersheim (2001) definen una incrustación de grafos como triplemente enlazada si hay tres ciclos de los cuales ninguno 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 n -enlazada para cualquier n como una incrustación que contiene un enlace de n -componentes que no puede separarse por una esfera topológica en dos partes separadas; los grafos mínimos menores que están intrínsecamente n -enlazados son conocidos para todos los n . [16]
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). Las incrustaciones sin enlaces fueron traídas a la atención de la comunidad de teoría de grafos por Horst Sachs (1983), quien planteó varios problemas relacionados, incluido el problema de encontrar una caracterización de grafo prohibido de los grafos con incrustaciones planas y sin enlaces; Sachs mostró que los siete grafos de la familia Petersen (incluido K 6 ) no tienen tales incrustaciones. Como observaron Nešetřil y Thomas (1985), los grafos incrustables sin enlaces están cerrados bajo los menores de grafos , 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 se deduce de los resultados de Sachs que los siete grafos de la familia Petersen pertenecen al conjunto. Estos problemas fueron finalmente resueltos por Robertson, Seymour y Thomas (1995), [17] quienes demostraron que los siete grafos de la familia Petersen son los únicos menores prohibidos mínimos para estos grafos. Por lo tanto, los grafos integrables sin enlaces y los grafos integrables planos son el mismo conjunto de grafos, y son ambos iguales a los grafos que no tienen un menor de la familia Petersen.
Sachs (1983) también pidió límites para el número de aristas y el número cromático de grafos integrables sin enlaces. El número de aristas en un grafo sin enlaces de n -vértices es como máximo 4 n − 10: los grafos de vértice máximo con n > 4 tienen exactamente esta cantidad de aristas, [1] y Mader (1968) demostró un límite superior coincidente para la clase más general de grafos libres de K 6 -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 grafo k -cromático tiene como menor un grafo completo de k -vértices. La demostración 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 grafos sin enlaces pueden colorearse con cinco colores como máximo, ya que cualquier grafo 6-cromático contiene un menor K 6 y no es sin enlaces, y existen grafos sin enlaces como K 5 que requieren cinco colores. El teorema de snark implica que todo grafo cúbico sin enlaces integrable es coloreable en 3 aristas .
Las incrustaciones sin enlaces comenzaron a estudiarse dentro de la comunidad de investigación de algoritmos a fines 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 grafos sin enlaces e incrustables planos se resolvió una vez que se demostró la caracterización de menor prohibido: un algoritmo de Robertson y Seymour (1995) se puede utilizar para probar en tiempo polinomial si un grafo dado contiene alguno de los siete menores prohibidos. [18] Este método no construye incrustaciones sin enlaces o planas cuando existen, pero van der Holst (2009) desarrolló un algoritmo que sí construye una incrustación, y Kawarabayashi, Kreutzer y Mohar (2010) encontraron un algoritmo de tiempo lineal más eficiente.
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 sin enlaces o plana con aristas curvas o lineales por partes implica la existencia de una incrustación sin enlaces o plana en la que las aristas son segmentos de línea recta ?