Base del ciclo

Ciclos en un gráfico que generan todos los ciclos

La diferencia simétrica de dos ciclos es un subgrafo euleriano

En teoría de grafos , una rama de las matemáticas, una base de ciclo de un grafo no dirigido es un conjunto de ciclos simples que forma una base del espacio de ciclos del grafo. Es decir, es un conjunto mínimo de ciclos que permite expresar cada subgrafo de grado par como una diferencia simétrica de ciclos de base.

Se puede formar una base de ciclo fundamental a partir de cualquier árbol de expansión o bosque de expansión del grafo dado, seleccionando los ciclos formados por la combinación de un camino en el árbol y una única arista fuera del árbol. Alternativamente, si las aristas del grafo tienen pesos positivos, la base de ciclo de peso mínimo se puede construir en tiempo polinomial .

En los grafos planares , el conjunto de ciclos acotados de una incrustación del grafo forma una base de ciclo. La base de ciclo de peso mínimo de un grafo planar corresponde al árbol de Gomory-Hu del grafo dual .

Definiciones

Un subgrafo generador de un grafo dado G tiene el mismo conjunto de vértices que G mismo pero, posiblemente, menos aristas. Se dice que un grafo G , o uno de sus subgrafos, es euleriano si cada uno de sus vértices tiene grado par (su número de aristas incidentes). Cada ciclo simple en un grafo es un subgrafo euleriano, pero puede haber otros. El espacio de ciclos de un grafo es la colección de sus subgrafos eulerianos. Forma un espacio vectorial sobre el cuerpo finito de dos elementos . La operación de adición vectorial es la diferencia simétrica de dos o más subgrafos, que forma otro subgrafo que consiste en las aristas que aparecen un número impar de veces en los argumentos de la operación de diferencia simétrica. ^[1]

Una base de ciclo es una base de este espacio vectorial en la que cada vector base representa un ciclo simple. Consiste en un conjunto de ciclos que se pueden combinar, utilizando diferencias simétricas, para formar cada subgrafo euleriano, y que es minimal con esta propiedad. Cada base de ciclo de un grafo dado tiene el mismo número de ciclos, que es igual a la dimensión de su espacio de ciclos. Este número se llama rango de circuito del grafo, y es igual a donde es el número de aristas del grafo, es el número de vértices y es el número de componentes conectados . ^[2] ${\displaystyle m-n+c}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle c}$

Bases especiales para ciclos

Se han estudiado varios tipos especiales de bases de ciclo, incluidas las bases de ciclo fundamental, las bases de ciclo débilmente fundamental, las bases de ciclo disperso (o 2-) y las bases de ciclo integral. ^[3]

Ciclos inducidos

Todo grafo tiene una base de ciclo en la que cada ciclo es un ciclo inducido . En un grafo conexo de 3 vértices , siempre existe una base formada por ciclos periféricos , ciclos cuya eliminación no separa el grafo restante. ^{[4] [5]} En cualquier grafo que no sea uno formado añadiendo una arista a un ciclo, un ciclo periférico debe ser un ciclo inducido.

Ciclos fundamentales

Si es un árbol de expansión o un bosque de expansión de un grafo dado , y es una arista que no pertenece a , entonces el ciclo fundamental definido por es el ciclo simple que consiste en junto con el camino en la conexión de los puntos finales de . Hay exactamente ciclos fundamentales, uno para cada arista que no pertenece a . Cada uno de ellos es linealmente independiente de los ciclos restantes, porque incluye una arista que no está presente en ningún otro ciclo fundamental. Por lo tanto, los ciclos fundamentales forman una base para el espacio de ciclos. ^{[1] [2]} Una base de ciclo construida de esta manera se llama base de ciclo fundamental o base de ciclo fuertemente fundamental . ^[3] ${\displaystyle T}$ ${\displaystyle G}$ ${\displaystyle e}$ ${\displaystyle T}$ ${\displaystyle C_{e}}$ ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle T}$ ${\displaystyle e}$ ${\displaystyle m-n+c}$ ${\displaystyle T}$ ${\displaystyle e}$

