Gráfico de cactus

En teoría de grafos , un cactus (a veces llamado árbol de cactus ) es un grafo conexo en el que dos ciclos simples cualesquiera tienen como máximo un vértice en común. De forma equivalente, es un grafo 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 vértice de corte ) es una arista o un ciclo.

Los cactus son grafos exteriores planares . Todo pseudoárbol es un cactus. Un grafo no trivial es un cactus si y solo si cada bloque es un ciclo simple o una arista simple.

La familia de grafos en la que cada componente es un cactus es cerrada hacia abajo bajo operaciones de menores de grafos . Esta familia de grafos puede caracterizarse por un único menor prohibido , el grafo diamante de cuatro vértices formado al eliminar una arista del grafo completo K ₄ . ^{[ 1 ]}

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

Los cactus triangulares tienen la propiedad de permanecer conectados 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. Todo árbol con un número impar de vértices puede ampliarse a un cactus triangular añadiéndole aristas, lo que da como resultado una ampliación mínima con la propiedad de permanecer conectado después de la eliminación de un emparejamiento. ^{[ 2 ]}

El cactus triangular más grande en cualquier grafo se puede encontrar en tiempo polinomial utilizando un algoritmo para el problema de paridad de matroides . Dado que los grafos de cactus triangulares son grafos planares , el cactus triangular más grande se puede usar como una aproximación al subgrafo planar más grande, un subproblema importante en la planarización . Como algoritmo de aproximación , este método tiene una razón de aproximación de 4/9, la mejor conocida para el problema del subgrafo planar 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 grafo dado en subconjuntos, con la propiedad de que cada triángulo del grafo tiene dos vértices en una sola clase de la partición de vértices o las tres aristas en una sola clase de la partición de aristas; 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.${\displaystyle {\mathcal {P}}=\{V_{1},V_{2},\dots ,V_{k}\}}$y${\displaystyle {\mathcal {Q}}=\{E_{1},E_{2},\dots ,E_{m}\}}$, de

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

dónde${\displaystyle n}$es el número de vértices en el grafo dado y${\displaystyle u_{i}}$es el número de clases de vértices que encuentra la clase de arista${\displaystyle E_{i}}$.

Cada gráfico plano${\displaystyle G}$contiene un subgrafo de cactus${\displaystyle C\subseteq G}$que incluye al menos${\displaystyle 1/6}$fracción de las caras triangulares de${\displaystyle G}$Este resultado implica un análisis directo del algoritmo de aproximación 4/9 para el problema del subgrafo planar máximo sin utilizar la fórmula min-max anterior. ^{[ 5 ]}

Algunos problemas de localización de instalaciones que son NP-difíciles para grafos generales, así como otros problemas de grafos, pueden resolverse en tiempo polinomial para cactus. ^{[ 7 ] [ 8 ]}

Dado que los cactus son casos especiales de grafos exteriores planares , se pueden resolver varios problemas de optimización combinatoria en grafos para ellos en tiempo polinomial . ^{[ 9 ]}

Los cactus representan circuitos eléctricos con propiedades útiles. Una aplicación temprana de los cactus se asoció con la representación de amplificadores operacionales. ^{[ 10 ] [ 11 ] [ 12 ]}

Los cactus también se han utilizado en genómica comparativa 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 a como máximo dos bloques, entonces se le llama cactus de Navidad . Todo grafo poliédrico tiene un subgrafo cactus de Navidad que incluye todos sus vértices, un hecho que juega un papel esencial en una demostración de Leighton y Moitra (2010) de que todo grafo poliédrico tiene una incrustación voraz en el plano euclidiano , una asignación de coordenadas a los vértices para la cual el reenvío voraz tiene éxito en el enrutamiento de mensajes entre todos los pares de vértices. ^{[ 14 ]}

En la teoría topológica de grafos , los grafos cuyas incrustaciones celulares son todas planas son precisamente la subfamilia de los grafos cactus con la propiedad adicional de que cada vértice pertenece a lo sumo a un ciclo. Estos grafos tienen dos menores prohibidos: el grafo diamante y el grafo de amistad de cinco vértices . ^{[ 15 ]}

Los cactus fueron estudiados por primera vez bajo el nombre de árboles de Husimi , otorgado por Frank Harary y George Eugene Uhlenbeck en honor al trabajo previo sobre estos gráficos realizado por 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 es estándar permitir ciclos de todas las longitudes.

Mientras tanto, el nombre árbol de Husimi pasó a referirse comúnmente a grafos en los que cada bloque es un grafo completo (o, equivalentemente, los grafos de intersección de los bloques en algún otro grafo). Este uso tenía poco que ver con el trabajo de Husimi, y actualmente se utiliza el término más pertinente grafo de bloques para esta familia; sin embargo, debido a esta ambigüedad, esta frase se usa con menos frecuencia para referirse a los grafos cactus. ^{[ 18 ]}

• Aplicación de gráficos de cactus en el análisis y diseño de circuitos electrónicos