El gráfico de Apolonio [1] es un gráfico no dirigido formado por el proceso recursivo de dividir un triángulo en tres triángulos más pequeños. Los gráficos de Apolonio se pueden definir de manera equivalente como 3 árboles planos , como gráficos cordales planos máximos , como gráficos planos de 4 colores únicos o como gráficos de politopos de bloques . Los gráficos llevan el nombre de Apolonio de Perga , quien estudió construcciones relacionadas con el empaquetamiento de círculos.
El gráfico de Apolonio se puede obtener a partir de un gráfico triangular incrustado en el plano euclidiano seleccionando repetidamente una cara de anidamiento triangular, agregando un nuevo vértice a esa cara triangular y conectando el nuevo vértice a cada vértice dentro de la cara. Como resultado, la cara se divide en tres triángulos más pequeños que, a su vez, se pueden dividir de la misma manera.
Los grafos completos de tres y cuatro vértices, K 3 y K 4 , son grafos de Apolonio. K 3 está formado por el triángulo inicial sin más operaciones de subdivisión, mientras que K 4 está formado por una sola operación de subdivisión.
El gráfico de Goldner-Harari es el gráfico de Apolonio y también el gráfico plano máximo no hamiltoniano más pequeño [2] . Nishizeki [3] usó otro gráfico de Apolonio más complejo como ejemplo de un gráfico plano máximo no hamiltoniano de 1 rigidez .
Debido a que los gráficos de Apolonio se definen mediante la subdivisión recursiva de triángulos, tienen diferentes descripciones matemáticas. Los gráficos son gráficos planares máximos cordales, gráficos poliédricos cordales y 3-árboles planos . Los gráficos son gráficos planos de 4 colores únicos y gráficos planos con una descomposición única en un bosque de Schneider que consta de tres árboles. Los gráficos son gráficos planos máximos con un ancho de árbol de tres, una clase de gráficos que pueden describirse por sus gráficos prohibidos o por su reducción mediante transformaciones Y-Δ . Los gráficos son gráficos planares máximos con degeneración tres. Los gráficos también son gráficos planos con 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 partes después de descomponerse en triángulos individuales.
Los gráficos de Apolonio son ejemplos de gráficos planos máximos a los que no se puede agregar un borde sin violar la planaridad o, de manera equivalente, gráficos que se pueden dibujar en el plano de modo que cualquier cara (incluida la cara exterior) sea un triángulo. Los grafos también son grafos cordales , en los que cada ciclo de cuatro o más vértices tiene un borde diagonal que conecta dos vértices del ciclo que no son consecutivos en el ciclo, y el orden en que se agregan los vértices durante la construcción del gráfico de Apolonio es el orden de eliminación en el gráfico cordal. Esta propiedad ofrece una descripción alternativa de los gráficos de Apolonio: son exactamente gráficos planos máximos cordales o, de manera equivalente, gráficos poliédricos cordales [4] .
En el grafo de Apollonia, cualquier clique maximal es un grafo completo con cuatro vértices, formado por la elección de cualquier vértice y tres vecinos más cercanos. Cualquier separador de camarilla mínimo (una camarilla cuya eliminación divide el gráfico en dos gráficos desconectados) es uno de los triángulos divididos. Un gráfico cordal en el que todas las cliques máximas y todos los separadores de cliques mínimas tienen el mismo tamaño es un k -tree , y las gráficas de Apollonius son ejemplos de 3- trees. No todos los 3 árboles son planos, pero los 3 árboles planos son exactamente gráficos de Apolonio.
Cualquier gráfico de Apolonio tiene una coloración única de 4 colores . Dado que el gráfico es plano, el teorema de los cuatro colores implica que el gráfico tiene una coloración de cuatro colores , pero dado que los colores del triángulo inicial son fijos, solo hay una opción de color para el nuevo vértice, por lo que hasta una permutación de colores, la coloración del gráfico será única. Es más difícil de mostrar, pero también es cierto que cualquier gráfico plano con un solo coloreado es un gráfico de Apolonio. Por lo tanto, el gráfico de Apolonio se puede caracterizar como un gráfico plano con 4 colores únicos [5] . Los gráficos de Apolonio dan ejemplos de gráficos planos que tienen el número mínimo de k -coloraciones para k > 4 [6]
Además, los gráficos de Apolonio son exactamente gráficos planos máximos que (si la cara exterior es fija) tienen un bosque de Schneider único , una partición de los bordes del gráfico en tres árboles enraizados en los vértices de la cara exterior [7] [8] .
Los grafos de Apolonio no forman una familia de grafos que sea cerrada respecto a la operación de tomar los menores del grafo , ya que al quitar aristas, pero no vértices, obtenemos un grafo que no es un grafo de Apolonio. Sin embargo, la familia de 3-árboles parciales planares , subgrafos de los gráficos de Apolonio, es una familia menormente cerrada. Así, según el teorema de Robertson-Seymour , pueden caracterizarse por un número finito de menores prohibidos . Los mínimos menores prohibidos para 3-árboles parciales planares son los cuatro grafos mínimos para grafos planos y 3-árboles parciales: el grafo completo K 5 , el grafo bipartito completo K 3,3 , el grafo octaedro y el grafo prisma pentagonal . Los grafos de Apolonio son grafos máximos que no contienen estos cuatro grafos como menores [9]
Una transformación Y-Δ que reemplaza un vértice de grado tres con un triángulo que conecta vecinos es suficiente (junto con la operación de eliminación de múltiples aristas) para reducir el gráfico de Apolonio a un solo triángulo. Los gráficos planos que se pueden reducir a un solo borde con una transformación Y-Δ, eliminando múltiples bordes, eliminando vértices de grado 1 y reemplazando un vértice de grado 2 con bordes por un solo borde, son precisamente 3-árboles parciales planares. Los gráficos duales de 3 árboles parciales planos forman otra familia de gráficos cerrados tomando menores, que son exactamente aquellos gráficos que se pueden reducir a un solo borde usando la transformación Δ-Y, eliminando múltiples bordes, eliminando vértices de grado 1 y deshacerse de los vértices de grado 2 [10] .
En cualquier subgráfico de un gráfico de Apolonio, el último vértice agregado tiene grado tres, por lo que los gráficos de Apolonio tienen degeneración tres. El orden en el que se agregan los vértices al crear un gráfico es, por lo tanto, el orden de degeneración, y los gráficos de Apolonio son los mismos que los gráficos planares máximos de 3 degenerados.
Otra propiedad que caracteriza a los grafos de Apolonio es la conectividad . Cualquier gráfico plano máximo se puede descomponer en subgráficos planos máximos conectados con 4 vértices dividiéndolos a lo largo de triángulos (no caras del gráfico); si hay un triángulo que no es una cara, se pueden formar dos gráficos planos máximos más pequeños, uno que consiste en el parte interior del triángulo, la otra consta de una parte exterior al triángulo. Los gráficos planares máximos sin triángulos de separación, que son generados por múltiples particiones de este tipo, a veces se denominan bloques, aunque el mismo nombre también se usa para los componentes biconectados de un gráfico que no está biconectado. El gráfico de Apolonio es un gráfico plano maximal en el que todos los bloques son isomorfos al gráfico completo K 4 .
En la teoría de grafos extremos, los grafos de Apolonio son grafos exactamente planos con n vértices, en los que el número de bloques alcanza el valor máximo n − 3 , y grafos planos, en los que el número de triángulos es máximo e igual a 3 n − 8 . Dado que cada K 4 subgrafo de un grafo plano debe ser un bloque, estos gráficos alcanzan el número máximo de K 4 subgrafos (este número es igual a n − 3 ). En los mismos gráficos, se logra el número máximo de camarillas de cualquier tipo (el número de camarillas es 8 n − 16 ) [11]
Los gráficos llevan el nombre de Apolonio de Perga , quien estudió el problema de construir círculos tangentes a otros tres círculos. Un método para construir gráficos de Apolonio es comenzar con tres círculos tangentes entre sí e inscribir repetidamente otro círculo en el espacio formado por los tres círculos construidos antes. Un fractal formado de esta manera se llama rejilla de Apolonio .
Si el proceso de construcción de la cuadrícula de Apolonio se detiene dibujando solo un número finito de círculos, entonces el gráfico que tiene un vértice para cada círculo y una arista para dos círculos tangentes cualesquiera es el gráfico de Apolonio [12] . La existencia de un conjunto de círculos tangentes cuya tangencia representa el gráfico de Apolonio está determinada por el teorema de Koebe-Andreev-Thurston , que establece que cualquier gráfico plano puede ser representado por círculos tangentes [13] .
Los grafos de Apolonio son grafos planos con 3 vértices conectados y, por lo tanto, según el teorema de Steinitz , siempre se pueden representar como grafos de poliedros convexos . El politopo convexo que representa el gráfico de Apolonio es un politopo de bloque tridimensional . Dichos poliedros se pueden obtener de un tetraedro pegando repetidamente tetraedros adicionales (uno a la vez) a las caras triangulares del poliedro. Por lo tanto, los gráficos de Apolonio se pueden definir como gráficos de poliedros tridimensionales de bloques [14] . Es posible encontrar una representación de cualquier gráfico de Apolonio como un poliedro tridimensional convexo en el que todas las coordenadas son polinomios enteros, lo que es mejor que para otros gráficos planos [15] .
La división recursiva de triángulos en tres triángulos más pequeños fue explorada por Elcock, Gargantini y Walsh como una técnica de segmentación de imágenes en visión artificial [16] . En este contexto, se refieren a tal división como una descomposición de triple triángulo inequilátero . Notaron que a medida que se agrega cada nuevo vértice al centroide en un triángulo, los triángulos de triangulación tendrán la misma área, aunque no tengan la misma forma. De manera más general, los gráficos de Apolonio se pueden dibujar en el plano, con cualquier área predeterminada de cada cara. Si las áreas se dan como números racionales , también lo serán las coordenadas de los vértices [17] .
Es posible realizar el proceso de división de triángulos al construir el gráfico de Apolonio de tal manera que en cada paso las longitudes de las aristas sean números racionales. No se sabe si se puede dibujar cualquier gráfico plano con las mismas propiedades [18] . En tiempo polinomial, uno puede encontrar un dibujo de un árbol plano de 3 con coordenadas enteras con un área mínima del cuadro delimitador y verificar si un árbol plano de 3 dado se puede dibujar con vértices en un conjunto dado de puntos [19 ]
Plummer [20] utilizó los gráficos de Apolonio para construir una familia infinita de gráficos planos máximos con un número par de vértices que no tienen una coincidencia perfecta . Los gráficos de Plummer se construyen en dos etapas. En la primera etapa, a partir del triángulo abc , se repite muchas veces la división de la cara triangular que contiene la arista bc . El gráfico resultante contiene un camino desde a hasta el vértice de la división final, y cada vértice de este camino está conectado por aristas a los vértices b y c . En la segunda etapa, cada cara (triangular) del gráfico plano resultante se vuelve a dividir. Si el camino desde a hasta el vértice final de la partición de la primera etapa tiene una longitud par, el número total de vértices en el gráfico también es par. Sin embargo, alrededor de 2/3 de los vértices insertados en la segunda etapa forman un conjunto independiente y no pueden coincidir entre sí, y los vértices restantes no son suficientes para formar una combinación perfecta.
Aunque los gráficos de Apolonio en sí mismos no pueden tener coincidencias perfectas, los gráficos duales a los gráficos de Apolonio son gráficos de 3 regulares sin bordes cortantes , por lo que según el teorema de Petersen [21] , necesariamente tienen al menos una coincidencia perfecta. Para los gráficos de Apolonio, se sabe aún más: los gráficos duales a los gráficos de Apolonio tienen un número exponencialmente grande de coincidencias perfectas [22] . Laszlo Lovas y Michael D. Plummer conjeturaron que debería existir un límite inferior exponencial similar para todos los gráficos de 3 regulares sin bordes cortantes, lo que luego se confirmó.
J. Andrade, G. Herrmann, R. Andrade y L. de Silva [12] estudiaron las leyes de potencias de sucesiones de grados de tipos especiales de gráficas de este tipo formadas al dividir todos los triángulos el mismo número de veces. Usaron estos gráficos para modelar el llenado del espacio con partes de varios tamaños. Con base en su trabajo, otros autores propusieron gráficos aleatorios de Apolonio obtenidos al elegir aleatoriamente una cara para la división, y demostraron que estos gráficos obedecen a una ley de potencia en la distribución de grados de vértices [23] , y también demostraron que estos gráficos tienen distancias pequeñas [ 24] [25] . Freese y Tsourakakis analizaron los mayores grados de vértices y valores propios de grafos aleatorios de Apolonio [26] . J. Andrade, G. Herrmann, R. Andrade y L. de Silva también notaron que sus gráficas satisfacen el efecto del “ mundo pequeño ” (la teoría de los seis apretones de manos), es decir, que todos los vértices están a una distancia cercana entre sí . Con base en experimentos numéricos, estimaron que la distancia promedio entre pares de vértices seleccionados al azar en un gráfico de n vértices es proporcional a (log n ) 3/4 , pero investigaciones posteriores demostraron que la distancia promedio era en realidad proporcional a log n [27] [28] .
Butler y Graham [29] notaron que si cada nuevo vértice se coloca en el punto de intersección de las bisectrices de un triángulo, entonces el conjunto de tripletes de ángulos de triángulos en una subdivisión, si se interpreta como las coordenadas baricéntricas de puntos en un triángulo regular , forma un triángulo de Sierpinski en el límite a medida que aumenta el nivel de subdivisión.
Takeo [30] afirmó erróneamente que todos los gráficos de Apolonio tienen ciclos hamiltonianos , pero el gráfico de Goldner-Harari proporciona un contraejemplo. Si un grafo de Apolonio tiene una rigidez mayor que uno (lo que significa que al eliminar cualquier número de vértices del grafo, quedan menos componentes conectadas que el número de vértices eliminados), es necesariamente hamiltoniano, pero hay gráficos de Apolonio no hamiltonianos si la rigidez es uno [31]
Takeo [30] estudió la tarea de la combinatoria para calcular las triangulaciones de Apolonio . Demostró que para el número de triangulaciones existe una función generatriz simple f ( x ) descrita por la igualdad f ( x ) = 1 + x ( f ( x )) 3 . En esta función generadora, el término de grado n contiene el número de grafos de Apolonio con un triángulo exterior y n + 3 vértices. Número de grafos de Apolonio (con triángulo exterior) y 3, 4, 5, ... vértices:
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675,... (secuencia A001764 en OEIS ).La misma secuencia especifica el número de árboles ternarios y el número de particiones de un polígono convexo en polígonos con un número impar de lados. Por ejemplo, hay 12 gráficos de Apolonio con 6 vértices: tres se forman dividiendo el triángulo exterior, seguido de la división de dos de los triángulos resultantes, y nueve más se forman dividiendo el triángulo exterior y dividiendo uno de los triángulos resultantes, seguidos de dividir uno de los pequeños triángulos.
Birkhoff [32] tiene un artículo anterior que usa la forma dual de los gráficos de Apolonio, mapas planos formados colocando repetidamente nuevas áreas en los vértices de mapas más simples, como un ejemplo de una clase de gráficos planos con pocos colores.
Las estructuras geométricas similares a los gráficos de Apolonio se han estudiado en la combinatoria de poliedros desde principios de la década de 1960, cuando Grünbaum [33] las utilizó para describir gráficos que se pueden realizar en poliedros de una manera única en términos de dimensión y desde el punto de vista. de combinatoria. También fueron utilizados por Moon y Moser [34] para buscar poliedros simpliciales sin caminos largos. En la teoría de grafos, la estrecha relación entre la planaridad y el ancho del árbol se remonta a un artículo de 1984 de Robertson y Seymour [35] , quienes demostraron que una familia de gráficos que es cerrada teniendo en cuenta los menores tiene un ancho de árbol acotado o contiene todos los gráficos planos. Los 3 árboles planos como una clase de grafos fueron considerados por Hakimi y Schmeichel [36] , Alon y Caro [37] , Patil [38] y muchos otros autores después de ellos.
El nombre "grafo de Apolonia" fue propuesto en el artículo de J. Andrade, G. Herrmann, R. Andrade y L. de Silva [12] para gráficos en los que el nivel de división de triángulos es homogéneo. Geométricamente, estos gráficos corresponden a politopos de bloque (politopos de Klee ) [33] [39] . Otros autores han usado el término para una clase más amplia de grafos, 3 árboles planos, para generalizar el modelo a grafos aleatorios de Apolonio [24] [25] . La triangularización así obtenida también ha sido llamada "triangularización de bloques" [37] [40] [41] [7] [27] [8] [22] .