Pseudo-bosque

En la teoría de grafos, un pseudobosque es un grafo no dirigido [1] en el que cualquier 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 no tienen vértices comunes y no pueden estar conectados por un camino. Un pseudo- árbol es un pseudo-bosque conectado.

Los nombres se toman por analogía con árboles y bosques conocidos (un árbol es un grafo conexo sin ciclos, un bosque es una unión de árboles desconectados). Gabov y Tarjan [2] atribuyen el estudio de los pseudobosques al libro de 1963 de Danzig sobre programación lineal , en el que los pseudobosques aparecen en la solución de algunos problemas de flujo de tráfico [3] . Los pseudobosques también forman modelos gráficos teóricos de funciones y aparecen en algunos problemas algorítmicos . Los pseudobosques son gráficos dispersos : tienen muy pocos bordes en relación con el número de vértices, y su estructura matroide permite que otras familias de gráficos dispersos se descompongan en una unión de bosques y pseudobosques. El nombre "pseudobosque" proviene de un artículo de Picard y Keran [4] .

Definiciones y estructura

Definimos un gráfico no dirigido como un conjunto de vértices y aristas tales que cada arista contiene dos vértices (posiblemente coincidentes) como puntos finales. Es decir, se permiten múltiples aristas (aristas con los mismos vértices finales) y bucles (aristas cuyos vértices finales son los mismos) [1] . Un subgrafo de un grafo es un grafo formado por un subconjunto de vértices y aristas, tal que cualquier arista en ese subconjunto tiene vértices terminales en el subconjunto de vértices. Un componente conexo de un grafo no dirigido es un subgrafo que consta de vértices y aristas a las que se puede llegar siguiendo las aristas a partir de un vértice inicial. Un grafo es conexo si cualquier vértice o arista se puede alcanzar desde cualquier otro vértice o arista. Un ciclo en un gráfico no dirigido es un subgrafo conexo en el que cualquier vértice incide exactamente en dos aristas o es un bucle.

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 , y los componentes que tienen un solo ciclo se denominan árboles de 1 o gráficos de un ciclo . Es decir, un árbol de 1 es un gráfico conexo que contiene exactamente un ciclo. Un pseudobosque con un solo componente conectado (comúnmente llamado pseudoárbol , aunque algunos autores definen un pseudoárbol como 1-árbol) es un árbol o 1-árbol. En general, un pseudobosque puede contener varios componentes conectados, todos los cuales son árboles o 1-árboles.

Si eliminamos uno de los bordes del bucle del árbol 1, obtenemos un árbol como resultado. En la dirección opuesta, si agregamos una nueva arista al árbol que conecta dos vértices cualesquiera, obtenemos un árbol 1. La ruta del árbol que conecta los dos puntos finales del arco agregado, junto con el propio arco agregado, forma un solo ciclo de 1 árbol. Si agregamos un borde al árbol 1 que conecta uno de los vértices del árbol con el vértice recién formado, el resultado será nuevamente un árbol 1 con un vértice más. Otro método para construir 1-árboles comienza con un solo ciclo, y los vértices se agregan secuencialmente al 1-árbol un número arbitrario de veces. Los bordes de cualquier árbol 1 se pueden dividir únicamente en dos subgrafos, uno de los cuales es un ciclo y el segundo es un bosque, y cada árbol del bosque contiene exactamente un vértice de ciclo [7]

También se están estudiando tipos de pseudobosques algo más estrechos.

Un 1-bosque , a veces llamado pseudobosque máximo , es un bosque al que no se le puede agregar ningún borde sin formar un gráfico con más de un ciclo. Si un pseudobosque contiene un árbol como uno de sus componentes, no puede ser un 1 bosque, porque puede agregar un borde a ese componente para recorrer ese componente, o puede agregar un borde que une el árbol con otro componente. Por lo tanto, los 1-bosques son exactamente pseudo-bosques en los que cada componente es un 1-árbol. Un pseudobosque de expansión de un grafo no dirigido G es un subgrafo de expansión que es un pseudobosque, es decir, un pseudobosque del grafo G que contiene todos los vértices del grafo G. Tales pseudobosques no están obligados a tener ningún borde, ya que, por ejemplo, un subgrafo vacío (es decir, que contiene todos los vértices del grafo G y no tiene ningún borde) es un pseudobosque (y sus componentes son árboles, cada uno de los cuales consta de de un solo vértice). Los pseudobosques máximos de G son los subgrafos de G que son pseudobosques que no están contenidos en ningún pseudobosque mayor contenido en G . El pseudobosque máximo de un grafo G siempre es un pseudoárbol de expansión, pero lo contrario no es cierto. Si G no tiene componentes conectados que sean árboles, entonces sus pseudobosques máximos son 1-bosques, pero si G tiene un árbol como componente, entonces sus pseudobosques máximos no serán 1-bosques. Más precisamente, en cualquier gráfico G , sus pseudobosques máximos consisten en todos los bosques de G junto con uno o más árboles 1 que cubren los vértices restantes de G.

