pseudobosque
En la teoría de grafos , un pseudobosque es un grafo no dirigido [1] en el que cada componente conectado tiene como máximo un ciclo . Es decir, es un sistema de vértices y aristas que conectan pares de vértices, de modo que dos ciclos de aristas consecutivas no comparten ningún vértice entre sí, ni dos ciclos cualesquiera pueden estar conectados entre sí por un camino de aristas consecutivas. Un pseudoárbol es un pseudobosque conectado.
Los nombres se justifican por analogía con los árboles y bosques más comúnmente estudiados . (Un árbol es un gráfico conectado sin ciclos; un bosque es una unión disjunta de árboles). Gabow y Tarjan [2] atribuyen el estudio de los pseudobosques al libro de Dantzig de 1963 sobre programación lineal , en el que los pseudobosques surgen en la solución de cierta red problemas de flujo [3] Los pseudobosques también forman modelos teóricos de grafos de funciones y ocurren en varios problemas algorítmicos . Los pseudobosques son grafos dispersos– su número de aristas está acotado linealmente en términos de su número de vértices (de hecho, tienen como máximo tantas aristas como vértices) – y su estructura matroide permite que varias otras familias de grafos dispersos se descompongan como uniones de bosques y pseudobosques. El nombre "pseudobosque" proviene de Picard & Queyranne (1982) .
Definimos un grafo no dirigido como un conjunto de vértices y aristas tales que cada arista tiene dos vértices (que pueden coincidir) como puntos finales. Es decir, permitimos múltiples aristas (aristas con el mismo par de extremos) y bucles (aristas cuyos dos extremos son el mismo vértice). [1] Un subgráfico de un gráfico es el gráfico formado por cualquier subconjunto de sus vértices y aristas, de modo que cada arista en el subconjunto de aristas tiene ambos extremos en el subconjunto de vértices. Un componente conexo de un gráfico no dirigido es el subgrafo que consta de los vértices y las aristas a las que se puede llegar siguiendo las aristas desde un único vértice inicial dado. Un grafo es conexo si todos los vértices o aristas son accesibles desde todos los demás vértices o aristas. AEl ciclo en un grafo no dirigido es un subgrafo conexo en el que cada vértice incide exactamente en dos aristas, o es un bucle. [4]
Un pseudobosque es un gráfico no dirigido en el que cada componente conectado contiene como máximo un ciclo. [5] De manera equivalente, es un gráfico no dirigido en el que cada componente conectado no tiene más aristas que vértices. [6] Los componentes que no tienen ciclos son simplemente árboles , mientras que los componentes que tienen un solo ciclo dentro de ellos se denominan árboles 1 o grafos unicíclicos . Es decir, un árbol de 1 es un gráfico conexo que contiene exactamente un ciclo. Un pseudobosque con un solo componente conectado (normalmente llamado pseudoárbol ), aunque algunos autores definen un pseudoárbol como un 1-árbol) es un árbol o un 1-árbol; en general, un pseudobosque puede tener múltiples componentes conectados siempre que todos ellos sean árboles o 1-árboles.
Si uno elimina de un árbol 1 uno de los bordes en su ciclo, el resultado es un árbol. Invirtiendo este proceso, si uno aumenta un árbol conectando dos de sus vértices por un nuevo borde, el resultado es un árbol 1; la ruta en el árbol que conecta los dos puntos finales del borde agregado, junto con el borde agregado en sí, forman el ciclo único de 1-tree. Si uno aumenta un árbol 1 agregando un borde que conecta uno de sus vértices con un vértice recién agregado, el resultado es nuevamente un árbol 1, con un vértice más; un método alternativo para construir 1-trees es comenzar con un solo ciclo y luego repetir esta operación de aumento cualquier número de veces. Los bordes de cualquier árbol 1 se pueden dividir de manera única en dos subgrafos, uno de los cuales es un ciclo y el otro es un bosque, de modo que cada árbol del bosque contiene exactamente un vértice del ciclo.[7]
