Pseudoforestal

Un bosque 1 (un seudofosque máximo), formado por tres árboles 1

En la teoría de grafos , un pseudoforestal 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 pueden estar conectados entre sí por una trayectoria de aristas consecutivas. Un pseudotree es un pseudoforest 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 pseudoforestes al libro de Dantzig de 1963 sobre programación lineal , en el que los pseudoforestales surgen en la solución de cierta red problemas de flujo . ^{[3] Los} pseudoforestales también forman modelos de funciones de teoría de grafos y ocurren en varios problemas algorítmicos . Los pseudoforestales son gráficos 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 tantos aristas como vértices) - y su estructura matroide permite que varias otras familias de grafos dispersos se descompongan como uniones de bosques y pseudoforestales. El nombre "pseudoforestal" proviene de Picard & Queyranne (1982) .

Definiciones y estructura

Definimos un gráfico no dirigido como un conjunto de vértices y aristas de modo que cada arista tenga 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 del subconjunto de aristas tenga ambos extremos en el subconjunto de vértices. Un componente conectado de un gráfico no dirigido es el subgráfico que consta de los vértices y los bordes que se pueden alcanzar siguiendo los bordes desde un único vértice inicial dado. Un gráfico está conectado si todos los vértices o aristas son accesibles desde todos los demás vértices o aristas. AEl ciclo en un gráfico no dirigido es un subgráfico conectado en el que cada vértice incide exactamente en dos aristas, o es un bucle. ^[4]

Los 21 gráficos unicíclicos con un máximo de seis vértices

Un pseudoforestal 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 gráficos unicíclicos . Es decir, un árbol 1 es un gráfico conectado que contiene exactamente un ciclo. Un pseudoforestal con un solo componente conectado (generalmente llamado pseudotree, aunque algunos autores definen un pseudotree como un árbol 1) es un árbol o un árbol 1; en general, un pseudoforestal puede tener múltiples componentes conectados siempre que todos sean árboles o árboles 1.

Si uno quita de un árbol 1 uno de los bordes en su ciclo, el resultado es un árbol. Invirtiendo este proceso, si se aumenta un árbol conectando dos de sus vértices con 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 se aumenta un árbol 1 agregando una arista 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 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]

También se han estudiado ciertos tipos más específicos de pseudoforestales.

Un bosque 1 , a veces llamado pseudoforestal máximo , es un pseudofosque al que no se pueden agregar más bordes sin que algún componente del gráfico contenga múltiples ciclos. Si un pseudoforestal contiene un árbol como uno de sus componentes, no puede ser un bosque 1, ya que se puede agregar un borde que conecte dos vértices dentro de ese árbol, formando un solo ciclo, o un borde que conecte ese árbol con algún otro componente. Por lo tanto, los bosques 1 son exactamente los pseudoforestales en los que cada componente es un árbol 1.

Los pseudoforests que abarcan de un grafo no dirigido G son los pseudoforest subgraphs de G que tienen todos los vértices de G . Un pseudoforestal de este tipo no necesita tener aristas, ya que, por ejemplo, el subgrafo que tiene todos los vértices de G y no tiene aristas es un pseudoforestal (cuyos componentes son árboles que constan de un solo vértice).

Los pseudoforests máximas de G son los subgrafos pseudoforest de G que no están contenidas dentro de cualquier pseudoforest mayor de G . Un seudofosque máximo de G es siempre un seudofosque que se extiende, pero no a la inversa. Si G no tiene componentes conectados que sean árboles, entonces sus pseudoforestas máximas son 1-bosques, pero si G tiene un componente arbóreo, sus pseudoforestas máximas no son 1-bosques. Dicho exactamente, en cualquier gráfico G sus pseudoforests máximas consisten en todos los componentes del árbol de G , junto con uno o más disjuntos 1-árboles que cubren los vértices restantes de G .

Seudoforestales dirigidos