Pseudobosques orientados

Las versiones de estas definiciones también se utilizan para gráficos dirigidos . Al igual que los gráficos no dirigidos, los gráficos dirigidos se componen de vértices y aristas, pero cada arista tiene una dirección (una arista dirigida suele llamarse arco). Un pseudobosque dirigido es un grafo dirigido en el que cada vértice tiene como máximo un arco saliente. Es decir, la gráfica tiene un grado de resultado que no excede de uno. Un 1-bosque dirigido , a menudo llamado gráfico funcional (ver más abajo ) y, a veces, pseudobosque dirigido al máximo , es un gráfico dirigido en el que cada vértice tiene un grado de salida de exactamente uno [8] . Si D es un pseudobosque dirigido, el gráfico no dirigido formado al eliminar direcciones de los bordes de D es un pseudobosque no dirigido.

Número de aristas

Cualquier pseudobosque en un conjunto de n vértices tiene como máximo n aristas, y cualquier pseudobosque máximo en un conjunto de n vértices tiene exactamente n vértices. Por el contrario, si un gráfico G tiene la propiedad de que para cualquier subconjunto S de vértices de gráfico, el número de aristas en un subgráfico generado del gráfico S no excede el número de vértices del gráfico 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] .

Para familias de grafos, si una familia de grafos tiene la propiedad de que cualquier subgrafo de un grafo en la familia está en la misma familia, y cada gráfico en la familia no tiene más bordes que vértices, entonces la familia contiene solo pseudobosques. Por ejemplo, cualquier subgrafo de un trackle (un gráfico dibujado de tal manera que cualquier par de aristas tiene un punto de intersección) también es un trackle, por lo que la hipótesis de Conway de que cualquier trackle no tiene más aristas que vértices puede reafirmarse que cada trackle es un pseudobosque. Más precisamente, si la conjetura es cierta, entonces los trekles son exactamente pseudobosques sin ciclos con cuatro vértices y como máximo un ciclo con un número impar de vértices [9] [10] .

Strainu y Teran [11] generalizaron las propiedades de la dispersión en la definición de pseudobosques: define un gráfico como ( k , l )-disperso si cualquier subgrafo no vacío con n vértices tiene como máximo kn  −  l aristas, y ( k , l )-denso si it ( k , l )-escaso y tiene exactamente kn  −  l aristas. Por lo tanto, los pseudobosques son gráficos dispersos (1,0) y los pseudobosques máximos son gráficos densos (1,0). Algunas otras familias importantes de grafos se pueden definir para otros valores de k y l , y si l  ≤  k , ( k , l )-grafos dispersos se pueden describir como grafos formados por la unión de l bosques sin bordes y k  −  l pseudobosques [12] .

Casi cualquier gráfico aleatorio suficientemente raro es un pseudobosque [13] . Es decir, si c es una constante (0 < c < 1/2) y P c ( n ) es la probabilidad de que un grafo elegido aleatoriamente entre n vértices y cn aristas sea un pseudobosque, entonces P c ( n ) tiende a uno en el límite a medida que n crece . Sin embargo, para c > 1/2, casi cualquier gráfico aleatorio con aristas cn tiene un componente grande que no es de ciclo único.

Enumeración

Un gráfico es simple si no tiene bucles o múltiples aristas. El número de árboles 1 simples con n vértices etiquetados es [14]

Los valores de n hasta 18 se pueden encontrar en la secuencia Encyclopedia of Integer Sequences A057500 .

El número máximo de pseudobosques de n vértices dirigidos donde se permiten bucles es n n , ya que para cualquier vértice hay n posibles vértices finales de arcos salientes. André Joyal usó este hecho para demostrar biyectivamente [15] la fórmula de Cayley de que el número de árboles no dirigidos en n vértices es igual a n n  − 2 al encontrar una biyección entre pseudobosques orientados al máximo y árboles no dirigidos con dos vértices diferentes [ 16] . Si se permiten bucles, el número máximo de pseudobosques dirigidos es ( n  − 1) n .