También es posible caracterizar bases de ciclos fundamentales sin especificar el árbol para el que son fundamentales. Existe un árbol para el que una base de ciclo dada es fundamental si y solo si cada ciclo contiene una arista que no está incluida en ningún otro ciclo de base, es decir, cada ciclo es independiente de los demás. De ello se deduce que una colección de ciclos es una base de ciclo fundamental de si y solo si tiene la propiedad de independencia y tiene el número correcto de ciclos para ser una base de . ^[6] ${\displaystyle G}$ ${\displaystyle G}$

Ciclos débilmente fundamentales

Una base de ciclo se llama débilmente fundamental si sus ciclos pueden colocarse en un ordenamiento lineal tal que cada ciclo incluye al menos una arista que no está incluida en ningún ciclo anterior. Una base de ciclo fundamental es automáticamente débilmente fundamental (para cualquier ordenamiento de aristas). ^{[3] [7]} Si cada base de ciclo de un grafo es débilmente fundamental, lo mismo es cierto para cada menor del grafo. Con base en esta propiedad, la clase de grafos (y multigrafos ) para los cuales cada base de ciclo es débilmente fundamental puede caracterizarse por cinco menores prohibidos : el grafo de la pirámide cuadrada , el multigrafo formado al duplicar todas las aristas de un ciclo de cuatro vértices, dos multigrafos formados al duplicar dos aristas de un tetraedro y el multigrafo formado al triplicar las aristas de un triángulo. ^[8]

Ciclos faciales

Si un grafo planar finito conexo está incrustado en el plano, cada cara de la incrustación está limitada por un ciclo de aristas. Una cara es necesariamente ilimitada (incluye puntos arbitrariamente alejados de los vértices del grafo) y las caras restantes están limitadas. Por la fórmula de Euler para grafos planares , hay caras exactamente limitadas. La diferencia simétrica de cualquier conjunto de ciclos de caras es el límite del conjunto de caras correspondiente, y diferentes conjuntos de caras limitadas tienen diferentes límites, por lo que no es posible representar el mismo conjunto como una diferencia simétrica de ciclos de caras de más de una manera; esto significa que el conjunto de ciclos de caras es linealmente independiente. Como conjunto linealmente independiente de suficientes ciclos, necesariamente forma una base de ciclo. ^[9] Siempre es una base de ciclo débilmente fundamental, y es fundamental si y solo si la incrustación del grafo es exteriormente plana . ${\displaystyle m-n+1}$

Para los grafos correctamente incrustados en otras superficies de modo que todas las caras de la incrustación sean discos topológicos, no es cierto en general que exista una base de ciclo que utilice solo ciclos de caras. Los ciclos de caras de estas incrustaciones generan un subconjunto propio de todos los subgrafos eulerianos. El grupo de homología de la superficie dada caracteriza a los subgrafos eulerianos que no pueden representarse como el límite de un conjunto de caras. El criterio de planaridad de Mac Lane utiliza esta idea para caracterizar los grafos planares en términos de las bases de ciclo: un grafo finito no dirigido es planar si y solo si tiene una base de ciclo dispersa o 2-base , ^[3] una base en la que cada arista del grafo participa en como máximo dos ciclos de base. En un grafo planar, la base de ciclo formada por el conjunto de caras acotadas es necesariamente dispersa y, a la inversa, una base de ciclo dispersa de cualquier grafo forma necesariamente el conjunto de caras acotadas de una incrustación plana de su grafo. ^{[9] [10]} ${\displaystyle H_{2}(S,\mathbb {Z} _{2})}$ ${\displaystyle S}$

Bases integrales

