Grafo cactus
# Grafo cactus

En teoría de grafos, un cactus (a veces llamado árbol de cactus) es un grafo conectado en el que dos ciclos simples tienen como máximo un vértice en común. De manera equivalente, es un grafo conectado en el que cada arista pertenece a un ciclo simple como máximo, o (para cactus no triviales) en el que cada bloque (subgrafo máximo sin vértices de corte) es una arista o un ciclo.

## Propiedades

Los grafos cactus son plano exteriores. Cada seudoárbol es un cactus. Un grafo no trivial es un cactus si y solo si cada unos de sus bloques es un ciclo simple o una sola arista.

La familia de grafos en los que cada componente es un cactus es cerrada hacia abajo respecto a las operaciones de determinación de menores. Esta familia de grafos se puede caracterizar por un solo menor prohibido, el grafo diamante de cuatro vértices formado al eliminar un borde del grafo completo $K_4.$

## Cactus triangular

Un cactus triangular es un tipo especial de grafo cactus en el que cada ciclo tiene una longitud de tres y cada arista pertenece a un ciclo. Por ejemplo, los grafos de la amistad, grafos formados a partir de una colección de triángulos unidos en un solo vértice compartido, son cactus triangulares. Además de ser grafos de cactus, los cactus triangulares también son grafos bloque y localmente lineales.

Los cactus triangulares tienen la propiedad de permanecer unidos si se les quita algún emparejamiento; para un número dado de vértices, tienen la menor cantidad posible de aristas con esta propiedad. Cada árbol con un número impar de vértices puede convertirse en un cactus triangular añadiéndole aristas, dando un aumentado mínimo con la propiedad de permanecer conectado después de la eliminación de un emparejamiento.

El cactus triangular más grande en cualquier grafo se puede encontrar en tiempo polinómico usando un algoritmo para el problema de la paridad de matroides. Dado que los grafos cactus triangulares son planos, el cactus triangular más grande se puede usar como una aproximación al subgrafo plano más grande, un subproblema importante en planarización. Como algoritmo de aproximación, este método tiene algoritmo de aproximación 4/9, el más conocido para el problema del subgrafo plano máximo.

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. Lovász y Plummer consideran pares de particiones de vértices y aristas del grafo dado en subconjuntos, con la propiedad de que cada triángulo del grafo tiene dos vértices en una sola clase de partición de vértices o las tres aristas en una sola clase de grafo de partición de arista; llaman a un par de particiones con esta propiedad "válidas".

Entonces, el número de triángulos en el cactus triangular más grande es igual al máximo, sobre pares de particiones válidas ${\mathcal {P}}=\{V_{1},V_{2},\dots ,V_{k}\}$ y ${\mathcal {Q}}=\{E_{1},E_{2},\dots ,E_{m}\}$, de

    $\sum _{i=1}^{m}{\frac {(u_{i}-1)}{2}}+n-k,$,

donde $n$ es el número de vértices en el grafo dado y $u_{i}$ es el número de clases de vértices que cumple la clase de arista $E_{i}$.

Recientemente, se probó un límite extremo estrecho que demostraba que dado cualquier grafo plano $G$, siempre existe un subgrafo de cactus $C\subseteq G$ que contiene al menos la fracción $1/6$ de las caras triangulares de $G$. Este resultado implica un análisis directo del algoritmo de aproximación 4/9 para el problema del subgrafo plano máximo sin usar la fórmula mín-máx anterior.

### Conjetura de Rosa

Una conjetura importante relacionada con el cactus triangular es la conjetura de Rosa, llamada así por Alexander Rosa, que dice que todos los cactus triangulares son elegantes o casi elegantes. Más precisamente

En todos los cactus triangulares con t ≡ 0, los 1 mod 4 bloques son elegantes, y en aquellos con t ≡ 2, los 3 mod 4 bloques son casi elegantes.

## Algoritmos y aplicaciones

Algunos problemas de ubicación de instalaciones que son de dificultad NP para grafos generales, así como algunos otros problemas de grafos, pueden resolverse en tiempo polinómico en el caso de los grafos cactus.

Dado que los cactus son casos especiales de grafos planos exteriores, se pueden resolver varios problemas de optimización combinatoria en grafos en tiempo polinómico.

Los grafos cactus representan circuitos que tienen propiedades útiles. Una de sus primeras aplicaciones se asoció con la representación de amplificadores operacionales.

También se han utilizado en genómica comparativa como una forma de representar la relación entre diferentes genomas o partes de genomas.

Si un grafo cactus está conectado, y cada uno de sus vértices pertenece como máximo a dos bloques, entonces se llama cactus de Navidad. Cada grafo poliédrico tiene un subgrafo de cactus navideño que incluye todos sus vértices, un hecho que juega un papel esencial en una prueba de Leighton y Moitra (2010) de que cada grafo poliédrico tiene un embebido ávido en un espacio bidimensional, una asignación de coordenadas a los vértices para los cuales un procedimiento de reenvío ávido logra enrutar mensajes entre todos los pares de vértices.

En teoría de grafos topológica, los grafos cuyos embebidos celulares son todos planos son exactamente la subfamilia de los grafos de cactus con la propiedad adicional de que cada vértice pertenece como máximo a un ciclo. Estos grafos tienen dos menores prohibidos, el grafo de diamante y el grafo de la amistad de cinco vértices.

## Historia

Los grafos cactus se estudiaron por primera vez con el nombre de árboles de Husimi, término ideado por Frank Harary y George Eugene Uhlenbeck en honor al trabajo previo de Kôdi Husimi en estos grafos. El mismo artículo de Harary-Uhlenbeck reservaba el nombre de cactus para grafos de este tipo en los que cada ciclo es un triángulo, pero posteriormente se permiten ciclos de cualquier longitud como estándar.

Mientras tanto, el nombre árbol de Husimi comúnmente vino a referirse a grafos en los que cada bloque es un grafo completo (equivalentemente, los grafos de intersección de los bloques en algún otro grafo). Este uso tuvo poco que ver con el trabajo de Husimi, y ahora se usa el término más pertinente grafo bloque para esta familia. Sin embargo, debido a esta ambigüedad, esta frase se usa con menos frecuencia para referirse a los grafos de cactus.