Las versiones de estas definiciones también se utilizan 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 se dirige desde uno de sus extremos al otro extremo. Un pseudoforesto dirigido es un gráfico dirigido en el que cada vértice tiene como máximo un borde de salida; es decir, tiene un grado superior a como máximo uno. Un bosque 1 dirigido , más comúnmente llamado gráfico funcional (ver más abajo ), a veces seudoforesco dirigido máximo , es un gráfico dirigido en el que cada vértice tiene un grado superior exactamente a uno. ^[8] Si Des un pseudoforestal dirigido, el gráfico no dirigido formado al eliminar la dirección de cada borde de D es un pseudoforestal no dirigido.

Numero de aristas

Cada pseudoforestal en un conjunto de n vértices tiene como máximo n aristas, y cada pseudoforestal 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 pseudofosque. Los árboles 1 se pueden definir como gráficos conectados con la misma cantidad de vértices y aristas. ^[2]

Pasando de grafos individuales a familias de grafos, si una familia de grafos tiene la propiedad de que cada subgrafo de un grafo de la familia también pertenece a la familia, y cada grafo de la familia tiene como máximo tantas aristas como vértices, entonces la familia contiene solo pseudoforestales. Por ejemplo, cada subgrafo de un thrackle (un gráfico dibujado de modo que cada par de aristas tenga un punto de intersección) es también un thrackle, por lo que la conjetura de Conway de que cada thrackle tiene como máximo tantos aristas como vértices puede reformularse diciendo que cada thrackle es un pseudoforestal. Una caracterización más precisa es que, si la conjetura es cierta, entonces los esclavos son exactamente los pseudoforestales sin ciclo de cuatro vértices y como máximo con un ciclo impar. ^[9]

Streinu y Theran ^[10] generalizan las condiciones de escasez que definen a los pseudoforestales: definen un grafo como ( k , l ) -sparse si cada subgrafo no vacío con n vértices tiene como máximo kn  -  l bordes, y ( k , l ) -tight si es ( k , l ) -espacio y tiene exactamente kn  -  l bordes. Por lo tanto, los pseudoforestales son los gráficos dispersos (1,0), y los pseudoforestales máximos son los gráficos ajustados (1,0). Varias otras familias importantes de gráficos pueden definirse a partir de otros valores de k y l, y cuando l  ≤  k las gráficas ( k , l ) -sparse pueden caracterizarse como las gráficas formadas como la unión borde-disjunta de l bosques y k  -  l pseudoforestas. ^[11]