Gráficas de funciones

Los pseudobosques dirigidos y los automapas son, en cierto sentido, matemáticamente equivalentes. Cualquier mapeo de ƒ en un conjunto X sobre sí mismo (es decir, un endomorfismo en X ) puede interpretarse como la definición de un pseudobosque dirigido que tiene un arco de x a y cuando ƒ( x ) = y . El pseudobosque dirigido resultante es máximo y puede incluir bucles si para alguna x ƒ( x ) = x . La eliminación de bucles conduce a pseudobosques no máximos. En la dirección opuesta, cualquier pseudobosque con orientación maximal define un mapeo ƒ para el cual ƒ( x ) es igual al vértice final del arco que sale de x , y cualquier pseudobosque con orientación no maximal se puede hacer maximal agregando bucles y convirtiéndolo en una función en de la misma manera Por esta razón, los pseudobosques dirigidos al máximo a veces se denominan grafos funcionales [2] . Representar una función como un gráfico funcional proporciona un lenguaje conveniente para describir propiedades que no son fáciles de describir desde el punto de vista de la teoría de funciones. Esta técnica es especialmente útil para problemas que involucran funciones iteradas , que corresponden a caminos en la teoría de grafos.

Búsqueda de ciclos , el problema de rastrear rutas 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 ro de Pollard para factorización de enteros y como método para encontrar colisiones en hash criptográfico funciones _ Estas aplicaciones asumen que ƒ es aleatoria. Flajolet y Odlyzhko [17] estudiaron las propiedades de los gráficos funcionales obtenidos a partir de mapeos aleatorios. En particular, una versión de la paradoja del cumpleaños implica que en un gráfico funcional aleatorio con n vértices, la ruta que comienza en un vértice elegido al azar generalmente se repite después de O (√ n ) pasos. Konyagin y colaboradores realizaron análisis y estudios estadísticos computacionales [18] .

Martin, Odlyzko y Wolfram [19] han explorado pseudobosques que modelan la dinámica de los autómatas celulares . Estos son grafos funcionales, los llamaron diagramas de transición de estado , tienen un vértice para cada posible configuración en la que se pueden ubicar las celdas del autómata celular, y arcos conectan cada configuración que se obtiene de ella según las reglas del autómata celular. Es posible obtener propiedades de autómatas a partir de la estructura de estos diagramas, como el número de componentes, la longitud de los ciclos finitos, la profundidad de los árboles que conectan los estados no finales de estos ciclos o la simetría del diagrama. Por ejemplo, cualquier vértice sin arco entrante corresponde al Jardín del Edén , mientras que los vértices con bucle corresponden a una naturaleza muerta .

Otra aplicación temprana de los gráficos funcionales es en cadenas [20], que se utiliza para estudiar los sistemas triples de Steiner [21] [22] [23] . Una cadena de ternas es un grafo funcional que contiene un vértice para cada terna posible de símbolos. Cada triple pqr es mapeado por la función ƒ a stu , donde pqs , prt y qru  son triples pertenecientes al sistema de triples y contienen los pares pq , pr y qr respectivamente. Se ha demostrado que las cadenas son una poderosa invariante de un sistema triple, aunque su cálculo es engorroso.

Matroide bicíclica

Un matroide es una estructura matemática en la que determinados conjuntos de elementos se definen como independientes, en el sentido de que los conjuntos independientes cumplen propiedades que modelan las propiedades de independencia lineal en un espacio vectorial . Uno de los ejemplos estándar de matroides es el grafo matroid , en el que los conjuntos independientes son los conjuntos de aristas en los bosques del grafo. La estructura matroide de los bosques es importante para los algoritmos que calculan el árbol de expansión mínimo de un gráfico. De manera similar, se pueden definir matroides para pseudobosques.

Para cualquier grafo G = ( V , E ), podemos definir un matroide en las aristas de G en el que el conjunto de aristas es independiente si y sólo si este conjunto forma un pseudobosque. Esta matroide es conocida como la matroide bicíclica del grafo G [24] [25] . Los conjuntos dependientes mínimos para esta matroide son los subgrafos conectados mínimos de G que tienen más de un ciclo, y estos subgrafos a veces se denominan bicicletas. Hay tres tipos posibles de bicicletas: el gráfico theta tiene dos vértices conectados por tres caminos que no tienen puntos comunes internos, "ocho" consta de dos ciclos que tienen un vértice común y "esposas" está formado por dos ciclos que no tienen no tienen vértices comunes, conectados por [ 26] . Un grafo es un pseudobosque si y solo si no contiene una bicicleta como subgrafo [11] .