El espacio de ciclos de un grafo puede interpretarse utilizando la teoría de homología como el grupo de homología de un complejo simplicial con un punto para cada vértice del grafo y un segmento de línea para cada arista del grafo. Esta construcción puede generalizarse al grupo de homología sobre un anillo arbitrario . Un caso especial importante es el anillo de números enteros , para el cual el grupo de homología es un grupo abeliano libre , un subgrupo del grupo abeliano libre generado por las aristas del grafo. De manera menos abstracta, este grupo puede construirse asignando una orientación arbitraria a las aristas del grafo dado; entonces los elementos de son etiquetados de las aristas del grafo por números enteros con la propiedad de que, en cada vértice, la suma de las etiquetas de las aristas entrantes es igual a la suma de las etiquetas de las aristas salientes. La operación de grupo es la suma de estos vectores de etiquetas. Una base de ciclo integral es un conjunto de ciclos simples que genera este grupo. ^[3] ${\displaystyle H_{1}(G,\mathbb {Z} _{2})}$ ${\displaystyle H_{1}(G,R)}$ ${\displaystyle R}$ ${\displaystyle H_{1}(G,\mathbb {Z} )}$ ${\displaystyle H_{1}(G,\mathbb {Z} )}$

Peso mínimo

Si a las aristas de un grafo se les asignan pesos de números reales, el peso de un subgrafo puede calcularse como la suma de los pesos de sus aristas. La base de peso mínima del espacio de ciclos es necesariamente una base de ciclos: por el teorema de Veblen , ^[11] cada subgrafo euleriano que no sea en sí mismo un ciclo simple puede descomponerse en múltiples ciclos simples, que necesariamente tienen un peso menor.

Según las propiedades estándar de las bases en espacios vectoriales y matroides, la base de ciclo de peso mínimo no solo minimiza la suma de los pesos de sus ciclos, sino que también minimiza cualquier otra combinación monótona de los pesos de los ciclos. Por ejemplo, es la base de ciclo la que minimiza el peso de su ciclo más largo. ^[12]

Algoritmos de tiempo polinomial

En cualquier espacio vectorial, y más generalmente en cualquier matroide , se puede encontrar una base de peso mínimo mediante un algoritmo voraz que considere los elementos de base potenciales uno a la vez, en orden ordenado por sus pesos, y que incluya un elemento en la base cuando sea linealmente independiente de los elementos de base elegidos previamente. La prueba de independencia lineal se puede realizar mediante eliminación gaussiana . Sin embargo, un grafo no dirigido puede tener un conjunto exponencialmente grande de ciclos simples, por lo que sería computacionalmente inviable generar y probar todos esos ciclos.

Horton (1987) proporcionó el primer algoritmo de tiempo polinomial para encontrar una base de peso mínimo, en grafos para los cuales cada peso de arista es positivo. Su algoritmo utiliza este enfoque de generación y prueba, pero restringe los ciclos generados a un pequeño conjunto de ciclos, llamados ciclos de Horton . Un ciclo de Horton es un ciclo fundamental de un árbol de ruta más corta del grafo dado. Hay como máximo n árboles de ruta más corta diferentes (uno para cada vértice inicial) y cada uno tiene menos de m ciclos fundamentales, lo que da el límite en el número total de ciclos de Horton. Como mostró Horton, cada ciclo en la base de ciclo de peso mínimo es un ciclo de Horton. ^[13] El uso del algoritmo de Dijkstra para encontrar cada árbol de ruta más corta y luego usar la eliminación gaussiana para realizar los pasos de prueba del algoritmo de base voraz conduce a un algoritmo de tiempo polinomial para la base de ciclo de peso mínimo. Investigadores posteriores han desarrollado algoritmos mejorados para este problema, ^{[14] [15] [16] [17]} reduciendo la complejidad temporal del peor caso para encontrar una base de ciclo de peso mínimo en un gráfico con aristas y vértices a . ^[18] ${\displaystyle O(mn)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle O(m^{2}n/\log n)}$

Dureza NP