Casi todos los gráficos aleatorios suficientemente dispersos son seudoforestales. ^[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 las n gráficas de n -vértices con cn aristas resulte en un pseudoforestal, entonces P _c ( n ) tiende a uno en el límite para n grandes . Sin embargo, para c > 1/2, casi todos los gráficos aleatorios con aristas cn tienen un componente grande que no es unicíclico.

Enumeración

Un gráfico es simple si no tiene bucles propios ni múltiples aristas con los mismos puntos finales. El número de árboles 1 simples con n vértices etiquetados es ^[13]

${\displaystyle n\sum _{k=1}^{n}{\frac {(-1)^{k-1}}{k}}\sum _{n_{1}+\cdots +n_{k}=n}{\frac {n!}{n_{1}!\cdots n_{k}!}}{\binom {{\binom {n_{1}}{2}}+\cdots +{\binom {n_{k}}{2}}}{n}}.}$

Los valores de n hasta 300 se pueden encontrar en la secuencia OEIS :  A057500 de la Enciclopedia en línea de secuencias de enteros .

El número de pseudoforestas máximas dirigidas en n vértices, que permiten auto-bucles, es n ⁿ , porque para cada vértice hay n posibles puntos finales para el borde de salida. André Joyal usó este hecho para proporcionar una prueba biyectiva de la fórmula de Cayley , que el número de árboles no dirigidos en n nodos es n ^{n  - 2} , al encontrar una biyección entre pseudoforestales 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 pseudoforestales dirigidos es ( n  - 1) ⁿ .

Gráficos de funciones

El "gráfico funcional" vuelve a dirigir aquí. Para otros usos, consulte Gráfico de una función .

Una función del conjunto {0,1,2,3,4,5,6,7,8} a ​​sí mismo, y el gráfico funcional correspondiente

Los pseudoforestales dirigidos y las funciones terminales son, en cierto sentido, matemáticamente equivalentes. Cualquier función ƒ partir de un conjunto X a sí misma (es decir, un endomorphism de X ) se puede interpretar como la definición de una pseudoforest dirigido que tiene un borde de x a y siempre que ƒ ( x ) = y . El pseudofosque dirigido resultante es máximo y puede incluir bucles propios siempre que algún valor x tenga ƒ ( x ) = x. Alternativamente, omitir los bucles propios produce un pseudoforestal no máximo. En la otra dirección, cualquier pseudoforesto dirigido máximo determina una función f tal que f ( x ) es el objetivo del borde que sale de x , y cualquier pseudoforesto 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 pseudoforestes máximos dirigidos a veces se denominan gráficos 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 la función; 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 una ruta en un gráfico funcional para encontrar un ciclo en él, tiene aplicaciones en criptografía y teoría numérica computacional , 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 f se comporte de forma aleatoria; Flajolet y Odlyzko ^[15] estudian las propiedades teóricas de los gráficos funcionales que surgen de mapeos elegidos aleatoriamente. En particular, una forma de la paradoja del cumpleaños implica que, en un gráfico funcional aleatorio con nvértices, la ruta que comienza a partir de un vértice seleccionado al azar normalmente se repetirá sobre sí misma para formar un ciclo dentro de O ( √ n ) pasos. Konyagin y col. han logrado avances analíticos y computacionales en estadísticas de gráficos. ^[dieciséis]

Martin, Odlyzko y Wolfram ^[17] investigan pseudoforestales que modelan la dinámica de los autómatas celulares . Estos gráficos funcionales, a los que denominan diagramas de transición de estados , tienen un vértice por cada configuración posible en la que puede estar el conjunto de células 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 duración de los ciclos limitantes, la profundidad de los árboles que conectan los estados no limitantes con 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ény 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 posible triple de símbolos; cada triple pqr es mapeado por ƒ 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 engorrosa de calcular.

Matroide bicircular

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 una matroide es la matroide gráfica en la 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 de pseudoforestales.

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 solo si forma un pseudofosque; este matroid se conoce como el matroid bicircular (o matroid bicicleta ) de G . ^{[19] [20]} Los conjuntos dependientes más pequeños para este 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 bicicleta: un gráfico thetatiene dos vértices que están conectados por tres rutas disjuntas internamente, 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 una ruta. ^[21] Un gráfico es un pseudoforestal si y solo si no contiene una bicicleta como subgráfico.^[10]

Menores prohibidos

El gráfico de mariposas (izquierda) y el gráfico de diamantes (derecha), menores prohibidos para pseudoforestales

Formar un menor de un pseudoforestal contrayendo algunos de sus bordes y eliminando otros produce otro pseudoforestal. Por lo tanto, la familia de pseudoforestas está cerrada bajo menores, y el teorema de Robertson-Seymour implica que los pseudoforestales pueden caracterizarse en términos de un conjunto finito de menores prohibidos , de manera análoga al teorema de Wagner que caracteriza los gráficos planares como los gráficos que no tienen ni el gráfico completo K ₅ ni el gráfico bipartito completo K _3,3como menores. Como se discutió anteriormente, cualquier gráfico que no sea pseudoforestal contiene como subgráfico un gráfico de esposas, figura 8 o theta; cualquier gráfico de esposas o figura 8 puede contraerse para formar un gráfico de mariposa (figura 8 de cinco vértices), y cualquier gráfico theta puede contraerse para formar un gráfico de diamante (gráfico theta de cuatro vértices), ^[22] por lo que cualquier no pseudoforestal contiene una mariposa o un diamante como menor, y estos son los únicos gráficos que no son pseudoforestales menores y mínimos. Así, una gráfica es un pseudoforestal si y solo si no tiene la mariposa o el diamante como menor. Si se prohíbe solo el diamante pero no la mariposa, la familia de gráficos más grande resultante consiste en los gráficos de cactus y las uniones disjuntas de varios gráficos de cactus. ^[23]

Más simplemente, si se consideran los gráficos múltiples con bucles propios, solo hay un menor prohibido, un vértice con dos bucles.

Algoritmos

Un uso algorítmico temprano de los pseudoforestales 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 producto que se puede convertir por unidad de tiempo), un multiplicador de flujo (la tasa de conversión entre productos) y un costo.(cuánta pérdida o, si es negativa, ganancia se incurre por unidad de conversión). La tarea es determinar qué cantidad de cada producto convertir a través de cada borde de la red de flujo, con el fin de minimizar el costo o maximizar las ganancias, mientras se obedecen las limitaciones de capacidad y no se permite que los 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 eventual, tienen una estructura especial: cada borde de la red de entrada no se utiliza o se utiliza en su máxima capacidad, a excepción de un subconjunto de los bordes, formando un pseudofosque que se extiende de la red de entrada, para la cual las cantidades de flujo 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 pseudoforestes máximos también se denominan a veces bosques aumentados . ^[24]