Menores ilegales

Formar un pseudobosque menor al contraer algunos bordes y eliminar algunos otros forma un nuevo pseudobosque. Por lo tanto, la familia de pseudobosques se cierra en menores, y del teorema de Robertson-Seymour se sigue que los pseudobosques se pueden describir en términos de un conjunto finito de menores prohibidos , similar al teorema de Wagner de describir grafos planos como grafos que no tienen ni un grafo completo K 5 ni un grafo bipartito completo K 3.3 como menores. Como se discutió anteriormente, cualquier gráfico que no sea pseudoforestal contiene esposas, ocho o theta como un subgráfico. Cualquier "esposas" y "ochos" se pueden contraer a una "mariposa" ("ocho" con cinco vértices), y cualquier gráfico "theta" se puede contraer a un " diamante " (gráfico "theta" con cuatro vértices) [27 ] , de modo que cualquier gráfico que no sea un pseudobosque contenga una "mariposa" o un "diamante" como menor, y solo estos gráficos son gráficos mínimos que no pertenecen a la familia de los pseudobosques. Si solo se prohíbe "diamante", pero no "mariposa", obtenemos una familia más amplia de gráficos, que consta de "cactus" y una unión dispar de un conjunto de "cactus" [28] .

Si consideramos multigrafos con bucles , solo hay un menor prohibido, un vértice con dos bucles.

Algoritmos

Una de las primeras aplicaciones algorítmicas de los pseudobosques utilizó el algoritmo de red símplex y su aplicación al problema de flujo de red generalizado para modelar transformaciones de productos de un tipo a otro [3] [29] . En estos problemas se define una red de transporte , en la que los vértices modelan cada producto, y las aristas modelan la admisibilidad de la transformación de un producto a otro. Cada borde está etiquetado como rendimiento (la cantidad de producto que se puede convertir por unidad de tiempo), flujo (la tasa de conversión entre productos) y precio (cuánto perdemos en la conversión por unidad de producto). El desafío es determinar cuánto de cada producto debe convertirse en cada arco de la red de transporte para minimizar los costos o maximizar los ingresos sin violar la restricción y sin permitir que ningún tipo de producto quede sin usar. Este tipo de problema puede formularse como un problema de programación lineal y resolverse mediante el método símplex . Las soluciones intermedias obtenidas de este algoritmo, así como la solución óptima final, tienen estructuras especiales: cada arco de la red de transporte no se usa o usa el ancho de banda máximo, con la excepción de un subconjunto de arcos que forman el pseudobosque central de la red. red de transporte, y en este subconjunto de arcos el flujo puede tomar un valor desde cero hasta el rendimiento máximo. En esta aplicación, los gráficos de un ciclo a veces también se denominan árboles aumentados , y los pseudobosques máximos también se denominan bosques aumentados [29] .

El problema del pseudobosque de expansión mínima utiliza la búsqueda de un pseudobosque de expansión de peso mínimo en un gráfico G más grande con pesos. Debido a la estructura matroide de los pseudobosques, se pueden encontrar pseudobosques máximos con un peso mínimo utilizando algoritmos codiciosos, similares al problema del árbol de expansión mínimo . Sin embargo, Gabov y Tarjan encontraron un enfoque de tiempo lineal más eficiente para este caso [2] .

El pseudo-treeness de un gráfico G se define por analogía con el treeness como el número mínimo de pseudobosques en los que se pueden dividir los bordes. De manera equivalente, es el número mínimo k tal que el gráfico G es ( k , 0)-disperso, o el número mínimo k tal que los bordes del gráfico G pueden orientarse de manera que el gráfico dirigido resultante tenga un grado de salida como máximo k _ Debido a la estructura matroide de los pseudobosques, el pseudoárbol se puede calcular en tiempo polinomial [30]

