En 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 no hay dos ciclos de aristas consecutivas que compartan ningún vértice entre sí, ni dos ciclos cualesquiera pueden estar conectados entre sí por una trayectoria 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 conexo sin ciclos; un bosque es una unión inconexa 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 de funciones de teoría de grafos y ocurren en varios problemas algorítmicos . Los pseudobosques son gráficos dispersos : su número de aristas está linealmente limitado 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 descomponer varias otras familias de gráficos dispersos. como uniones de bosques y pseudobosques. El nombre "pseudobosque" proviene de Picard y Queyranne (1982).
Definimos un gráfico 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 puntos finales) y bucles (aristas cuyos dos puntos finales son el mismo vértice). [1] Un subgrafo 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 tenga ambos puntos finales en el subconjunto de vértices. Un componente conectado de un gráfico no dirigido es el subgrafo que consta de los vértices y aristas que se pueden alcanzar siguiendo las aristas desde un único vértice inicial dado. Un gráfico es conexo si cada vértice o arista es accesible desde cualquier otro vértice o arista. Un ciclo en un gráfico no dirigido es un subgrafo conectado 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 solo árboles , mientras que los componentes que tienen un solo ciclo dentro de ellos se llaman 1-árboles o gráficos unicíclicos . Es decir, un árbol 1 es un gráfico conectado que contiene exactamente un ciclo. Un pseudobosque con un único componente conectado (generalmente 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 sean árboles o 1-árboles.
Si uno elimina de un árbol 1 uno de los bordes de su ciclo, el resultado es un árbol. Invirtiendo este proceso, si uno aumenta un árbol conectando dos de sus vértices cualesquiera mediante una nueva arista, 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 del árbol 1. 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 árboles 1 es comenzar con un solo ciclo y luego repetir esta operación de aumento tantas veces como desee. Los bordes de cualquier árbol 1 se pueden dividir de una 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]
También se han estudiado ciertos tipos más específicos de pseudobosques.
También se utilizan versiones de estas definiciones para gráficos dirigidos . Al igual que un gráfico no dirigido, un gráfico dirigido consta de vértices y aristas, pero cada arista está dirigida desde uno de sus puntos finales al otro punto final. Un pseudobosque dirigido es un gráfico dirigido en el que cada vértice tiene como máximo un borde saliente; es decir, tiene un grado superior como máximo a uno. Un bosque 1 dirigido , más comúnmente llamado gráfico funcional (ver más abajo), a veces pseudobosque dirigido máximo , es un gráfico dirigido en el que cada vértice tiene un grado superior a exactamente uno. [8] Si D es un pseudobosque dirigido, el gráfico no dirigido formado al eliminar la dirección de cada borde de D es un pseudobosque no dirigido.
Cada pseudobosque en un conjunto de n vértices tiene como máximo n aristas, y cada pseudobosque máximo en un conjunto de n vértices tiene exactamente n aristas. Por el contrario, si un gráfico G tiene la propiedad de que, para cada subconjunto S de sus vértices, el número de aristas en el subgrafo inducido de S es como máximo el número de vértices en S , entonces G es un pseudobosque. Los árboles 1 se pueden definir como gráficos conectados con el mismo número de vértices y aristas. [2]
Pasando de gráficos individuales a familias de gráficos, si una familia de gráficos tiene la propiedad de que cada subgrafo de un gráfico de la familia también está en la familia, y cada gráfico de la familia tiene como máximo tantas aristas como vértices, entonces la familia contiene sólo pseudobosques. Por ejemplo, cada subgrafo de un thrackle (un gráfico dibujado de modo que cada par de aristas tenga un punto de intersección) también es un thrackle, por lo que la conjetura de Conway de que cada thrackle tiene como máximo tantas aristas como vértices puede reformularse diciendo que cada thrackle tiene como máximo tantas aristas como vértices. thrackle es un pseudobosque. Una caracterización más precisa es que, si la conjetura es cierta, entonces los grilletes son exactamente pseudobosques sin ciclo de cuatro vértices y como máximo un ciclo impar. [9]
Streinu y Theran [10] generalizan las condiciones de escasez que definen los pseudobosques: definen un gráfico como ( k , l )-escaso si cada subgrafo no vacío con n vértices tiene como máximo kn − l aristas, y ( k , l )-apretado si es ( k , l ) -escaso y tiene exactamente kn − l aristas. Por lo tanto, los pseudobosques son los gráficos dispersos (1,0) y los pseudobosques máximos son los gráficos ajustados (1,0). Se pueden definir varias otras familias importantes de gráficos a partir de otros valores de k y l , y cuando l ≤ k , los gráficos ( k , l ) dispersos se pueden caracterizar como los gráficos formados como la unión de bordes disjuntos de l bosques y k − l pseudobosques. [11]
Casi todos los gráficos aleatorios suficientemente escasos son pseudobosques. [12] Es decir, si c es una constante con 0 < c < 1/2, y P c ( n ) es la probabilidad de que elegir uniformemente al azar entre los gráficos de n -vértices con aristas cn dé como resultado un pseudobosque, entonces P c ( n ) tiende a uno en el límite para n grande . Sin embargo, para c > 1/2, casi todos los gráficos aleatorios con aristas cn tienen un componente grande que no es unicíclico.
Un gráfico es simple si no tiene bucles automáticos ni aristas múltiples con los mismos puntos finales. El número de árboles 1 simples con n vértices etiquetados es [13]
Los valores para n hasta 300 se pueden encontrar en la secuencia OEIS : A057500 de la Enciclopedia en línea de secuencias enteras .
El número máximo de pseudobosques dirigidos en n vértices, que permiten bucles automáticos, es n n , porque para cada vértice hay n puntos finales posibles para el borde saliente. André Joyal utilizó este hecho para proporcionar una prueba biyectiva de la fórmula de Cayley , de que el número de árboles no dirigidos en n nodos es n n − 2 , al encontrar una biyección entre pseudobosques dirigidos máximos y árboles no dirigidos con dos nodos distinguidos. [14] Si no se permiten bucles automáticos, el número máximo de pseudobosques dirigidos es ( n − 1) n .
Los pseudobosques dirigidos y las endofunciones son, en cierto sentido, matemáticamente equivalentes. Cualquier función ƒ de un conjunto X consigo mismo (es decir, un endomorfismo de X ) puede interpretarse como la definición de un pseudobosque dirigido que tiene una arista de x a y siempre que ƒ( x ) = y . El pseudobosque dirigido resultante es máximo y puede incluir bucles automáticos siempre que algún valor x tenga ƒ( x ) = x . Alternativamente, omitir los bucles automáticos produce un pseudobosque no máximo. En la otra dirección, cualquier pseudobosque dirigido máximo determina una función ƒ tal que ƒ( x ) es el objetivo del borde que sale de x , y cualquier pseudobosque dirigido no máximo puede hacerse máximo agregando bucles propios y luego convertido en una función de la misma manera. Por esta razón, los pseudobosques máximos dirigidos a veces se denominan grafos funcionales . [2] Ver una función como un gráfico funcional proporciona un lenguaje conveniente para describir propiedades que no se describen tan fácilmente desde el punto de vista de la teoría de funciones; Esta técnica es especialmente aplicable a problemas que involucran funciones iteradas , que corresponden a rutas en gráficos funcionales.
La detección de ciclos , el problema de seguir un camino en un gráfico funcional para encontrar un ciclo en él, tiene aplicaciones en criptografía y teoría computacional de números , como parte del algoritmo rho de Pollard para la factorización de enteros y como método para encontrar colisiones en funciones hash criptográficas . En estas aplicaciones, se espera que ƒ se comporte aleatoriamente; Flajolet y Odlyzko [15] estudian las propiedades teóricas de grafos de los grafos funcionales que surgen de mapeos elegidos al azar. En particular, una forma de la paradoja del cumpleaños implica que, en un gráfico funcional aleatorio con n vértices, el camino que comienza desde un vértice seleccionado al azar normalmente volverá sobre sí mismo para formar un ciclo dentro de O ( √ n ) pasos. Konyagin et al. han logrado avances analíticos y computacionales en estadísticas de gráficos. [dieciséis]
Martin, Odlyzko y Wolfram [17] investigan pseudobosques que modelan la dinámica de los autómatas celulares . Estos grafos funcionales, a los que llaman diagramas de transición de estados , tienen un vértice para cada configuración posible en la que puede estar el conjunto de celdas del autómata, y un borde que conecta cada configuración con la configuración que le sigue según la regla del autómata. Se pueden inferir propiedades del autómata a partir de la estructura de estos diagramas, como el número de componentes, la longitud de los ciclos limitantes, la profundidad de los árboles que conectan estados no limitantes a estos ciclos o las simetrías del diagrama. Por ejemplo, cualquier vértice sin borde entrante corresponde a un patrón del Jardín del Edén y un vértice con un bucle propio corresponde a un patrón de naturaleza muerta .
Otra aplicación temprana de los gráficos funcionales se encuentra en los trenes utilizados para estudiar los sistemas triples de Steiner . [18] El tren de un sistema triple es un gráfico funcional que tiene un vértice para cada triple posible de símbolos; cada triple pqr se asigna mediante ƒ a stu , donde pqs , prt y qru son los triples que pertenecen al sistema triple y contienen los pares pq , pr y qr respectivamente. Se ha demostrado que los trenes son una poderosa invariante de los sistemas triples, aunque algo engorrosos de calcular.
Una matroide es una estructura matemática en la que ciertos conjuntos de elementos se definen como independientes , de tal manera que los conjuntos independientes satisfacen propiedades modeladas a partir de las propiedades de independencia lineal en un espacio vectorial . Uno de los ejemplos estándar de matroide es el matroide gráfico en el que los conjuntos independientes son los conjuntos de aristas en los bosques de un gráfico; La estructura matroide de los bosques es importante en los algoritmos para calcular el árbol de expansión mínimo del gráfico. De manera análoga, podemos definir matroides a partir de pseudobosques.
Para cualquier gráfico G = ( V , E ), podemos definir una matroide en las aristas de G , en la que un conjunto de aristas es independiente si y sólo si forma un pseudobosque; esta matroide se conoce como matroide bicircular (o matroide en bicicleta ) de G. [19] [20] Los conjuntos dependientes más pequeños para esta matroide son los subgrafos mínimos conectados de G que tienen más de un ciclo, y estos subgrafos a veces se denominan bicicletas. Hay tres tipos posibles de bicicleta: un gráfico theta tiene dos vértices que están conectados por tres caminos internamente disjuntos, un gráfico en forma de 8 consta de dos ciclos que comparten un solo vértice y un gráfico de esposas está formado por dos ciclos disjuntos conectados por un camino. . [21] Un gráfico es un pseudobosque si y sólo si no contiene una bicicleta como subgrafo.[10]
Formar una parte menor de un pseudobosque contrayendo algunos de sus bordes y eliminando otros produce otro pseudobosque. Por lo tanto, la familia de pseudobosques está cerrada bajo menores, y el teorema de Robertson-Seymour implica que los pseudobosques pueden caracterizarse en términos de un conjunto finito de menores prohibidos , de manera análoga al teorema de Wagner que caracteriza las gráficas planas como las gráficas que no tienen ni la gráfica completa K. 5 ni el gráfico bipartito completo K 3,3 como menores. Como se analizó anteriormente, cualquier gráfico que no sea pseudobosque contiene como subgrafo una esposa, figura 8 o gráfico theta; cualquier gráfico de esposas o figura de 8 se puede contraer para formar un gráfico de mariposa (figura 8 de cinco vértices), y cualquier gráfico theta se puede contraer para formar un gráfico de diamante (gráfico theta de cuatro vértices), [22] por lo que cualquier gráfico que no sea pseudobosque contiene una mariposa o un diamante como menor, y estos son los únicos gráficos menores-mínimos que no son pseudobosques. Así, un grafo es un pseudobosque si y sólo si no tiene la mariposa o el diamante como menores. Si uno prohíbe solo el diamante pero no la mariposa, la familia de gráficos más grande resultante consta de gráficos de cactus y uniones disjuntas de múltiples gráficos de cactus. [23]
Más simplemente, si se consideran multigrafos con bucles propios , sólo hay un menor prohibido, un vértice con dos bucles.
Un uso algorítmico temprano de pseudobosques involucra el algoritmo de red simplex y su aplicación a problemas de flujo generalizados que modelan la conversión entre productos de diferentes tipos. [3] [24] En estos problemas, se da como entrada una red de flujo en la que los vértices modelan cada producto y los bordes modelan las conversiones permitidas entre un producto y otro. Cada borde está marcado con una capacidad (la cantidad de un bien que se puede convertir por unidad de tiempo), un multiplicador de flujo (la tasa de conversión entre bienes) y un costo (cuánta pérdida o, si es negativa, ganancia se incurre por unidad de tiempo). conversión). La tarea es determinar qué cantidad de cada producto convertir a través de cada borde de la red de flujo, para minimizar el costo o maximizar las ganancias, obedeciendo al mismo tiempo las restricciones de capacidad y no permitiendo que productos de ningún tipo se acumulen sin usar. Este tipo de problema puede formularse como un programa lineal y resolverse utilizando el algoritmo simplex . Las soluciones intermedias que surgen de este algoritmo, así como la solución óptima final, tienen una estructura especial: cada borde en la red de entrada no se utiliza o se utiliza en su plena capacidad, excepto por un subconjunto de los bordes, que forman un pseudobosque de expansión. la red de entrada, para la cual los caudales pueden estar entre cero y la capacidad total. En esta aplicación, los gráficos unicíclicos también se denominan a veces árboles aumentados y los pseudobosques máximos también se denominan a veces bosques aumentados . [24]
El problema del pseudobosque de expansión mínima implica encontrar un pseudobosque de expansión de peso mínimo en un gráfico G ponderado por bordes más grande . Debido a la estructura matroide de los pseudobosques, se pueden encontrar pseudobosques máximos de peso mínimo mediante algoritmos codiciosos similares a los del problema del árbol de expansión mínima . Sin embargo, Gabow y Tarjan encontraron un enfoque de tiempo lineal más eficiente en este caso. [2]
La pseudoarboricidad de un gráfico G se define por analogía con la arboricidad como el número mínimo de pseudobosques en los que se pueden dividir sus bordes; de manera equivalente, es el mínimo k tal que G sea ( k ,0)-escaso, o el mínimo k tal que los bordes de G puedan orientarse para formar un gráfico dirigido con un grado exterior como máximo k . Debido a la estructura matroide de los pseudobosques, la pseudoarboricidad se puede calcular en tiempo polinomial. [25]
Un gráfico bipartito aleatorio con n vértices a cada lado de su bipartición, y con cn aristas elegidas independientemente al azar de cada uno de los n 2 posibles pares de vértices, es un pseudobosque con alta probabilidad siempre que c sea una constante estrictamente menor que uno. Este hecho juega un papel clave en el análisis del hashing cuco , una estructura de datos para buscar pares clave-valor buscando en una de las dos tablas hash ubicaciones determinadas a partir de la clave: se puede formar un gráfico, el "gráfico cuco", cuyos vértices corresponden a ubicaciones de la tabla hash y cuyos bordes unen las dos ubicaciones en las que se podría encontrar una de las claves, y el algoritmo hash cuco logra encontrar ubicaciones para todas sus claves si y sólo si el gráfico cuco es un pseudobosque. [26]
Los pseudobosques también desempeñan un papel clave en algoritmos paralelos para colorear gráficos y problemas relacionados. [27]
