En teoría de grafos topológica, un embedido sin enlaces de un grafo es una incrustación del grafo en un espacio euclídeo tridimensional de tal manera que no hay dos ciclos del grafo enlazados entre sí. Un embedido plano es una incrustación con la propiedad de que cada ciclo es el límite de un disco topológico cuyo interior es disjunto con respecto al grafo. Un grafo embebible sin enlaces es un grafo que tiene un embedido plano o sin enlaces; estos grafos forman un análogo tridimensional de los grafos planos.. Complementariamente, un grafo vinculado intrínsecamente es un grafo que no tiene un embedido sin enlaces.
Los embebidos planos no tienen enlaces automáticamente, pero no al revés. El grafo completo , el grafo de Petersen y los otros cinco grafos de la familia de Petersen no tienen embebidos sin enlaces. Cada menor de un grafo integrable sin vínculos es nuevamente integrable sin vínculos, al igual que cada grafo al que se puede llegar desde un grafo integrable sin enlaces mediante el teorema de Kennelly. Los grafos integrables sin enlaces tienen los grafos de la familia de Petersen como sus menores prohibidos,. e incluyen los grafos planos y los grafos de ápice. Se pueden reconocer, y se puede construir un empotramiento plano para ellos, en .
Definiciones Cuando un círculo se asigna a un espacio euclídeo 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.
Dos curvas cerradas disjuntas que se encuentran ambas en el mismo plano están desenlazadas y, de manera más general, se dice que un par de curvas cerradas disjuntas están desvinculadas cuando existe una deformación continua del espacio capaz de mover ambas al mismo plano, sin que ninguna de las curvas atraviese a la otra o a sí misma. Si no existe tal movimiento continuo, se dice que las dos curvas están enlazadas. Por ejemplo, el enlace de Hopf está formado por dos aros que pasan cada uno por el disco interior del otro atravesándolo. Forma el ejemplo más simple de un par de curvas vinculadas, pero es posible que las curvas se vinculen de otras formas más complicadas. Si dos curvas no están vinculadas, entonces es posible encontrar un disco topológico en el espacio, teniendo la primera curva como su límite y disjunto de la segunda curva. Por el contrario, si existe tal disco, 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 en cualquiera de varias formas equivalentes, que no cambia si las curvas se mueven continuamente sin cruzarse entre sí. La versión del número de enlace utilizada para definir embebidos de grafos sin enlaces se puede hallar proyectando el embedido sobre un plano y contando el número de veces que la primera curva cruza sobre la segunda, en módulo 2.. La proyección debe ser "regular", lo que significa que dos vértices no se pueden proyectar hacia el mismo punto, ningún vértice se proyecta hacia el interior de una arista, y en cada punto de la proyección donde se cruzan las proyecciones de dos aristas, se cruzan transversalmente. Con esta restricción, dos proyecciones cualesquiera conducen al mismo número de enlace.
El número de enlace de un modelo desvinculado es cero y, por lo tanto, si un par de curvas tiene un número de vinculación distinto de cero, las dos curvas deben estar enlazadas. Sin embargo, hay ejemplos de curvas que están enlazadas pero que tienen un número de enlace cero, como el eslabón de Whitehead.
Un embedido de un grafo en un espacio tridimensional consiste en una aplicación desde los vértices del grafo a puntos en el espacio, y desde los bordes del grafo a curvas en el espacio, de modo que cada punto final de cada borde se aplica a un punto final de la curva correspondiente, y tal que las curvas de dos aristas diferentes no se cortan excepto en un punto final común de las aristas.
Cualquier grafo finito tiene un número finito (aunque puede ser exponencial) de ciclos simples distintos, y si el grafo está embebido en un espacio tridimensional, 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 el embedido no tiene enlaces.;;.
En algunos casos, un grafo puede estar incrustado en el espacio de tal manera que, para cada ciclo del grafo, se puede encontrar un disco delimitado por ese ciclo que no cruza a ningún otro elemento del grafo. En este caso, el ciclo debe estar desvinculado de todos los demás ciclos separados de él en el grafo. Se dice que el embedido es plano si cada ciclo limita un disco de esta manera.. Una definición similar de "buena incrustación" figura en ; véase también y . Un embedido plano no tiene enlaces necesariamente, pero pueden existir embebidos sin enlaces que no son planos: por ejemplo, si G es un grafo formado por dos ciclos disjuntos, y está embebido para formar el enlace de Whitehead, entonces el embedido no tiene enlaces pero no es plano.
Se dice que un grafo está intrínsecamente enlazado si, independientemente de cómo esté embebido, el embedido resultante siempre está enlazado. Aunque los embebidos planos y sin enlaces no son lo mismo, los grafos que tienen embebidos sin enlaces son los mismos que los grafos que tienen embebidos planos..
Ejemplos y contraejemplos
Como mostró , cada uno de los siete grafos de la familia de Petersen están intrínsecamente enlazados: no importa cómo cada uno de estos grafos esté embebido en el espacio, siempre tienen dos ciclos que están vinculados entre sí. Estos grafos incluyen el grafo completo K6, el grafo de Petersen, el grafo formado al eliminar un borde del grafo bipartito completo K4,4 y el grafo tripartito completo K3,3,1.
Cada grafo plano tiene un embedido plano y sin enlaces: simplemente debe embeberse el grafo en un plano y embeber a su vez el plano en el espacio. Si un grafo es plano, esta es la única forma de embeberlo de forma plana y sin enlaces en el espacio: cada embedido plano puede deformarse continuamente para que quede en un plano. Y a la inversa, cada grafo sin enlaces no plano posee múltiples embebidos sin enlaces.
Un grafo de ápice, formado al agregar un solo vértice a un grafo plano, también tiene un embedido plano y sin enlaces: para comprobarlo, basta embeber la parte plana del grafo en un plano, colocar el ápice sobre el plano y dibujar las aristas desde el ápice hasta sus vecinos como segmentos de línea recta. Cualquier curva cerrada dentro del plano delimita un disco por debajo del plano que no pasa por ningún otro elemento del grafo, y cualquier curva cerrada a través del ápice delimita un disco por encima del plano que no pasa por ningún otro elemento del grafo.
Si un grafo se puede transformar en un embedido plano o sin enlaces, entonces se puede modificar el grafo subdividiendo o dessubdividiendo sus aristas, agregando o eliminando múltiples aristas entre el mismo par de vértices y aplicando el teorema de Kennelly (que permite reemplazar un vértice de grado tres por un triángulo que conecta los tres vecinos o al revés), de manera que siempre se conserva la planitud y la ausencia de enlaces. En particular, en un grafo plano cúbico (uno en el que todos los vértices tienen exactamente tres vecinos, como en un cubo) es posible hacer duplicados de cualquier conjunto independiente de vértices realizando transformaciones Y-Δ, agregando múltiples copias de los triángulos de aristas resultantes, y luego realizar las transformadas inversas Δ-Y.
Identificación y caracterización Si un grafo G tiene un embedido plano o sin enlaces, entonces cada menor de G (un grafo formado por la contracción de las aristas y la eliminación de aristas y vértices) también tiene un embedido plano o sin enlaces. Las eliminaciones no pueden destruir la planitud de un embedido, y se puede realizar una contracción dejando un punto final del borde contraído en su lugar y redirigiendo todos los bordes incidentes a otro punto final en la ruta del borde contraído. Por lo tanto, por el teorema de Robertson–Seymour, los grafos integrables sin enlaces tienen una caracterización de grafo prohibida como los grafos que no contienen ningún elemento de un conjunto finito de menores.
El conjunto de menores prohibidos para los grafos embebibles sin enlaces fue identificado por : los siete grafos de la familia de Petersen son todos grafos menores-mínimos intrínsecamente vinculados. Sin embargo, Sachs no pudo probar que estos fueran los únicos grafos vinculados mínimos, aunque finalmente logró demostrarlo.
La caracterización menor prohibida de los grafos sin enlaces conduce a un algoritmo de tiempo lineal para su identificación, pero no para construir realmente un embedido. describió un algoritmo de tiempo lineal que comprueba si un grafo se puede embeber sin enlaces y, de ser así, construye un embedido plano del grafo. Su algoritmo encuentra grandes subgrafos planos dentro del grafo dado de tal manera que, si existe un embedido sin enlace, debe respetar el embedido plano 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 ha acotado la anchura del árbol, en cuyo punto puede resolverse mediante un procedimiento de programación dinámica. planteó el problema de comprobar de manera eficiente si un embedido dado es plano o sin enlaces. Sigue sin resolverse, y es equivalente en complejidad a un problema de desanudamiento, el problema de probar si una sola curva en el espacio no está anudada. Se sabe que la prueba de ausencia de nudos (y, por lo tanto, también la prueba de falta de enlace de un embedido) es de dificultad NP, pero no se sabe que sea NP-completo..
Familias relacionadas de grafos El invariante de grafo de Colin de Verdière es un número entero definido para cualquier grafo definido mediante la teoría de grafos algebraicos. Los grafos con invariante de Colin de Verdière a lo sumo μ, para cualquier constante fija μ, forman una familia menor-cerrada, y los primeros son bien conocidos: los grafos con μ ≤ 1 son los bosques lineales (uniones disjuntas de caminos), los grafos con μ ≤ 2 son los grafos no planos, y los grafos con μ ≤ 3 son los grafos planos. Como conjeturó y demostró , los grafos con μ ≤ 4 son exactamente los grafos integrables sin enlaces.
Los grafos planos y los grafos de ápice se pueden embeber sin enlaces, al igual que los grafos obtenidos por el teorema de Kennelly a partir de estos grafos. Los grafos reducibles YΔY son aquellos que se pueden reducir a un solo vértice mediante transformadas 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 grafos planos. Sin embargo, existen grafos sin enlaces que no son reducibles con YΔY, como el grafo de ápice formado al conectar el ápice a cada vértice de grado tres de un rombododecaedro.. También existen grafos sin enlaces que no se pueden transformar en un grafo de ápice mediante transformaciones Y-Δ, eliminación de vértices aislados y vértices de grado uno, y compresión de vértices de grado dos: por ejemplo, el grafo en corona de diez vértices tiene un embedido sin enlace, pero no se puede transformar en un grafo de ápice de esta manera.