Un grafo bipartito aleatorio con n vértices en cada una de sus partes con cn aristas elegidas al azar e independientemente para cada par de n 2 posibles pares de vértices es un pseudobosque con una alta probabilidad de una constante c estrictamente menor que uno. Este hecho juega un papel clave en el análisis de cuckoo hashing [31] , una estructura de datos para encontrar pares clave-valor mirando una de las dos tablas hash en la ubicación determinada por la clave; uno puede formar un "gráfico emparejado". cuyos vértices corresponden a la posición de la ubicación en las tablas hash, y las aristas unen dos ubicaciones donde se puede encontrar una de las claves. El hashing por pares encuentra todas las claves si y solo si el gráfico emparejado es un pseudobosque [32] .

Los pseudobosques también juegan un papel clave en los algoritmos de coloreado de gráficos paralelos y problemas relacionados [33] [34] .

Notas

  1. ↑ 1 2 Los gráficos no dirigidos considerados aquí son multigrafos o seudógrafos, no gráficos simples .
  2. ↑ 1 2 3 4 Gabow, Tarjan, 1988 .
  3. ↑ 12 Dantzig , 1963 .
  4. ↑ Picard, Queyranne, 1982 .
  5. ↑ Esta definición, por ejemplo, es utilizada por Gabow y Westermann ( Gabow, Westermann (1992 )).
  6. ↑ Esta definición es utilizada por Gabow y Tarjan ( Gabow, Tarjan (1988 )).
  7. ↑ Véase, por ejemplo, la demostración del Lema 4 en Alvarez, Bles y Cern ( Àlvarez et al (2002 )).
  8. ↑ Krusk, Rudolf y Snir ( Kruskal et al (1990 )) en su lugar usan la definición inversa, en la que cada vértice tiene un grado de entrada de uno. Los gráficos resultantes, a los que denominan monociclo , son los gráficos transpuestos de los gráficos considerados en este trabajo.
  9. ↑ Woodall, 1969 .
  10. ↑ Lovász et al, 1997 .
  11. ↑ 12 Streinu, Theran, 2009 .
  12. ↑ Whiteley, 1988 .
  13. ↑ Bolobash ( Bollobás (1985 )). Ver, en particular, el Corolario 24, página 120, para un límite en el número de vértices pertenecientes a componentes de un ciclo en un grafo aleatorio, y el Corolario 19, página 113, para un límite en el número de componentes diferentes etiquetados de un ciclo. gráficos de ciclo
  14. ↑ Riddell (1951 ); consulte A057500 en Encyclopedia of Integer Sequences .
  15. ↑ Puedes leer sobre el método de prueba biyectiva en el artículo de Vershik ( Vershik (1986 ))
  16. ↑ Aigner, Ziegler, 1998 .
  17. ↑ Flajolet, Odlyzko, 1990 .
  18. ↑ Konyagin y otros, 2016 .
  19. ↑ Martín, Odlyzko, Wolfram, 1984 .
  20. ↑ En la versión en inglés - trenes
  21. ↑ Blanco, 1913 .
  22. ↑ Colbourn, Colbourn, Rosenbaum, 1982 .
  23. ↑ Stinson, 1983 .
  24. ↑ Simoes-Pereira, 1972 .
  25. ↑ Matthews, 1977 .
  26. ↑ Glosario de gráficos firmados y de ganancia y áreas afines . Consultado el 23 de octubre de 2016. Archivado desde el original el 3 de marzo de 2016.
  27. ↑ Para conocer esta terminología, consulte la lista de gráficos pequeños . Archivado el 22 de julio de 2012 en Wayback Machine desde Information System on Graph Class Inclusions. Archivado el 5 de febrero de 2019 en Wayback Machine . Sin embargo, la mariposa puede referirse a una familia diferente de gráficos, relacionados con los hipercubos .
  28. ↑ El Mallah, Colbourn, 1988 .
  29. ↑ 1 2 Ahuja, Magnanti, Orlin, 1993 .
  30. ↑ Gabow, Westermann (1992 ). Véase también los esquemas de aproximación rápida de Kowalik ( Kowalik (2006 )).
  31. ↑ . En términos generales, el término no tiene éxito, pero se ha arraigado en la literatura en idioma ruso (como una traducción directa de hash de cuco ). Aparentemente, el término surgió debido al emparejamiento de "cuco". El método debe llamarse hashing emparejado o de dos etapas.
  32. ↑ Kutzelnigg, 2006 .
  33. ↑ Goldberg, Plotkin, Shannon, 1988 .
  34. ↑ Kruskal y otros, 1990 .

Literatura

Enlaces