Gráfico de cactus
En teoría de grafos , un cactus (a veces llamado árbol de cactus ) es un gráfico conectado en el que dos ciclos simples tienen como máximo un vértice en común. De manera equivalente, es un gráfico conectado en el que cada borde 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 un borde o un ciclo.
Los cactus son gráficos planos exteriores . Cada pseudotree es un cactus. Un gráfico no trivial es un cactus si y solo si cada bloque es un ciclo simple o un solo borde.
La familia de gráficos en la que cada componente es un cactus se cierra hacia abajo en las operaciones menores del gráfico . Esta familia de gráficos se puede caracterizar 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 de modo que cada ciclo tiene una longitud de tres y cada borde 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 solo 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 alguna coincidencia ; 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 aumentarse a un cactus triangular agregándole bordes, dando un aumento mínimo con la propiedad de permanecer conectado después de la eliminación de una coincidencia. [2]
El cactus triangular más grande en cualquier gráfico se puede encontrar en tiempo polinomial 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 subgráfico 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 de 4/9, la más conocida para el problema del subgráfico plano máximo. [3]