El problema de pseudoforesis de extensión mínima implica encontrar un pseudoforestal de extensión de peso mínimo en un gráfico G de borde ponderado más grande . Debido a la estructura matroide de los pseudoforestales, se pueden encontrar pseudoforestales de peso mínimo y máximo mediante algoritmos codiciosos similares a los del problema del árbol de expansión mínimo . Sin embargo, Gabow y Tarjan encontraron un enfoque de tiempo lineal más eficiente en este caso. ^[2]

La pseudoarboricidad de un grafo G se define por analogía con la arboricidad como el número mínimo de pseudoforestales en los que se pueden dividir sus bordes; de manera equivalente, es el mínimo k tal que G es ( k , 0) -espacio, o el mínimo k tal que los bordes de G se pueden orientar para formar un gráfico dirigido con fuera de grado como máximo k . Debido a la estructura matroide de los pseudoforestales, la pseudoarboricidad puede calcularse en tiempo polinomial. ^[25]

Un grafo 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 ² posibles pares de vértices, es un pseudoforestal con alta probabilidad siempre que c sea ​​una constante estrictamente menor que uno. Este hecho juega un papel clave en el análisis del hash de cuco., una estructura de datos para buscar pares clave-valor al buscar en una de las dos tablas hash en ubicaciones determinadas a partir de la clave: se puede formar un gráfico, el "gráfico cuco", cuyos vértices corresponden a las ubicaciones de la tabla hash y cuyos bordes vinculan el dos ubicaciones en las que se puede encontrar una de las claves, y el algoritmo de hash de cuco logra encontrar ubicaciones para todas sus claves si y solo si el gráfico de cuco es un pseudoforestal. ^[26]

Los pseudoforestales también juegan un papel clave en los algoritmos paralelos para colorear gráficos y problemas relacionados. ^[27]

Notas

