En matemáticas combinatorias , una red apolínea es un grafo 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 planares , los grafos cordales planares maximalistas, los grafos planares de 4 colores únicos y los grafos de politopos apilados . Reciben su nombre en honor a Apolonio de Perga , quien estudió una construcción relacionada con el empaquetamiento de círculos.
Se puede formar una red apolínea, a partir de un único triángulo incrustado en el plano euclidiano , seleccionando repetidamente una cara triangular de la incrustación, añadiendo un nuevo vértice dentro de la cara y conectando el nuevo vértice con cada vértice de la cara que lo contiene. De esta manera, el triángulo que contiene el nuevo vértice se subdivide en tres triángulos más pequeños, que a su vez pueden subdividirse de la misma manera.
Los grafos completos de tres y cuatro vértices, K 3 y K 4 , son ambos redes apolíneas. K 3 se forma partiendo de un triángulo y sin realizar ninguna subdivisión, mientras que K 4 se forma realizando una única subdivisión antes de detenerse.
El gráfico de Goldner-Harary es una red apolínea que forma el gráfico plano maximalista 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 maximalista no hamiltoniano 1-tough .
Además de definirse por la subdivisión recursiva de triángulos, las redes apolíneas tienen varias otras caracterizaciones matemáticas equivalentes. Son los grafos planos maximal cordales , los grafos poliédricos cordales y los 3-árboles planos . Son los grafos planos con 4 colores únicos y los grafos planos con una descomposición única de Schnyder Wood en tres árboles. Son los grafos planos maximal con ancho de árbol tres, una clase de grafos que se pueden caracterizar por sus menores prohibidos o por su reducibilidad bajo transformadas Y-Δ . Son los grafos planos maximal con degeneración tres. También son los grafos planos en un número dado 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 la descomposición separando triángulos.
Las redes apolíneas son ejemplos de grafos planos maximalistas , grafos a los que no se pueden añadir aristas adicionales sin destruir la planaridad, o equivalentemente grafos que se pueden dibujar en el plano de modo que cada cara (incluida la cara exterior) sea un triángulo. También son grafos cordales , grafos en los que cada ciclo de cuatro o más vértices tiene una arista diagonal que conecta dos vértices de ciclo no consecutivos, y el orden en el que se añaden los vértices en el proceso de subdivisión que forma una red apolínea es un orden de eliminación como un grafo cordal. Esto forma una caracterización alternativa de las redes apolíneas: son exactamente los grafos planos maximalistas cordales o equivalentemente los grafos poliédricos cordales . [2]
En una red apolínea, cada clique maximal es un grafo completo de cuatro vértices, formado eligiendo cualquier vértice y sus tres vecinos anteriores. Cada separador de clique minimal (un clique que divide el grafo en dos subgrafos desconectados) es uno de los triángulos subdivididos. Un grafo cordal en el que todos los clique maximal y todos los separadores de clique minimal 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 grafo único con 4 colores . Debido a que es un grafo plano, el teorema de los cuatro colores implica que tiene una coloración de grafo con solo cuatro colores, pero una vez que se seleccionan los tres colores del triángulo inicial, solo hay una opción posible para el color de cada vértice sucesivo, por lo que hasta la permutación del conjunto de colores tiene exactamente una coloración de 4 colores. Es más difícil de probar, pero también cierto, que cada grafo plano único con 4 colores es una red apolínea. Por lo tanto, las redes apolíneas también pueden caracterizarse como los grafos planos únicos con 4 colores. [3] Las redes apolíneas también proporcionan ejemplos de grafos planos que tienen la menor cantidad posible de k colores para k > 4. [4 ]
Las redes apolíneas son también exactamente los gráficos planares máximos que (una vez que se fija una cara exterior) tienen una única madera de Schnyder , una partición de los bordes del gráfico en tres árboles intercalados con raíces en los tres vértices de la cara exterior. [5]
Las redes apolíneas no forman una familia de grafos que esté cerrada bajo la operación de tomar menores de grafos , ya que quitar aristas pero no vértices de una red apolínea produce un grafo que no es una red apolínea. Sin embargo, los 3-árboles parciales planares , subgrafos de redes apolíneas, son menores cerrados. Por lo tanto, de acuerdo con el teorema de Robertson-Seymour , pueden caracterizarse por un número finito de menores prohibidos . Los menores prohibidos mínimos para los 3-árboles parciales planares son los cuatro grafos mínimos entre los menores prohibidos para los grafos planares y los 3-árboles parciales: el grafo completo K 5 , el grafo bipartito completo K 3,3 , el grafo del octaedro y el grafo del prisma pentagonal . Los grafos apolíneos son los grafos maximales que no tienen ninguno de estos cuatro grafos como menor. [6]
Una transformación Y-Δ , una operación que reemplaza un vértice de grado tres en un grafo por un triángulo que conecta sus vecinos, es suficiente (junto con la eliminación de las aristas paralelas) para reducir cualquier red apolínea a un solo triángulo, y más generalmente los grafos planares que pueden reducirse a una sola arista mediante transformaciones Y-Δ, eliminación de aristas paralelas, eliminación de vértices de grado uno y compresión de vértices de grado dos son exactamente los 3-árboles parciales planares. Los grafos duales de los 3-árboles parciales planares forman otra familia de grafos cerrados menores y son exactamente los grafos planares que pueden reducirse a una sola arista mediante transformaciones Δ-Y, eliminación de aristas paralelas, 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 añadido más recientemente tiene un grado de tres como máximo, por lo que las redes apolíneas tienen una degeneración de tres. El orden en el que se añaden los vértices para crear la red es, por tanto, un orden de degeneración, y las redes apolíneas coinciden con los grafos planos maximalistas de 3 degeneraciones.
Otra caracterización de las redes apolíneas implica su conectividad . Cualquier grafo plano maximal puede descomponerse en subgrafos planos maximalistas conexos por 4 vértices dividiéndolo a lo largo de sus triángulos separadores (triángulos que no son caras del grafo): dado cualquier triángulo no facial: se pueden formar dos grafos planos maximalistas más pequeños, uno que consiste en la parte dentro del triángulo y el otro que consiste en la parte fuera del triángulo. Los grafos planos maximalistas sin triángulos separadores que pueden formarse por divisiones repetidas de este tipo a veces se denominan bloques, aunque ese nombre también se ha utilizado para los componentes biconectados de un grafo que no es en sí mismo biconectado. Una red apolínea es un grafo plano maximal en el que todos los bloques son isomorfos al grafo completo K 4 .
En la teoría de grafos extremales , las redes apolíneas son también exactamente los grafos planares de n -vértices en los que el número de bloques alcanza su máximo, n − 3 , y los grafos planares en los que el número de triángulos alcanza su máximo, 3 n − 8 . Dado que cada K 4 subgrafo de un grafo planar debe ser un bloque, estos son también los grafos planares en los que el número de K 4 subgrafos alcanza su máximo, n − 3 , y los grafos en los que el número de camarillas de cualquier tipo alcanza su máximo, 8 n − 16 . [8]
Las redes apolíneas reciben su 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 una instancia simple del teorema de empaquetamiento de círculos de Koebe-Andreev-Thurston , que establece que cualquier gráfico plano puede ser representado por círculos tangentes de la misma manera. [10]
Las redes apolíneas son grafos planos 3-conexos y, por lo tanto, por el teorema de Steinitz , siempre se pueden representar como los grafos de poliedros convexos. El poliedro convexo que representa una red apolínea es un politopo apilado tridimensional . Un politopo de este tipo se puede obtener a partir de un tetraedro pegando repetidamente tetraedros adicionales, uno a la vez, sobre sus caras triangulares. Por lo tanto, las redes apolíneas también se pueden definir como los grafos de politopos tridimensionales apilados. [11] Es posible encontrar una representación de cualquier red apolínea como un poliedro tridimensional convexo en el que todas las coordenadas sean números enteros de tamaño polinomial, mejor que lo que se conoce para otros grafos planos. [12]
La subdivisión recursiva de triángulos en tres triángulos más pequeños fue investigada como una técnica de segmentación de imágenes en visión por computadora por Elcock, Gargantini y Walsh (1987); en este contexto, la llamaron descomposición triangular escalena ternaria . Observaron que, al colocar cada nuevo vértice en el centroide del triángulo que lo rodea, la triangulación podría elegirse de tal manera que todos los triángulos tengan áreas iguales, aunque no todos tengan 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 llevar a cabo el proceso de subdividir un triángulo para formar una red apolínea de tal manera que, en cada paso, las longitudes de las aristas sean números racionales; es un problema abierto si cada grafo planar tiene un dibujo con esta propiedad. [14] Es posible en tiempo polinomial encontrar un dibujo de un 3-árbol planar con coordenadas enteras que minimicen el área del cuadro delimitador del dibujo, y probar si un 3-árbol planar dado puede dibujarse con sus vértices en un conjunto dado de puntos. [15]
Plummer (1992) utilizó redes apolíneas para construir una familia infinita de grafos planares maximalistas con un número par de vértices pero sin emparejamiento perfecto . Los grafos de Plummer se forman en dos etapas. En la primera etapa, a partir de un triángulo abc , se subdivide repetidamente la cara triangular de la subdivisión que contiene la arista bc : el resultado es un grafo que consiste en un camino desde a hasta el vértice de subdivisión final junto con una arista desde cada vértice del camino hasta cada uno de b y c . En la segunda etapa, cada una de las caras triangulares del grafo planar 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 grafo 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 se pueden emparejar 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 emparejamientos perfectos, los grafos duales planares de las redes apolíneas son grafos 3-regulares sin aristas cortadas , por lo que por un teorema de Petersen (1891) se garantiza que tienen al menos un emparejamiento perfecto. Sin embargo, en este caso se sabe más: los duales de las redes apolíneas siempre tienen un número exponencial de emparejamientos perfectos. [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 grafo 3-regular sin aristas cortadas, 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 subdividiendo todos los triángulos el mismo número de veces. Utilizaron estas redes para modelar empaquetamientos del espacio por partículas de distintos tamaños. Basándose en su trabajo, otros autores introdujeron redes apolíneas aleatorias, formadas eligiendo repetidamente una cara aleatoria para subdividir, y demostraron que éstas también obedecen leyes de potencia en su distribución de grados [17] y tienen pequeñas distancias medias. [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 observaron que sus redes satisfacen el efecto de mundo pequeño , de que todos los vértices están a una pequeña distancia entre sí. Basándose en evidencia numérica, estimaron que la distancia promedio entre pares de vértices seleccionados aleatoriamente 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 triángulos en la subdivisión, cuando se reinterpreta como triples de coordenadas baricéntricas de puntos en un triángulo equilátero , converge en forma del 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 grafo de Goldner-Harary proporciona un contraejemplo. Si una red apolínea tiene una tenacidad mayor que uno (lo que significa que al eliminar cualquier conjunto de vértices del grafo queda 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 tenacidad 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. Por lo tanto, el número 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 planares formados al colocar repetidamente nuevas regiones en los vértices de mapas más simples, como una clase de ejemplos de mapas planares con pocas coloraciones.
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 grafos que pueden realizarse como el grafo de un politopo de una sola manera, sin ambigüedades dimensionales o 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 grafos menor-cerrada tiene un ancho de árbol acotado o contiene todos los grafos planares. Los 3-árboles planares, como una clase de grafos, fueron considerados explícitamente por Hakimi y Schmeichel (1979), Alon y Caro (1984), Patil (1986) y muchos autores desde entonces.
El nombre de "red apolínea" fue dado por Andrade et al. (2005) a las redes que estudiaron en las que el nivel de subdivisión de los triángulos es uniforme a lo largo de 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 3-árboles planares en su trabajo de generalización del modelo de Andrade et al. a redes apolíneas aleatorias. [18] Las triangulaciones generadas de esta manera también se han denominado "triangulaciones apiladas" [23] o "stack-triangulations". [24]