Encontrar la base fundamental con el mínimo peso posible está estrechamente relacionado con el problema de encontrar un árbol de expansión que minimice el promedio de las distancias por pares; ambos son NP-hard . ^[19] Encontrar una base fundamental débilmente ponderada también es NP-hard, ^[7] y aproximarla es MAXSNP-hard . ^[20] Si se permiten pesos negativos y ciclos ponderados negativamente, entonces encontrar una base de ciclo mínimo (sin restricción) también es NP-hard, ya que se puede utilizar para encontrar un ciclo hamiltoniano : si un grafo es hamiltoniano, y a todas las aristas se les da un peso −1, entonces una base de ciclo de peso mínimo necesariamente incluye al menos un ciclo hamiltoniano.

En grafos planares

La base de ciclo de peso mínimo para un grafo planar no es necesariamente la misma que la base formada por sus caras acotadas: puede incluir ciclos que no sean caras, y algunas caras pueden no estar incluidas como ciclos en la base de ciclo de peso mínimo. Sin embargo, existe una base de ciclo de peso mínimo en la que no hay dos ciclos que se crucen entre sí: por cada dos ciclos en la base, o bien los ciclos encierran subconjuntos disjuntos de las caras acotadas, o bien uno de los dos ciclos encierra al otro. Este conjunto de ciclos corresponde, en el grafo dual del grafo planar dado, a un conjunto de cortes que forman un árbol de Gomory–Hu del grafo dual, la base de peso mínimo de su espacio de cortes . ^[21] Con base en esta dualidad, se puede construir una representación implícita de la base de ciclo de peso mínimo en un grafo planar en el tiempo . ^[22] ${\displaystyle O(n\log ^{3}n)}$

Aplicaciones

Las bases de ciclos se han utilizado para resolver problemas periódicos de programación, como el problema de determinar el horario de un sistema de transporte público. En esta aplicación, los ciclos de una base de ciclos corresponden a variables en un programa entero para resolver el problema. ^[23]

En la teoría de la rigidez estructural y la cinemática , las bases de ciclo se utilizan para guiar el proceso de configuración de un sistema de ecuaciones no redundantes que se pueden resolver para predecir la rigidez o el movimiento de una estructura. En esta aplicación, las bases de ciclo de peso mínimo o casi mínimo conducen a sistemas de ecuaciones más simples. ^[24]

En la computación distribuida , se han utilizado bases de ciclo para analizar el número de pasos necesarios para que un algoritmo se estabilice. ^[25]

En bioinformática , las bases cíclicas se han utilizado para determinar información de haplotipos a partir de datos de secuencias del genoma. ^[26] Las bases cíclicas también se han utilizado para analizar la estructura terciaria del ARN . ^[27]

La base del ciclo de peso mínimo de un gráfico del vecino más cercano de puntos muestreados de una superficie tridimensional se puede utilizar para obtener una reconstrucción de la superficie. ^[28]

En quimioinformática , la base del ciclo mínimo de un gráfico molecular se denomina el conjunto más pequeño de anillos más pequeños . ^{[29] [30] [31]}

Referencias

