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 cíclica de un gráfico no dirigido es un conjunto de ciclos simples que forma la base del espacio de ciclos del gráfico. Es decir, es un conjunto mínimo de ciclos que permite expresar cada subgrafo de grado par como una diferencia simétrica de ciclos básicos.

Se puede formar una base de ciclo fundamental a partir de cualquier árbol o bosque de expansión del gráfico dado, seleccionando los ciclos formados por la combinación de una ruta en el árbol y un solo borde fuera del árbol. Alternativamente, si los bordes del gráfico tienen pesos positivos, la base del ciclo de peso mínimo se puede construir en tiempo polinómico .

En los gráficos planos , el conjunto de ciclos acotados de una incrustación del gráfico forma una base de ciclo. La base del ciclo de peso mínimo de un gráfico plano corresponde al árbol Gomory-Hu del gráfico dual .

Definiciones

Un subgrafo de expansión de un gráfico dado G tiene el mismo conjunto de vértices que el propio G pero, posiblemente, menos aristas. Un grafo G , o uno de sus subgrafos, se dice euleriano si cada uno de sus vértices tiene grado par (su número de aristas incidentes). Cada ciclo simple en un gráfico es un subgrafo euleriano, pero puede haber otros. El espacio de ciclo de un gráfico es el conjunto de sus subgrafos eulerianos. Forma un espacio vectorial sobre el campo finito de dos elementos . La operación de suma de vectores es la diferencia simétrica de dos o más subgrafos, que forma otro subgrafo que consta de 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 el que cada vector de base representa un ciclo simple. Consiste en un conjunto de ciclos que se pueden combinar, usando diferencias simétricas, para formar cada subgrafo euleriano, y que es mínimo con esta propiedad. Cada base de ciclo de un gráfico dado tiene el mismo número de ciclos, lo que es igual a la dimensión de su espacio de ciclos. Este número se llama rango de circuito del gráfico y es igual a dónde está el número de aristas en el gráfico, 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 de ciclo especiales

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

Ciclos inducidos

Cada gráfico tiene una base de ciclo en la que cada ciclo es un ciclo inducido . En un grafo conectado con 3 vértices , siempre existe una base que consta de ciclos periféricos , ciclos cuya eliminación no separa el grafo restante. ^{[4] [5]} En cualquier gráfico que no sea uno formado agregando un borde 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 gráfico dado , y es un borde al que no pertenece , entonces el ciclo fundamental definido por es el ciclo simple que consiste junto con la ruta para conectar los puntos finales de . Hay exactamente ciclos fundamentales, uno para cada arista que no pertenece . 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 tanto, los ciclos fundamentales forman una base para el espacio de ciclos. ^{[1] [2]} Una base de ciclo construida de esta manera se denomina 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 cual una base de ciclo determinada es fundamental si y sólo 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 sólo 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 denomina débilmente fundamental si sus ciclos se pueden colocar en un orden lineal de modo que cada ciclo incluya al menos un borde que no esté incluido en ningún ciclo anterior. Una base de ciclo fundamental es automáticamente débilmente fundamental (para cualquier orden de borde). ^{[3] [7]} Si cada base de ciclo de un gráfico es débilmente fundamental, lo mismo ocurre con cada menor del gráfico. Con base en esta propiedad, la clase de gráficos (y multigrafos ) para los cuales cada base de ciclo es débilmente fundamental puede caracterizarse por cinco menores prohibidos : el gráfico 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 gráfico plano finito conectado 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 gráfico) y las caras restantes están acotadas. Según la fórmula de Euler para gráficos planos , hay caras exactamente acotadas. La diferencia simétrica de cualquier conjunto de ciclos de caras es el límite del correspondiente conjunto de caras, y diferentes conjuntos de caras acotadas tienen límites diferentes, por lo que no es posible representar el mismo conjunto como una diferencia simétrica de ciclos de caras en más de un forma; esto significa que el conjunto de ciclos faciales 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 gráfico es externa . ${\displaystyle m-n+1}$