1. El tipo de gráfico no dirigido que se considera aquí a menudo se denomina multigrafo o pseudógrafo, para distinguirlo de un gráfico simple .
2. Gabow y Tarjan (1988) .
3. Dantzig (1963) .
4. Consulte los artículos vinculados y las referencias en los mismos para conocer estas definiciones.
5. Ésta es la definición utilizada, por ejemplo, por Gabow & Westermann (1992) .
6. Ésta es la definición en Gabow & Tarjan (1988) .
7. Ver, por ejemplo, la demostración del Lema 4 en Àlvarez, Blesa & Serna (2002) .
8. Kruskal, Rudolph & Snir (1990) en su lugar utilizan la definición opuesta, en la que cada vértice tiene uno por debajo; los gráficos resultantes, que ellos denominan uniciculares , son las transposiciones de los gráficos aquí considerados.
9. Woodall (1969) ; Lovász, Pach y Szegedy (1997) .
10. Streinu y Theran (2009) .
11. Whiteley (1988) .
12. Bollobás (1985) . Ver especialmente el Corolario 24, p.120, para un límite en el número de vértices que pertenecen a componentes unicíclicos en un gráfico aleatorio, y el Corolario 19, p.113, para un límite en el número de gráficos unicíclicos etiquetados distintos.
13. Riddell (1951) ; consulte OEIS :  A057500 en la Enciclopedia en línea de secuencias de enteros .
14. Aigner y Ziegler (1998) .
15. Flajolet y Odlyzko (1990) .
16. Konyagin y col. (2010) .
17. Martin, Odlyzko y Wolfram (1984) .
18. Blanco (1913) ; Colbourn, Colbourn y Rosenbaum (1982) ; Stinson (1983) .
19. Simoes-Pereira (1972) .
20. Matthews (1977) .
21. Glosario de gráficos firmados y de ganancia y áreas afines
22. Para esta terminología, consulte la lista de gráficos pequeños del Sistema de información sobre inclusiones de clases de gráficos . Sin embargo, el gráfico de mariposa también puede referirse a una familia diferente de gráficos relacionados con los hipercubos , y la figura 8 de cinco vértices a veces se denomina gráfico de pajarita .
23. El-Mallah y Colbourn (1988) .
24. Ahuja, Magnanti y Orlin (1993) .
25. Gabow y Westermann (1992) . Véanse también los esquemas de aproximación más rápidos de Kowalik (2006) .
26. Kutzelnigg (2006) .
27. Goldberg, Plotkin y Shannon (1988) ; Kruskal, Rudolph y Snir (1990) .

Referencias

• Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993), Flujos de red: teoría, algoritmos y aplicaciones , Prentice Hall, ISBN 0-13-617549-X.
• Aigner, Martin ; Ziegler, Günter M. (1998), Pruebas de EL LIBRO , Springer-Verlag , págs. 141-146.
• Álvarez, Carme; Blesa, Maria; Serna, Maria (2002), "Estabilidad universal de grafos no dirigidos en el modelo de cola adversarial", Proc. 14 ° Simposio de ACM sobre algoritmos y arquitecturas paralelas , págs. 183–197, doi : 10.1145 / 564870.564903 , hdl : 2117/97553 , S2CID  14384161.
• Bollobás, Béla (1985), Random Graphs , Academic Press.
• Colbourn, Marlene J .; Colbourn, Charles J .; Rosenbaum, Wilf L. (1982), "Trenes: un invariante para los sistemas triples de Steiner", Ars Combinatoria , 13 : 149-162, MR  0666934.
• Dantzig, GB (1963), Programación lineal y extensiones , Princeton University Press.
• El-Mallah, Ehab; Colbourn, Charles J. (1988), "La complejidad de algunos problemas de eliminación de bordes", IEEE Transactions on Circuits and Systems , 35 (3): 354–362, doi : 10.1109 / 31.1748.
• Flajolet, P .; Odlyzko, A. (1990), "Estadísticas de mapeo aleatorio", Advances in Cryptology - EUROCRYPT '89: Workshop on the Theory and Application of Cryptographic Techniques , Lecture Notes in Computer Science, 434 , Springer-Verlag, pp. 329–354.
• Gabow, HN ; Tarjan, RE (1988), "Un algoritmo de tiempo lineal para encontrar un pseudoforesto de extensión mínima", Information Processing Letters , 27 (5): 259-263, doi : 10.1016 / 0020-0190 (88) 90089-0.
• Gabow, HN ; Westermann, HH (1992), "Bosques, marcos y juegos: algoritmos para sumas y aplicaciones matroides", Algorithmica , 7 (1): 465–497, doi : 10.1007 / BF01758774 , S2CID  40358357.
• Goldberg, AV ; Plotkin, SA; Shannon, GE (1988), "Ruptura de simetría paralela en gráficos dispersos" , SIAM Journal on Discrete Mathematics , 1 (4): 434–446, doi : 10.1137 / 0401044.
• Konyagin, Sergei; Luca, Florian; Mans, Bernard; Mathieson, Luke; Shparlinski, Igor E. (2010), Gráficos funcionales de polinomios sobre campos finitos
• Kowalik, Ł. (2006), "Esquema de aproximación para medidas de densidad de gráficos y orientación de grado más bajo", en Asano, Tetsuo (ed.), Actas del Simposio internacional sobre algoritmos y computación , Lecture Notes in Computer Science, 4288 , Springer-Verlag, págs. 557–566, doi : 10.1007 / 11940128 , ISBN 978-3-540-49694-6.
• Kruskal, Clyde P .; Rudolph, Larry; Snir, Marc (1990), "Algoritmos paralelos eficientes para problemas de gráficos", Algorithmica , 5 (1): 43–64, doi : 10.1007 / BF01840376 , S2CID  753980.
• Picard, Jean-Claude; Queyranne, Maurice (1982), "Una solución de flujo de red para algunos problemas de programación 0-1 no lineales, con aplicaciones a la teoría de grafos", Redes , 12 (2): 141-159, doi : 10.1002 / net.3230120206 , MR  0670021.
• Kutzelnigg, Reinhard (2006), "Gráficos aleatorios bipartitos y hash de cuco" , Cuarto Coloquio sobre Matemáticas y Ciencias de la Computación , Matemáticas Discretas y Ciencias de la Computación Teórica, AG , págs. 403–406.
• Lovász, L .; Pach, J .; Szegedy, M. (1997), "Sobre la conjetura de la esclavitud de Conway", Geometría discreta y computacional , 18 (4): 369-376, doi : 10.1007 / PL00009322.
• Martin, O .; Odlyzko, AM ; Wolfram, S. (1984), "Propiedades algebraicas de los autómatas celulares" , Communications in Mathematical Physics , 93 (2): 219–258, Bibcode : 1984CMaPh..93..219M , doi : 10.1007 / BF01223745 , S2CID  6900060.
• Matthews, LR (1977), "Matroides bicirculares", The Quarterly Journal of Mathematics , Segunda serie, 28 (110): 213-227, doi : 10.1093 / qmath / 28.2.213 , MR  0505702.
• Riddell, RJ (1951), Contribuciones a la teoría de la condensación , Ph.D. tesis, Ann Arbor: Universidad de Michigan, Bibcode : 1951PhDT ........ 20R.
• Simoes-Pereira, JMS (1972), "On subgraphs as matroid cells", Mathematische Zeitschrift , 127 (4): 315–322, doi : 10.1007 / BF01111390.
• Stinson, DR (1983), "Una comparación de dos invariantes para los sistemas triples de Steiner: fragmentos y trenes", Ars Combinatoria , 16 : 69-76, MR  0734047.
• Streinu, I .; Theran, L. (2009), "Descomposiciones de gráficos que certifican la dispersión", Gráficos y combinatorios , 25 (2): 219, arXiv : 0704.0002 , doi : 10.1007 / s00373-008-0834-4 , S2CID  15877017.
• White, HS (1913), "Sistemas triples como transformaciones y sus caminos entre tríadas", Transactions of the American Mathematical Society , American Mathematical Society, 14 (1): 6-13, doi : 10.2307 / 1988765 , JSTOR  1988765.
• Whiteley, W. (1988), "La unión de matroides y la rigidez de los marcos", SIAM Journal on Discrete Mathematics , 1 (2): 237-255, doi : 10.1137 / 0401025.
• Woodall, DR (1969), "Thrackles and deadlock", en galés, DJA (ed.), Combinatorial Mathematics and Its Applications , Academic Press, págs. 335–348.

enlaces externos

• Weisstein, Eric W. , "Gráfico unicíclico" , MathWorld