En matemáticas combinatorias , una red apolínea es un gráfico no dirigido formado por un proceso de subdivisión recursiva de un triángulo en tres triángulos más pequeños. Las redes apolíneas pueden definirse de manera equivalente como los 3 árboles planos , los gráficos cordales planos máximos, los gráficos planos de 4 colores únicos y los gráficos de politopos apilados . Llevan el nombre de Apolonio de Perga , quien estudió una construcción de embalaje circular relacionada.
Se puede formar una red apolínea, a partir de un solo triángulo incrustado en el plano euclidiano , seleccionando repetidamente una cara triangular de la incrustación, agregando un nuevo vértice dentro de la cara y conectando el nuevo vértice a cada vértice de la cara que lo contiene. De esta forma, el triángulo que contiene el nuevo vértice se subdivide en tres triángulos más pequeños, que a su vez podrán subdividirse de la misma forma.
Los gráficos completos de tres y cuatro vértices, K 3 y K 4 , son redes apolíneas. K 3 se forma comenzando con un triángulo y sin realizar ninguna subdivisión, mientras que K 4 se forma haciendo una única subdivisión antes de detenerse.
El gráfico de Goldner-Harary es una red apolínea que forma el gráfico plano máximo no hamiltoniano más pequeño. [1] Nishizeki (1980) utilizó otra red apolínea más complicada para proporcionar un ejemplo de un gráfico plano máximo no hamiltoniano resistente a 1 .
Además de estar definidas por la subdivisión recursiva de triángulos, las redes apolíneas tienen otras caracterizaciones matemáticas equivalentes. Son los gráficos planos cordales máximos, los gráficos poliédricos cordales y los 3 árboles planos . Se trata de gráficos planos de 4 colores únicos y gráficos planos con una descomposición única de la madera de Schnyder en tres árboles. Son los gráficos planos máximos con un ancho de árbol tres, una clase de gráficos que pueden caracterizarse por sus menores prohibidos o por su reducibilidad bajo transformadas Y-Δ . Son los gráficos planos máximos con degeneración tres. También son los gráficos planos en un número determinado de vértices que tienen el mayor número posible de triángulos, el mayor número posible de subgrafos tetraédricos, el mayor número posible de camarillas y el mayor número posible de piezas después de descomponerse separando triángulos.
Las redes apolíneas son ejemplos de gráficos planos máximos , gráficos a los que no se pueden agregar aristas adicionales sin destruir la planaridad, o de manera equivalente, gráficos que se pueden dibujar en el plano de modo que cada cara (incluida la cara exterior) sea un triángulo. También son gráficos cordales , gráficos en los que cada ciclo de cuatro o más vértices tiene un borde diagonal que conecta dos vértices del ciclo no consecutivos, y el orden en el que se agregan los vértices en el proceso de subdivisión que forma una red apolínea es un orden de eliminación como un gráfico cordal. Esto forma una caracterización alternativa de las redes apolíneas: son exactamente los gráficos planos cordales máximos o, de manera equivalente, los gráficos cordales poliédricos . [2]
En una red apolínea, cada camarilla máxima es un gráfico completo de cuatro vértices, formado eligiendo cualquier vértice y sus tres vecinos anteriores. Cada separador de camarilla mínimo (una camarilla que divide el gráfico en dos subgrafos desconectados) es uno de los triángulos subdivididos. Un gráfico cordal en el que todas las camarillas máximas y todos los separadores de camarillas mínimos tienen el mismo tamaño es un k -árbol , y las redes apolíneas son ejemplos de 3 árboles. No todos los 3 árboles son planos, pero los 3 árboles planos son exactamente las redes apolíneas.
Cada red apolínea es también un gráfico exclusivo de 4 colores . Debido a que es un gráfico plano, el teorema de los cuatro colores implica que tiene un color de gráfico con solo cuatro colores, pero una vez que se seleccionan los tres colores del triángulo inicial, solo hay una elección posible para el color de cada vértice sucesivo, por lo que hasta la permutación del conjunto de colores, tiene exactamente una de 4 colores. Es más difícil de demostrar, pero también cierto, que cada gráfico plano de cuatro colores únicos es una red apolínea. Por lo tanto, las redes apolíneas también pueden caracterizarse como gráficos planos de cuatro colores únicos. [3] Las redes apolíneas también proporcionan ejemplos de gráficos planos que tienen la menor cantidad posible de k -coloraciones para k > 4 . [4]
Las redes apolíneas también son exactamente los grafos planos máximos que (una vez que se fija una cara exterior) tienen una madera de Schnyder única , una partición de los bordes del grafo en tres árboles intercalados enraizados en los tres vértices de la cara exterior. [5]
Las redes apolíneas no forman una familia de gráficos que se cierra bajo la operación de tomar grafos menores , ya que eliminar los bordes pero no los vértices de una red apolínea produce un gráfico que no es una red apolínea. Sin embargo, los 3 árboles parciales planos , subgrafos de redes apolíneas, son menores-cerrados. Por tanto, según el teorema de Robertson-Seymour , pueden caracterizarse por un número finito de menores prohibidos . Los menores mínimos prohibidos para los 3 árboles parciales planos son los cuatro gráficos mínimos entre los menores prohibidos para los gráficos planos y los 3 árboles parciales: el gráfico completo K 5 , el gráfico bipartito completo K 3,3 , el gráfico del octaedro , y la gráfica del prisma pentagonal . Las gráficas apolíneas son las gráficas máximas que no tienen ninguna de estas cuatro gráficas como menor. [6]
Una transformada Y-Δ , una operación que reemplaza un vértice de grado tres en un gráfico por un triángulo que conecta sus vecinos, es suficiente (junto con la eliminación de aristas paralelas) para reducir cualquier red apolínea a un solo triángulo y, de manera más general, la Los gráficos planos que se pueden reducir a un solo borde mediante transformaciones Y-Δ, eliminación de bordes paralelos, eliminación de vértices de grado uno y compresión de vértices de grado dos son exactamente los 3 árboles parciales planos. Los gráficos duales de los 3 árboles parciales planos forman otra familia de gráficos menores cerrados y son exactamente los gráficos planos que se pueden reducir a un solo borde mediante transformaciones Δ-Y, eliminación de bordes paralelos, eliminación de vértices de grado uno y compresión de vértices de grado dos. [7]
En cada subgrafo de una red apolínea, el vértice agregado más recientemente tiene grado como máximo tres, por lo que las redes apolíneas tienen degeneración tres. El orden en el que se agregan los vértices para crear la red es, por tanto, un orden de degeneración, y las redes apolíneas coinciden con los gráficos planos máximos de 3 degenerados.
Otra caracterización de las redes apolíneas tiene que ver con su conectividad . Cualquier gráfico plano máximo se puede descomponer en subgrafos planos máximos conectados por 4 vértices dividiéndolos a lo largo de sus triángulos separadores (triángulos que no son caras del gráfico): dado cualquier triángulo no facial: se pueden formar dos gráficos planos máximos más pequeños, uno formado por la parte interior del triángulo y el otro formado por la parte exterior del triángulo. Los gráficos planos máximos sin triángulos separadores que pueden formarse mediante divisiones repetidas de este tipo a veces se denominan bloques, aunque ese nombre también se ha utilizado para los componentes biconectados de un gráfico que no es en sí mismo biconectado. Una red apolínea es un gráfico plano máximo en el que todos los bloques son isomorfos al gráfico completo K 4 .
En la teoría de grafos extremos , las redes apolíneas también son exactamente los gráficos planos de n -vértices en los que el número de bloques alcanza su máximo, n − 3 , y los gráficos planos en los que el número de triángulos alcanza su máximo, 3 n − 8 . Dado que cada subgrafo K 4 de un gráfico plano debe ser un bloque, estos también son los gráficos planos en los que el número de subgrafos K 4 alcanza su máximo, n − 3 , y los gráficos en los que el número de camarillas de cualquier tipo alcanza su máximo. máximo, 8 norte - 16 . [8]
Las redes apolíneas llevan el nombre de Apolonio de Perge , quien estudió el problema de Apolonio de construir un círculo tangente a otros tres círculos. Un método para construir redes apolíneas es comenzar con tres círculos mutuamente tangentes y luego inscribir repetidamente otro círculo dentro del espacio formado por tres círculos previamente dibujados. La colección fractal de círculos producida de esta manera se llama junta apolínea .
Si el proceso de producción de una junta apolínea se detiene antes de tiempo, con solo un conjunto finito de círculos, entonces el gráfico que tiene un vértice para cada círculo y una arista para cada par de círculos tangentes es una red apolínea. [9] La existencia de un conjunto de círculos tangentes cuyas tangencias representan una red apolínea dada forma un ejemplo simple del teorema de empaquetado de círculos de Koebe-Andreev-Thurston , que establece que cualquier gráfico plano puede representarse mediante círculos tangentes de la misma manera. . [10]
Las redes apolíneas son gráficas planas de 3 conexos y, por lo tanto, según el teorema de Steinitz , siempre pueden representarse como gráficas de poliedros convexos . El poliedro convexo que representa una red apolínea es un politopo apilado tridimensional . Tal politopo se puede obtener a partir de un tetraedro pegando repetidamente tetraedros adicionales, uno a la vez, en sus caras triangulares. Por lo tanto, las redes apolíneas también pueden definirse como gráficos de politopos 3D apilados. [11] Es posible encontrar una representación de cualquier red apolínea como un poliedro tridimensional convexo en el que todas las coordenadas son números enteros de tamaño polinómico, mejor que lo que se conoce para otros gráficos planos. [12]
Elcock, Gargantini y Walsh (1987) investigaron la subdivisión recursiva de triángulos en tres triángulos más pequeños como técnica de segmentación de imágenes en visión por computadora ; en este contexto, la llamaron descomposición del triángulo escaleno ternario . Observaron que, al colocar cada nuevo vértice en el centroide de su triángulo circundante, se podía elegir la triangulación de tal manera que todos los triángulos tuvieran áreas iguales, aunque no todos tuvieran la misma forma. De manera más general, las redes apolíneas pueden dibujarse en el plano con cualquier área prescrita en cada cara; Si las áreas son números racionales , también lo son todas las coordenadas de los vértices. [13]
También es posible realizar el proceso de subdividir un triángulo para formar una red apolínea de tal forma que, en cada paso, las longitudes de las aristas sean números racionales; Es un problema abierto si todo gráfico plano tiene un dibujo con esta propiedad. [14] Es posible en tiempo polinómico encontrar un dibujo de un árbol de 3 planos con coordenadas enteras que minimice el área del cuadro delimitador del dibujo, y probar si un árbol de 3 planos determinado se puede dibujar con sus vértices en un conjunto dado de puntos. [15]
Plummer (1992) utilizó redes apolíneas para construir una familia infinita de gráficos planos máximos con un número par de vértices pero sin una coincidencia perfecta . Las gráficas de Plummer se forman en dos etapas. En la primera etapa, partiendo de un triángulo abc , se subdivide repetidamente la cara triangular de la subdivisión que contiene el borde bc : el resultado es un gráfico que consiste en un camino desde a hasta el vértice de la subdivisión final junto con un borde desde cada vértice del camino hasta cada uno de b y c . En la segunda etapa, cada una de las caras triangulares del gráfico plano resultante se subdivide una vez más. Si el camino desde a hasta el vértice de subdivisión final de la primera etapa tiene una longitud par, entonces el número de vértices en el gráfico general también es par. Sin embargo, aproximadamente 2/3 de los vértices son los insertados en la segunda etapa; estos forman un conjunto independiente y no pueden coincidir entre sí, ni hay suficientes vértices fuera del conjunto independiente para encontrar coincidencias para todos ellos.
Aunque las redes apolíneas en sí mismas pueden no tener coincidencias perfectas, los gráficos duales planos de las redes apolíneas son gráficos de 3 regulares sin bordes cortados , por lo que según un teorema de Petersen (1891) se garantiza que tendrán al menos una coincidencia perfecta. Sin embargo, en este caso se sabe más: los duales de las redes apolíneas siempre tienen un número exponencial de coincidencias perfectas. [16] László Lovász y Michael D. Plummer conjeturaron que un límite inferior exponencial similar se cumple de manera más general para cada gráfico de 3 regulares sin bordes cortados, un resultado que se demostró más tarde.
Andrade et al. (2005) estudiaron leyes de potencia en las secuencias de grados de un caso especial de redes de este tipo, formadas al subdividir todos los triángulos el mismo número de veces. Utilizaron estas redes para modelar empaquetamientos del espacio mediante partículas de diferentes tamaños. Basándose en su trabajo, otros autores introdujeron redes apolíneas aleatorias, formadas al elegir repetidamente una cara aleatoria para subdividir, y demostraron que éstas también obedecen a leyes de potencia en su distribución de grados [17] y tienen distancias promedio pequeñas. [18] Alan M. Frieze y Charalampos E. Tsourakakis analizaron los grados más altos y los valores propios de redes apolíneas aleatorias. [19] Andrade et al. También observó que sus redes satisfacen el efecto de mundo pequeño , es decir, que todos los vértices están a una pequeña distancia entre sí. Con base en evidencia numérica, estimaron que la distancia promedio entre pares de vértices seleccionados al azar en una red de n -vértices de este tipo era proporcional a (log n ) 3/4 , pero investigadores posteriores demostraron que la distancia promedio es en realidad proporcional a log n. . [20]
Butler y Graham (2010) observaron que si cada nuevo vértice se coloca en el incentro de su triángulo, de modo que las aristas del nuevo vértice bisecan los ángulos del triángulo, entonces el conjunto de triples de ángulos de los triángulos en la subdivisión, cuando reinterpretado como tripletas de coordenadas baricéntricas de puntos en un triángulo equilátero , converge en forma al triángulo de Sierpinski a medida que crece el número de niveles de subdivisión.
Takeo (1960) afirmó erróneamente que todas las redes apolíneas tienen ciclos hamiltonianos ; sin embargo, el gráfico de Goldner-Harary proporciona un contraejemplo. Si una red apolínea tiene una dureza mayor que uno (lo que significa que al eliminar cualquier conjunto de vértices del gráfico se deja un número menor de componentes conectados que el número de vértices eliminados), entonces necesariamente tiene un ciclo hamiltoniano, pero existen redes apolíneas no hamiltonianas. cuya dureza es igual a uno. [21]
El problema de enumeración combinatoria de contar triangulaciones apolíneas fue estudiado por Takeo (1960), quien demostró que tienen la función generadora simple f ( x ) descrita por la ecuación f ( x ) = 1 + x ( f ( x )) 3 . En esta función generadora, el término de grado n cuenta el número de redes apolíneas con un triángulo exterior fijo y n + 3 vértices. Así, los números de redes apolíneas (con un triángulo exterior fijo) en 3, 4, 5,... vértices son:
una secuencia que también cuenta árboles ternarios y disecciones de polígonos convexos en polígonos de lados impares. Por ejemplo, hay 12 redes apolíneas de 6 vértices: tres formadas subdividiendo el triángulo exterior una vez y luego subdividiendo dos de los triángulos resultantes, y nueve formadas subdividiendo el triángulo exterior una vez, subdividiendo uno de sus triángulos y luego subdividiendo uno de los triángulos más pequeños resultantes.
Birkhoff (1930) es uno de los primeros artículos que utiliza una forma dual de redes apolíneas, los mapas planos formados colocando repetidamente nuevas regiones en los vértices de mapas más simples, como una clase de ejemplos de mapas planos con pocos colores.
Las estructuras geométricas estrechamente relacionadas con las redes apolíneas se han estudiado en combinatoria poliédrica desde al menos principios de la década de 1960, cuando fueron utilizadas por Grünbaum (1963) para describir gráficos que pueden representarse como el gráfico de un politopo de una sola manera, sin dimensiones o ambigüedades combinatorias, y por Moon y Moser (1963) para encontrar politopos simpliciales sin caminos largos. En teoría de grafos , la estrecha conexión entre planaridad y ancho de árbol se remonta a Robertson y Seymour (1984), quienes demostraron que cada familia de gráficos menor-cerrada tiene un ancho de árbol limitado o contiene todos los gráficos planos. Los árboles planos 3, como una clase de gráficos, fueron considerados explícitamente por Hakimi y Schmeichel (1979), Alon y Caro (1984), Patil (1986) y muchos autores posteriores.
El nombre "red apolínea" fue dado por Andrade et al. (2005) a las redes que estudiaron en las que el nivel de subdivisión de triángulos es uniforme en toda la red; estas redes corresponden geométricamente a un tipo de poliedro apilado llamado Kleetope . [22] Otros autores aplicaron el mismo nombre de manera más amplia a los árboles 3 planos en su trabajo generalizando el modelo de Andrade et al. a redes apolíneas aleatorias. [18] Las triangulaciones generadas de esta manera también han sido denominadas "triangulaciones apiladas" [23] o "triangulaciones apiladas". [24]