Para gráficos incrustados correctamente en otras superficies de modo que todas las caras de la incrustación sean discos topológicos, en general no es cierto que exista una base de ciclo que utilice solo ciclos de caras. Los ciclos de caras de estas incrustaciones generan un subconjunto adecuado de todos los subgrafos eulerianos. El grupo de homología de la superficie dada caracteriza 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 gráficos planos en términos de las bases del ciclo: un gráfico finito no dirigido es plano si y sólo si tiene una base de ciclo dispersa o base 2 , ^[3] una base en la que cada borde de el gráfico participa como máximo en dos ciclos básicos. En un gráfico plano, la base del ciclo formada por el conjunto de caras acotadas es necesariamente escasa y, a la inversa, una base del ciclo escasa de cualquier gráfico necesariamente forma el conjunto de caras acotadas de una incrustación plana de su gráfico. ^{[9] [10]} ${\displaystyle H_{2}(S,\mathbb {Z} _{2})}$ ${\displaystyle S}$

Bases integrales

El espacio de ciclo de un gráfico se puede interpretar utilizando la teoría de la homología como el grupo de homología de un complejo simplicial con un punto para cada vértice del gráfico y un segmento de línea para cada borde del gráfico. 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 los bordes del gráfico. De manera menos abstracta, este grupo se puede construir asignando una orientación arbitraria a los bordes del gráfico dado; entonces los elementos de son etiquetados de los bordes del gráfico mediante números enteros con la propiedad de que, en cada vértice, la suma de las etiquetas de los bordes entrantes es igual a la suma de las etiquetas de los bordes 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 los bordes de un gráfico se les dan pesos de números reales, el peso de un subgrafo se puede calcular como la suma de los pesos de sus bordes. La base de peso mínimo del espacio de ciclos es necesariamente una base de ciclos: según 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 del 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 del ciclo. Por ejemplo, es la base del ciclo la que minimiza el peso de su ciclo más largo. ^[12]

Algoritmos de tiempo polinómico

En cualquier espacio vectorial, y más generalmente en cualquier matroide , se puede encontrar una base de peso mínimo mediante un algoritmo codicioso que considera los elementos básicos potenciales uno a la vez, ordenados por sus pesos, y que incluye un elemento en la base cuando es linealmente independiente de los elementos base previamente elegidos. La prueba de independencia lineal se puede realizar mediante eliminación gaussiana . Sin embargo, un gráfico 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 gráficos para los cuales cada peso de arista es positivo. Su algoritmo utiliza este enfoque de generar y probar, 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 camino más corto del gráfico dado. Hay como máximo n árboles de caminos más cortos diferentes (uno para cada vértice inicial) y cada uno tiene menos de m ciclos fundamentales, lo que da el límite del número total de ciclos de Horton. Como demostró Horton, cada ciclo basado en el ciclo de peso mínimo es un ciclo de Horton. ^[13] Usar el 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 codiciosa conduce a un algoritmo de tiempo polinómico para la base del ciclo de peso mínimo. Investigadores posteriores han desarrollado algoritmos mejorados para este problema, ^{[14] [15] [16] [17]} reduciendo la complejidad temporal del peor de los casos 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 generador que minimice el promedio de las distancias por pares; ambos son NP-difíciles . ^[19] Encontrar una base débilmente fundamental de peso mínimo también es NP-duro, ^[7] y aproximarla es MAXSNP-duro . ^[20] Si se permiten pesos negativos y ciclos ponderados negativamente, entonces encontrar una base de ciclo mínima (sin restricción) también es NP-difícil, ya que puede usarse para encontrar un ciclo hamiltoniano : si un gráfico es hamiltoniano y todos los bordes son dado el peso −1, entonces una base de ciclo de peso mínimo incluye necesariamente al menos un ciclo hamiltoniano.

En gráficos planos

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

Aplicaciones

Las bases ciclistas se han utilizado para resolver problemas de programación periódica, como el problema de determinar el horario de un sistema de transporte público. En esta aplicación, los ciclos de una base cíclica 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 del ciclo se utilizan para guiar el proceso de establecimiento de un sistema de ecuaciones no redundantes que pueden resolverse para predecir la rigidez o el movimiento de una estructura. En esta aplicación, las bases del ciclo de peso mínimo o casi mínimo conducen a sistemas de ecuaciones más simples. ^[24]

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

