En teoría de grafos , un cactus (a veces llamado árbol de cactus ) es un gráfico conexo en el que dos ciclos simples cualesquiera tienen como máximo un vértice en común. De manera equivalente, es un gráfico conexo en el que cada arista pertenece como máximo a un ciclo simple, o (para cactus no triviales) en el que cada bloque (subgrafo máximo sin un vértice de corte ) es una arista o un ciclo.
Los cactus son gráficos planos exteriores . Todo pseudoárbol es un cactus. Un gráfico no trivial es un cactus si y sólo si cada bloque es un ciclo simple o una arista única.
La familia de gráficos en la que cada componente es un cactus se cierra hacia abajo en operaciones menores de gráficos . Esta familia de gráficos puede caracterizarse por un único menor prohibido , el gráfico de diamante de cuatro vértices formado al eliminar un borde del gráfico completo K 4 . [1]
Un cactus triangular es un tipo especial de gráfico de cactus en el que cada ciclo tiene una longitud de tres y cada arista pertenece a un ciclo. Por ejemplo, los gráficos de amistad , gráficos formados a partir de una colección de triángulos unidos en un único vértice compartido, son cactus triangulares. Además de ser gráficos de cactus, los cactus triangulares también son gráficos de bloques y gráficos localmente lineales .
Los cactus triangulares tienen la propiedad de permanecer conectados si se les quita cualquier coincidencia ; para un número determinado de vértices, tienen la menor cantidad de aristas posibles con esta propiedad. Todo árbol con un número impar de vértices puede ampliarse a un cactus triangular añadiéndole aristas, dando un aumento mínimo con la propiedad de permanecer conectado después de eliminar una coincidencia. [2]
El cactus triangular más grande en cualquier gráfico se puede encontrar en tiempo polinómico usando un algoritmo para el problema de paridad matroide . Dado que los gráficos de cactus triangulares son gráficos planos , el cactus triangular más grande se puede utilizar como una aproximación al subgrafo plano más grande, un subproblema importante en la planarización . Como algoritmo de aproximación , este método tiene una relación de aproximación 4/9, la más conocida para el problema del subgrafo plano máximo. [3]
El algoritmo para encontrar el cactus triangular más grande está asociado con un teorema de Lovász y Plummer que caracteriza el número de triángulos en este cactus más grande. [4] Lovász y Plummer consideran pares de particiones de los vértices y aristas del gráfico dado en subconjuntos, con la propiedad de que cada triángulo del gráfico tiene dos vértices en una sola clase de partición de vértices o las tres aristas en una sola. clase de partición de borde; llaman válidas a un par de particiones con esta propiedad . Entonces, el número de triángulos en el cactus triangular más grande es igual al máximo, entre pares de particiones válidas y , de
donde es el número de vértices en el gráfico dado y es el número de clases de vértices que cumple la clase de borde .
Cada gráfico plano contiene un subgrafo de cactus que incluye al menos una fracción de las caras triangulares de . Este resultado implica un análisis directo del algoritmo de aproximación 4/9 para el problema del subgrafo plano máximo sin utilizar la fórmula mín-máx anterior. [5]
Una conjetura importante relacionada con el cactus triangular es la Conjetura de Rosa , llamada así en honor a Alexander Rosa , que dice que todos los cactus triangulares son gráciles o casi gráciles. [6] Más precisamente
Todos los cactus triangulares con bloques t ≡ 0, 1 mod 4 son elegantes, y aquellos con t ≡ 2, 3 mod 4 son casi elegantes.
Algunos problemas de ubicación de instalaciones que son NP-difíciles para gráficos generales, así como algunos otros problemas de gráficos, pueden resolverse en tiempo polinomial para cactus. [7] [8]
Dado que los cactus son casos especiales de gráficos planos externos , se pueden resolver varios problemas de optimización combinatoria en gráficos en tiempo polinomial . [9]
Los cactus representan circuitos eléctricos que tienen propiedades útiles. Una de las primeras aplicaciones de cactus se asoció con la representación de amplificadores operacionales. [10] [11] [12]
Los cactus también se han utilizado en genómica comparada como una forma de representar la relación entre diferentes genomas o partes de genomas. [13]
Si un cactus está conectado, y cada uno de sus vértices pertenece como máximo a dos bloques, entonces se llama cactus de Navidad . Cada gráfico poliédrico tiene un subgrafo de cactus navideño que incluye todos sus vértices, un hecho que juega un papel esencial en la prueba de Leighton y Moitra (2010) de que cada gráfico poliédrico tiene una incrustación codiciosa en el plano euclidiano , una asignación de coordenadas a los vértices para los cuales el reenvío codicioso logra enrutar mensajes entre todos los pares de vértices. [14]
En teoría de grafos topológicos , los gráficos cuyas incrustaciones celulares son todas planas son exactamente la subfamilia de los gráficos de cactus con la propiedad adicional de que cada vértice pertenece como máximo a un ciclo. Estas gráficas tienen dos menores prohibidos, la gráfica del diamante y la gráfica de la amistad de cinco vértices . [15]
Los cactus se estudiaron por primera vez con el nombre de árboles Husimi , que les otorgaron Frank Harary y George Eugene Uhlenbeck en honor al trabajo anterior sobre estos gráficos de Kôdi Husimi . [16] [17] El mismo artículo de Harary-Uhlenbeck reserva el nombre "cactus" para gráficos de este tipo en los que cada ciclo es un triángulo, pero ahora permitir ciclos de todas las longitudes es estándar.
Mientras tanto, el nombre de árbol Husimi comúnmente llegó a referirse a gráficos en los que cada bloque es un gráfico completo (de manera equivalente, los gráficos de intersección de los bloques en algún otro gráfico). Este uso tuvo poco que ver con el trabajo de Husimi, y ahora se utiliza el término más pertinente gráfico de bloques para esta familia; sin embargo, debido a esta ambigüedad, esta frase se ha utilizado con menos frecuencia para referirse a los gráficos de cactus. [18]
