En la teoría de grafos topológicos , un gráfico de 1 plano es un gráfico que se puede dibujar en el plano euclidiano de tal manera que cada borde tiene como máximo un punto de cruce, donde cruza un solo borde adicional. Si un gráfico de 1 plano, una de las generalizaciones más naturales de los gráficos planos , se dibuja de esa manera, el dibujo se llama gráfico de 1 plano o incrustación de 1 plano del gráfico .
Colorear [ editar ]
Los gráficos de 1 plano fueron estudiados por primera vez por Ringel (1965) , quien demostró que se pueden colorear con un máximo de siete colores. [1] Más tarde, se demostró que el número preciso de colores necesarios para colorear estos gráficos, en el peor de los casos, era seis. [2] El ejemplo del gráfico completo K 6 , que es 1 plano, muestra que los gráficos 1 plano a veces pueden requerir seis colores. Sin embargo, la prueba de que seis colores siempre son suficientes es más complicada.
La motivación de Ringel fue tratar de resolver una variación de coloración total para gráficos planos , en el que uno colorea simultáneamente los vértices y las caras de un gráfico plano de tal manera que no haya dos vértices adyacentes que tengan el mismo color, ni dos caras adyacentes tengan el mismo color, y ningún vértice y cara adyacentes tienen el mismo color. Obviamente, esto se puede hacer usando ocho colores aplicando el teorema de cuatro colores al gráfico dado y su gráfico dualpor separado, utilizando dos conjuntos disjuntos de cuatro colores. Sin embargo, se pueden obtener menos colores formando un gráfico auxiliar que tenga un vértice para cada vértice o cara del gráfico plano dado, y en el que dos vértices del gráfico auxiliar sean adyacentes siempre que correspondan a características adyacentes del gráfico plano dado. Una coloración de vértice del gráfico auxiliar corresponde a una coloración de la cara del vértice del gráfico plano original. Este gráfico auxiliar es 1 plano, de lo que se deduce que el problema de coloración de la cara del vértice de Ringel también se puede resolver con seis colores. [2] El gráfico K 6no puede formarse como un gráfico auxiliar de esta manera, pero sin embargo, el problema de coloración de la cara del vértice a veces también requiere seis colores; por ejemplo, si el gráfico plano que se va a colorear es un prisma triangular , entonces sus once vértices y caras requieren seis colores, porque a tres de ellos no se les puede dar un solo color. [3]
Densidad de borde [ editar ]
Cada gráfica de 1 plano con n vértices tiene como máximo 4 n - 8 aristas. [4] Más fuertemente, cada dibujo de 1 plano tiene como máximo n - 2 cruces ; eliminar un borde de cada par de bordes cruzados deja un gráfico plano, que puede tener como máximo 3 n - 6 bordes, del cual sigue inmediatamente el 4 n - 8 unido al número de bordes en el gráfico original de 1 plano. [5] Sin embargo, a diferencia de los gráficos planos (para los cuales todos los gráficos planos máximos en un conjunto de vértices dado tienen el mismo número de aristas que los demás), existen valores máximosGráficos de 1 planar (gráficos a los que no se pueden agregar bordes adicionales mientras se conserva la 1 planaridad) que tienen significativamente menos de 4 n - 8 bordes. [6] El límite de 4 n - 8 en el número máximo posible de aristas en un gráfico de 1 plano puede usarse para mostrar que el gráfico completo K 7 en siete vértices no es de 1 plano, porque este gráfico tiene 21 aristas y en este caso 4 n - 8 = 20 <21 .="" font="" nbsp="">[7]
Se dice que un gráfico de 1 plano es un gráfico de 1 plano óptimo si tiene exactamente 4 n - 8 aristas, el máximo posible. En una incrustación de 1 plano de un gráfico óptimo de 1 plano, los bordes no cruzados necesariamente forman una cuadrangulación (un gráfico poliédrico en el que cada cara es un cuadrilátero ). Cada cuadrangulación da lugar a un gráfico óptimo de 1 plano de esta manera, al agregar las dos diagonales a cada una de sus caras cuadriláteras. Se deduce que cada gráfico óptimo de 1 plano es euleriano (todos sus vértices tienen un grado par), que el grado mínimo en dicho gráfico es seis, y que cada gráfico óptimo de 1 plano tiene al menos ocho vértices de grado exactamente seis. Además, cada gráfico óptimo de 1 plano está conectado a 4 vértices , y cada corte de 4 vértices en dicho gráfico es un ciclo de separación en la cuadrangulación subyacente. [8]
Los gráficos que tienen dibujos rectos de 1 plano (es decir, dibujos en los que cada borde está representado por un segmento de línea, y en el que cada segmento de línea está cruzado como máximo por otro borde) tienen un límite ligeramente más apretado de 4 n - 9 en el número máximo de aristas, alcanzado por infinitos gráficos. [9]
Gráficos multipartitos completos [ editar ]
Se conoce una clasificación completa de los gráficos completos de 1 plano , gráficos bipartitos completos y, en general, gráficos multipartitos completos . Cada gráfico bipartito completo de la forma K 2, n es 1 plano, como lo es cada gráfico tripartito completo de la forma K 1,1, n . Además de estos conjuntos infinitos de ejemplos, los únicos gráficos completos de 1 plano multipartito son K 6 , K 1,1,1,6 , K 1,1,2,3 , K 2,2,2,2 , K 1, 1,1,2,2, y sus subgrafos. Los gráficos multipartitos completos no planos 1 mínimos son K 3,7 , K 4,5 , K 1,3,4 , K 2,3,3 y K 1,1,1,1,3 . Por ejemplo, el gráfico bipartito completo K 3,6 es 1 plano porque es un subgrafo de K 1,1,1,6 , pero K 3,7 no es 1 plano. [7]
Complejidad computacional [ editar ]
Es NP-complete para probar si un gráfico dado es 1-planar, [10] [11] y sigue siendo NP-complete incluso para los gráficos formados a partir de gráficos planos agregando un solo borde [12] y para gráficos de ancho de banda acotado . [13] El problema es el parámetro fijo manejable cuando se parametriza por número ciclomático o por profundidad de árbol , por lo que puede resolverse en tiempo polinómico cuando esos parámetros están limitados. [13]
En contraste con el teorema de Fáry para gráficos planos, no todos los gráficos de 1 plano se pueden dibujar de 1 plano con segmentos de línea recta para sus bordes. [14] [15] Sin embargo, la prueba de si un dibujo de 1 plano se puede enderezar de esta manera se puede hacer en tiempo polinómico . [16] Además, cada gráfico de 1 plano conectado a 3 vértices tiene un dibujo de 1 plano en el que, como máximo, un borde, en la cara exterior del dibujo, tiene una curva . Este dibujo se puede construir en tiempo lineal a partir de una incrustación de 1 plano del gráfico. [17] Los gráficos de 1 plano tienen grosor de libro acotado , [18]pero algunas gráficas planas 1 que incluyen K 2,2,2,2 tienen un grosor de libro de al menos cuatro. [19]
Los gráficos de 1 plano tienen un ancho de árbol local acotado , lo que significa que hay una función (lineal) f tal que los gráficos de 1 plano de diámetro d tienen un ancho de árbol como máximo f ( d ); la misma propiedad se aplica más generalmente a los gráficos que se pueden incrustar en una superficie de género limitado con un número limitado de cruces por borde. También tienen separadores , pequeños conjuntos de vértices cuya eliminación descompone el gráfico en componentes conectados cuyo tamaño es una fracción constante del tamaño de todo el gráfico. En base a estas propiedades, numerosos algoritmos para gráficos planos, como la técnica de Baker para diseñaralgoritmos de aproximación , pueden extenderse a gráficos de 1 plano. Por ejemplo, este método conduce a un esquema de aproximación de tiempo polinómico para el conjunto máximo independiente de un gráfico de 1 plano. [20]
[ editar ]
La clase de gráficas análogas a las gráficas planas externas para 1-planaridad se llaman gráficas 1-planar externas . Estos son gráficos que se pueden dibujar en un disco, con los vértices en el límite del disco y, como máximo, un cruce por borde. Estos gráficos siempre se pueden dibujar (de forma externa-1-plana) con bordes rectos y cruces de ángulo recto . [21] Al utilizar la programación dinámica en el árbol SPQR de un gráfico dado, es posible probar si es exterior-1-plano en tiempo lineal . [22] [23] Los componentes triconéctados del gráfico (nodos del árbol SPQR) pueden consistir solo en gráficos de ciclo ,gráficos de enlace y gráficos completos de cuatro vértices , de los cuales también se deduce que los gráficos exteriores-1-planos son planos y tienen un ancho de árbol como máximo tres.
Los gráficos de 1 plano incluyen los gráficos de 4 mapas , gráficos formados a partir de las adyacencias de regiones en el plano con un máximo de cuatro regiones reunidas en cualquier punto. Por el contrario, cada gráfico óptimo de 1 plano es un gráfico de 4 mapas. Sin embargo, los gráficos de 1 plano que no son óptimos de 1 plano pueden no ser gráficos de mapa. [24]
Los gráficos de 1 plano se han generalizado a gráficos de k planos, gráficos para los que se cruza cada borde en la mayoría de las veces k (los gráficos de 0 planos son exactamente los gráficos planos). Ringel definió que el número de cruce local de G es el número entero k no menos negativo tal que G tiene un dibujo k -plano. Debido a que el número de cruce local es el grado máximo del gráfico de intersección de los bordes de un dibujo óptimo, y el grosor (número mínimo de gráficos planos en los que se pueden dividir los bordes) puede verse como el número cromáticode un gráfico de intersección de un dibujo apropiado, del teorema de Brooks se deduce que el grosor es como máximo uno más el número de cruce local. [25] Los gráficos k -planar con n vértices tienen como máximo O ( k 1/2 n ) aristas, [26] y el ancho del árbol O (( kn ) 1/2 ). [27] Un menor superficial de un gráfico k -planar, con profundidad d , es en sí mismo un gráfico (2 d + 1) k -planar, por lo que los menores superficiales de los gráficos 1-planar y de kLas gráficas planas también son gráficas dispersas , lo que implica que las gráficas planar 1 y k tienen una expansión limitada . [28]
Los gráficos no planos también se pueden parametrizar por su número de cruce , el número mínimo de pares de bordes que se cruzan en cualquier dibujo del gráfico. Un gráfico con el número de cruce k es necesariamente k -planar, pero no necesariamente viceversa. Por ejemplo, el gráfico de Heawood tiene el número de cruce 3, pero no es necesario que sus tres cruces ocurran en el mismo borde del gráfico, por lo que es 1 plano y, de hecho, se puede dibujar de una manera que optimice simultáneamente El número total de cruces y los cruces por borde.
Otro concepto relacionado para los gráficos no planos es el sesgo del gráfico , el número mínimo de aristas que deben eliminarse para hacer un gráfico plano.
emparejamiento tridimensional es una generalización del emparejamiento bipartito (también conocido como emparejamiento bidimensional) a hipergrafías de 3 uniformes . Encontrar una coincidencia tridimensional más grande es un problema NP-hard bien conocido en la teoría de la complejidad computacional .
Emparejamientos tridimensionales. (a) de entrada T . (b) - (c) Soluciones.
Definición [ editar ]
Deje que X , Y , y Z es finito, conjuntos disjuntos, y dejar que T sea un subconjunto de X × Y × Z . Es decir, T consiste en triples ( x , y , z ) tal que x ∈ X , y ∈ Y , y z ∈ Z . Ahora M ⊆ T es una coincidencia tridimensional si se cumple lo siguiente: para dos triples distintos ( x 1 , y 1 , z1 ) ∈ M y ( x 2 , y 2 , z 2 ) ∈ M , tenemos x 1 ≠ x 2 , y 1 ≠ y 2 , y z 1 ≠ z 2 .
Ejemplo [ editar ]
La figura de la derecha ilustra los emparejamientos tridimensionales. El conjunto X está marcado con puntos rojos, Y está marcado con puntos azules y Z está marcado con puntos verdes. La figura (a) muestra el conjunto T (áreas grises). La figura (b) muestra una M tridimensional que coincide con | M | = 2, y la Figura (c) muestra una M tridimensional que coincide con | M | = 3.
La coincidencia M ilustrada en la figura (c) es una coincidencia tridimensional máxima , es decir, maximiza | M | El juego se ilustra en las figuras (b) - (c) son máximas matchings 3-dimensionales , es decir, no pueden ser extendidos por la adición de más elementos de T .
Aquí hay un ejemplo de visualización interactiva en javascript
Comparación con coincidencia bipartita [ editar ]
Una coincidencia bidimensional se puede definir de una manera completamente análoga. Deje que X e Y sean finitos, conjuntos disjuntos, y dejar que T sea un subconjunto de X × Y . Ahora M ⊆ T es una coincidencia bidimensional si se cumple lo siguiente: para dos pares distintos ( x 1 , y 1 ) ∈ M y ( x 2 , y 2 ) ∈ M , tenemos x 1 ≠ x 2 e y 1 ≠ y2 .
En el caso de la coincidencia bidimensional, el conjunto T puede interpretarse como el conjunto de aristas en un gráfico bipartito G = ( X , Y , T ); cada borde en T se conecta un vértice en X a un vértice en Y . Una coincidencia bidimensional es entonces una coincidencia en el gráfico G , es decir, un conjunto de aristas no adyacentes por pares.
Por lo tanto, los emparejamientos tridimensionales se pueden interpretar como una generalización de emparejamientos con hipergrafías: los conjuntos X , Y y Z contienen los vértices, cada elemento de T es una hiperedificación, y el conjunto M consiste en bordes no adyacentes por pares (bordes que no tienen un vértice común). En caso de emparejamiento bidimensional, tenemos Y = Z.
Comparación con el conjunto de embalaje [ editar ]
Una coincidencia tridimensional es un caso especial de un conjunto de conjuntos : podemos interpretar cada elemento ( x , y , z ) de T como un subconjunto { x , y , z } de X ∪ Y ∪ Z ; entonces una M coincidente tridimensional consiste en subconjuntos separados por pares.
Problema de decisión [ editar ]
En la teoría de la complejidad computacional, la coincidencia tridimensional es también el nombre del siguiente problema de decisión : dado un conjunto T y un entero k , decida si existe una coincidencia tridimensional M ⊆ T con | M | ≥ k .
Se sabe que este problema de decisión es NP-completo ; Es uno de los 21 problemas de NP completos de Karp . [1] Sin embargo, existen algoritmos de tiempo polinomiales para ese problema para hipergrafías densas. [2] [3]
El problema es NP-completo incluso en el caso especial de que k = | X | = | Y | = | Z |. [1] [4] [5] En este caso, una coincidencia tridimensional (dominante) no es solo un conjunto de conjuntos sino también una cubierta exacta : el conjunto M cubre cada elemento de X , Y y Z exactamente una vez. [6]
Problema de optimización [ editar ]
Una coincidencia tridimensional máxima es una coincidencia tridimensional más grande. En la teoría de la complejidad computacional, este también es el nombre del siguiente problema de optimización : dado un conjunto T , encuentre una coincidencia tridimensional M ⊆ T que maximice | M | .
Dado que el problema de decisión descrito anteriormente es NP-completo, este problema de optimización es NP-hard y, por lo tanto, parece que no existe un algoritmo de tiempo polinómico para encontrar una coincidencia tridimensional máxima. Sin embargo, existen algoritmos eficientes de tiempo polinómico para encontrar una coincidencia bipartita máxima (coincidencia bidimensional máxima), por ejemplo, el algoritmo Hopcroft-Karp .
Algoritmos de aproximación [ editar ]
El problema es APX-complete , es decir, es difícil de aproximar dentro de alguna constante. [7] [8] [9] Sin embargo, para cualquier constante ε> 0 hay un algoritmo de aproximación de tiempo polinómico (4/3 + ε) para la correspondencia tridimensional. [10]
Existe un algoritmo de aproximación tridimensional de tiempo polinómico muy simple para la coincidencia tridimensional: encuentre cualquier coincidencia tridimensional máxima. [9] Al igual que una coincidencia máxima está dentro del factor 2 de una coincidencia máxima, [11] una coincidencia tridimensional máxima está dentro del factor 3 de una coincidencia tridimensional máxima.
No hay comentarios:
Publicar un comentario