1. Diestel, Reinhard (2012), "1.9 Algo de álgebra lineal", Graph Theory , Textos de posgrado en matemáticas, vol. 173, Springer, págs. 23-28.
2. Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Gráficos y espacios vectoriales", Teoría de grafos y sus aplicaciones (2.ª ed.), CRC Press, págs. 197-207, ISBN 9781584885054.
3. Liebchen, Christian; Rizzi, Romeo (2007), "Clases de bases de ciclos", Matemáticas Aplicadas Discretas , 155 (3): 337–355, doi : 10.1016/j.dam.2006.06.007 , MR  2303157.
4. Diestel (2012), págs. 32, 65.
5. Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la London Mathematical Society , Tercera serie, 13 : 743–767, doi :10.1112/plms/s3-13.1.743, MR  0158387. Véase en particular el Teorema 2.5.
6. Cribb, DW; Ringeisen, RD; Shier, DR (1981), "Sobre las bases cíclicas de un grafo", Actas de la Duodécima Conferencia del Sudeste sobre Combinatoria, Teoría de Grafos y Computación, vol. I (Baton Rouge, La., 1981) , Congressus Numerantium, vol. 32, págs. 221–229, MR  0681883.
7. Rizzi, Romeo (2009), "Las bases mínimas de ciclos fundamentales débiles son difíciles de encontrar", Algorithmica , 53 (3): 402–424, doi :10.1007/s00453-007-9112-8, MR  2482112, S2CID  12675654.
8. Hartvigsen, David; Zemel, Eitan (1989), "¿Es fundamental la base de cada ciclo?", Journal of Graph Theory , 13 (1): 117–137, doi :10.1002/jgt.3190130115, MR  0982873.
9. Diestel (2012), págs.
10. Mac Lane, S. (1937), "Una condición combinatoria para gráficos planos" (PDF) , Fundamenta Mathematicae , 28 : 22–32, doi : 10.4064/fm-28-1-22-32.
11. Veblen, Oswald (1912), "Una aplicación de ecuaciones modulares en el análisis in situ", Anales de Matemáticas , Segunda serie, 14 (1): 86–94, doi :10.2307/1967604, JSTOR  1967604.
12. Chickering, David M.; Geiger, Dan; Heckerman, David (1995), "Sobre la búsqueda de una base de ciclo con un ciclo máximo más corto", Information Processing Letters , 54 (1): 55–58, CiteSeerX 10.1.1.650.8218 , doi :10.1016/0020-0190(94)00231-M, MR  1332422 .
13. Horton, JD (1987), "Un algoritmo de tiempo polinomial para encontrar la base del ciclo más corto de un gráfico", SIAM Journal on Computing , 16 (2): 358–366, doi :10.1137/0216026.
14. Berger, Franziska; Gritzmann, Peter; de Vries, Sven (2004), "Bases de ciclo mínimo para gráficos de red", Algorithmica , 40 (1): 51–62, doi :10.1007/s00453-004-1098-x, MR  2071255, S2CID  9386078.
15. Mehlhorn, Kurt ; Michail, Dimitrios (2006), "Implementación de algoritmos de base de ciclo mínimo", ACM Journal of Experimental Algorithmics , 11 : 2.5, CiteSeerX 10.1.1.60.1087 , doi :10.1145/1187436.1216582, S2CID  6198296 .
16. Kavitha, Telikepalli ; Mehlhorn, Kurt ; Michail, Dimitrios; Paluch, Katarzyna E. (2008), "Un algoritmo para la base de gráficos de ciclo mínimo", Algorithmica , 52 (3): 333–349, doi : 10.1007/s00453-007-9064-z , SEÑOR  2452919 ${\displaystyle {\tilde {O}}(m^{2}n)}$.
17. Kavitha, Telikepalli; Liebchen, Christian; Mehlhorn, Kurt ; Michail, Dimitrios; Rizzi, Romeo; Ueckerdt, Torsten; Zweig, Katharina A. (2009), "Bases de ciclos en grafos: caracterización, algoritmos, complejidad y aplicaciones", Computer Science Review , 3 (4): 199–243, doi :10.1016/j.cosrev.2009.08.001.
18. Amaldi, Edoardo; Iuliano, Claudio; Rizzi, Romeo (2010), "Algoritmos determinísticos eficientes para encontrar una base de ciclo mínimo en grafos no dirigidos", Integer Programming and Combinatorial Optimization: 14th International Conference, IPCO 2010, Lausanne, Suiza, 9-11 de junio de 2010, Actas , Lecture Notes in Computer Science, vol. 6080, Springer, pp. 397–410, Bibcode :2010LNCS.6080..397A, doi :10.1007/978-3-642-13036-6_30, ISBN 978-3-642-13035-9, Sr.  2661113.
19. Deo, Narsingh; Prabhu, GM; Krishnamoorthy, MS (1982), "Algoritmos para generar ciclos fundamentales en un gráfico", ACM Transactions on Mathematical Software , 8 (1): 26–42, doi : 10.1145/355984.355988 , MR  0661120, S2CID  2260051.
20. Galbiati, Giulia; Amaldi, Edoardo (2004), "Sobre la aproximabilidad del problema de la base del ciclo fundamental mínimo", Approximation and Online Algorithms: First International Workshop, WAOA 2003, Budapest, Hungría, 16-18 de septiembre de 2003, Documentos revisados , Lecture Notes in Computer Science, vol. 2909, Berlín: Springer, págs. 151-164, doi :10.1007/978-3-540-24592-6_12, ISBN 978-3-540-21079-5, Sr.  2089904.
21. Hartvigsen, David; Mardon, Russell (1994), "El problema del corte mínimo de todos los pares y el problema de la base del ciclo mínimo en grafos planares", SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi :10.1137/S0895480190177042, MR  1285579.
22. Borradaile, Glencora; Eppstein, David ; Nayyeri, Amir; Wulff-Nilsen, Christian (2016), "Cortes mínimos de todos los pares en tiempo casi lineal para gráficos incrustados en la superficie", Proc. 32nd Int. Symp. Computational Geometry , Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, Schloss Dagstuhl, págs. 22:1–22:16, arXiv : 1411.7055 , doi : 10.4230/LIPIcs.SoCG.2016.22 , S2CID  215762172.
23. Liebchen, Christian (2007), "Optimización periódica de horarios en el transporte público", Actas de investigación de operaciones 2006 , vol. 2006, págs. 29-36, doi :10.1007/978-3-540-69995-8_5, ISBN 978-3-540-69994-1.
24. Cassell, AC; De Henderson, JC; Kaveh, A. (1974), "Bases cíclicas para el análisis de flexibilidad de estructuras", International Journal for Numerical Methods in Engineering , 8 (3): 521–528, Bibcode :1974IJNME...8..521C, doi :10.1002/nme.1620080308.
25. Boulinier, Christian; Petit, Franck; Villain, Vincent (2004), "Cuando la teoría de grafos ayuda a la autoestabilización", Actas del vigésimo tercer simposio anual de la ACM sobre principios de computación distribuida (PODC '04) , Nueva York, NY, EE. UU.: ACM, págs. 150-159, CiteSeerX 10.1.1.79.2190 , doi :10.1145/1011767.1011790, ISBN  978-1581138023, Número de identificación del sujeto  14936510.
26. Aguiar, Derek; Istrail, Sorin (2012), "HapCompass: un algoritmo de base de ciclo rápido para el ensamblaje preciso de haplotipos de datos de secuencia", Journal of Computational Biology , 19 (6): 577–590, doi :10.1089/cmb.2012.0084, PMC 3375639 , PMID  22697235 .
27. Lemieux, Sébastien; Major, François (2006), "Extracción y clasificación automatizadas de motivos cíclicos de la estructura terciaria del ARN", Nucleic Acids Research , 34 (8): 2340–2346, doi :10.1093/nar/gkl120, PMC 1458283 , PMID  16679452 .
28. Gotsman, Craig; Kaligosi, Kanela; Mehlhorn, Kurt ; Michail, Dimitrios; Pyrga, Evangelia (2007), "Bases cíclicas de gráficos y variedades muestreadas", Diseño geométrico asistido por computadora , 24 (8–9): 464–480, CiteSeerX 10.1.1.298.9661 , doi :10.1016/j.cagd.2006.07. 001, señor  2359763 .
29. May, John W.; Steinbeck, Christoph (2014), "Percepción eficiente de anillos para el kit de desarrollo químico", Journal of Cheminformatics , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID  24479757 
30. Downs, GM; Gillet, VJ; Holliday, JD; Lynch, MF (1989), "Una revisión de los algoritmos de percepción de anillos para gráficos químicos", J. Chem. Inf. Comput. Sci. , 29 (3): 172–187, doi :10.1021/ci00063a007
31. Zamora, A. (1979), "Un algoritmo para encontrar el conjunto más pequeño de anillos más pequeños", J. Chem. Inf. Comput. Sci. , 16 (1): 40–43, doi :10.1021/ci60005a013