En bioinformática , las bases del ciclo se han utilizado para determinar información de haplotipos a partir de datos de secuencia del genoma. ^[26] Las bases del ciclo 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 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 conoce como 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", Teoría de grafos , 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, cristiano; Rizzi, Romeo (2007), "Clases de bases del ciclo", 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 Sociedad Matemática de Londres , 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 del ciclo de un gráfico", Actas de la Duodécima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación, vol. I (Baton Rouge, Luisiana, 1981) , Congressus Numerantium, vol. 32, págs. 221–229, SEÑOR  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 análisis situs", Annals of Mathematics , 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, SEÑOR  1332422 .
13. Horton, JD (1987), "Un algoritmo de tiempo polinómico 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, cristiano; Mehlhorn, Kurt ; Michail, Dimitrios; Rizzi, Romeo; Ueckerdt, Torsten; Zweig, Katharina A. (2009), "Bases de ciclos en gráficos: caracterización, algoritmos, complejidad y aplicaciones", Computer Science Review , 3 (4): 199–243, doi :10.1016/j.cosrev.2009.08.001.
18. Amaldi, Eduardo; Juliano, Claudio; Rizzi, Romeo (2010), "Algoritmos deterministas eficientes para encontrar una base de ciclo mínima en gráficos no dirigidos", Programación entera y optimización combinatoria: 14ª Conferencia Internacional, IPCO 2010, Lausana, Suiza, 9 al 11 de junio de 2010, Actas , Notas de la conferencia en Ciencias de la Computación, vol. 6080, Springer, págs. 397–410, Bibcode :2010LNCS.6080..397A, doi :10.1007/978-3-642-13036-6_30, ISBN 978-3-642-13035-9, SEÑOR  2661113.
19. Deo, Narsingh; Prabhu, director general; 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, Julia; Amaldi, Edoardo (2004), "Sobre la aproximabilidad del problema de base del ciclo fundamental mínimo", Aproximación y algoritmos en línea: primer taller internacional, WAOA 2003, Budapest, Hungría, 16 al 18 de septiembre de 2003, artículos revisados , notas de conferencias en informática Ciencia, vol. 2909, Berlín: Springer, págs. 151–164, doi :10.1007/978-3-540-24592-6_12, ISBN 978-3-540-21079-5, señor  2089904.
21. Hartvigsen, David; Mardon, Russell (1994), "El problema de corte mínimo de todos los pares y el problema de base de ciclo mínimo en gráficos planos", 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 integrados en superficie", Proc. 32° Int. Síntoma. Geometría computacional , Actas internacionales de informática de Leibniz (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 de horarios periódicos en el transporte público", Procedimientos 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, CA; De Henderson, JC; Kaveh, A. (1974), "Bases de ciclos para el análisis de flexibilidad de estructuras", Revista internacional de métodos numéricos en ingeniería , 8 (3): 521–528, Bibcode :1974IJNME...8..521C, doi :10.1002 /nme.1620080308.
25. Boulinier, cristiano; Pequeño, Franck; Villain, Vincent (2004), "Cuando la teoría de grafos ayuda a la autoestabilización", Actas del vigésimo tercer simposio anual de ACM sobre principios de informática distribuida (PODC '04) , Nueva York, NY, EE. UU.: ACM, págs. 159, CiteSeerX 10.1.1.79.2190 , doi :10.1145/1011767.1011790, ISBN  978-1581138023, S2CID  14936510.
26. Aguiar, Derek; Istrail, Sorin (2012), "HapCompass: un algoritmo básico 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 estructura terciaria de 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. Mayo, John W.; Steinbeck, Christoph (2014), "Percepción de anillo eficiente para el kit de desarrollo de química", Journal of Cheminformatics , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID  24479757 
30. Downs, gerente general; 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. Computadora. Ciencia. , 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. Computadora. Ciencia. , 16 (1): 40–43, doi :10.1021/ci60005a013