En la teoría de grafos , una rama de las matemáticas, la base de un ciclo de un grafo no dirigido es un conjunto de ciclos simples que forma la base del espacio cíclico del grafo. Es decir, es un conjunto mínimo de ciclos que permite que cada subgrafo de grado par se exprese como una diferencia simétrica de ciclos básicos.
Se puede formar una base de ciclo fundamental a partir de cualquier árbol de expansión 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 puede construirse 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 de Gomory-Hu del gráfico dual .
Definiciones
Un subgrafo que se extiende 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 un grado par (su número de aristas incidentes). Cada ciclo simple en un gráfico es un subgráfico euleriano, pero puede haber otros. El espacio cíclico de un gráfico es la colección de sus subgráficos eulerianos. Forma un espacio vectorial sobre el campo finito de dos elementos . La operación de suma vectorial es la diferencia simétrica de dos o más subgrafos, que forma otro subgrafo que consta de los bordes 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 eso es mínimo con esta propiedad. Cada base de ciclo de un gráfico dado tiene el mismo número de ciclos, lo que equivale a la dimensión de su espacio de ciclo. Este número se llama rango de circuito de la gráfica y es igual a dónde es 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]
Bases de ciclos especiales
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
Cada gráfico tiene una base de ciclo en la que cada ciclo es un ciclo inducido . En un gráfico conectado a 3 vértices , siempre existe una base que consta de ciclos periféricos , ciclos cuya eliminación no separa el gráfico restante. [4] [5] En cualquier gráfico que no sea el que se forma 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 determinado, y es un borde que no pertenece a , luego el ciclo fundamental definido por es el ciclo simple que consiste en junto con el camino en conectando los puntos finales de . Hay exactamente ciclos fundamentales, uno por cada borde que no pertenece a . Cada uno de ellos es linealmente independiente de los ciclos restantes, porque incluye un bordeque no está presente en ningún otro ciclo fundamental. Por lo tanto, los ciclos fundamentales forman una base para el espacio del ciclo. [1] [2] Una base de ciclo construida de esta manera se denomina base de ciclo fundamental o base de ciclo fuertemente fundamental . [3]
También es posible caracterizar las bases del ciclo fundamental sin especificar el árbol para el que son fundamentales. Existe un árbol para el cual 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 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]
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 fundamentalmente débil (para cualquier orden de borde). [3] [7] Si cada base de ciclo de una gráfica es débilmente fundamental, lo mismo es cierto para cada menor de la gráfica. Con base en esta propiedad, la clase de gráficos (y multigraphs ) para los cuales cada base de ciclo es débilmente fundamental se puede caracterizar por cinco menores prohibidos : el gráfico de la pirámide cuadrada , el multigraph formado al duplicar todos los bordes de un ciclo de cuatro vértices, dos multigrafos formados al doblar 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á delimitada 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 limitadas. Según la fórmula de Euler para gráficas planas , hay exactamenterostros acotados. 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 delimitadas 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 uno. camino; 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 un plano externo .
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 faciales 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 solo si tiene una base de ciclo disperso o 2-base , [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 de ciclo formada por el conjunto de caras delimitadas es necesariamente escasa y, a la inversa, una base de ciclo escaso de cualquier gráfico forma necesariamente el conjunto de caras delimitadas de una incrustación plana de su gráfico. [9] [10]
Bases integrales
El espacio de ciclo de un gráfico se puede interpretar utilizando la teoría de la homología como 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íaes 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 deson etiquetas 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 del borde saliente. La operación de grupo es la adición de estos vectores de etiquetas. Una base de ciclo integral es un conjunto de ciclos simples que genera este grupo. [3]
Peso mínimo
Si a los bordes de un gráfico se les asignan pesos numéricos reales, el peso de un subgráfico se puede calcular como la suma de los pesos de sus bordes. La base de peso mínimo del espacio cíclico es necesariamente una base cíclica: según el teorema de Veblen , [11] todo subgrafo euleriano que no sea en sí mismo un ciclo simple puede descomponerse en múltiples ciclos simples, que necesariamente tienen un peso menor.
Por propiedades estándar de 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 ciclo. Por ejemplo, es la base del 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 codicioso que considera los elementos de base potenciales uno a la vez, en orden según sus pesos, y que incluye un elemento en la base cuando es linealmente independiente de los elementos básicos elegidos previamente. Las pruebas de independencia lineal se pueden 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 borde es positivo. Su algoritmo utiliza este enfoque de generar y probar, pero restringe los ciclos generados a un pequeño conjunto deciclos, llamados ciclos de Horton . Un ciclo de Horton es un ciclo fundamental de un árbol de ruta más corto del gráfico dado. Hay como máximo n árboles de camino más corto 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 mostró Horton, cada ciclo en la base del ciclo de peso mínimo es un ciclo de Horton. [13] Usar el algoritmo de Dijkstra para encontrar cada árbol de ruta más corto y luego usar la eliminación gaussiana para realizar los pasos de prueba del algoritmo de base codiciosa conduce a un algoritmo de tiempo polinomial 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 de tiempo en el peor de los casos para encontrar una base de ciclo de peso mínimo en un gráfico con bordes y vértices a . [18]
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ébil de peso mínimo también es NP-hard, [7] y aproximarlo 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-difícil, ya que se puede usar para encontrar un ciclo hamiltoniano : si una gráfica es hamiltoniana, 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 hay dos ciclos que se crucen entre sí: por cada dos ciclos en la base, o los ciclos encierran subconjuntos disjuntos de las caras delimitadas, 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]
Aplicaciones
Las bases de ciclo 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 de ciclo 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 establecer 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 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 ciclo 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 la información del haplotipo a partir de los datos de la secuencia del genoma. [26] Las bases de 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 quimioformá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 (SSSR). [29] [30] [31]
Referencias
- ^ a b Diestel, Reinhard (2012), "1.9 Algún álgebra lineal" , Teoría de grafos , Textos de posgrado en matemáticas, 173 , Springer, págs. 23-28.
- ^ a b Gross, Jonathan L .; Yellen, Jay (2005), "4.6 Gráficos y espacios vectoriales" , Teoría de gráficos y sus aplicaciones (2ª ed.), CRC Press, págs. 197–207, ISBN 9781584885054.
- ^ a b c d e Liebchen, Christian; Rizzi, Romeo (2007), "Clases de bases de ciclo", Matemáticas aplicadas discretas , 155 (3): 337–355, doi : 10.1016 / j.dam.2006.06.007 , MR 2303157.
- ^ Diestel (2012) , págs. 32, 65.
- ^ Tutte, WT (1963), "Cómo dibujar un gráfico", Proceedings of the London Mathematical Society , Third Series, 13 : 743–767, doi : 10.1112 / plms / s3-13.1.743 , MR 0158387. Ver en particular el Teorema 2.5.
- ^ 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 Gráficos y Computación, vol. I (Baton Rouge, Luisiana, 1981) , Congressus Numerantium, 32 , págs. 221-229, MR 0681883.
- ^ a b Rizzi, Romeo (2009), "Las bases de ciclos mínimos débiles fundamentales son difíciles de encontrar", Algorithmica , 53 (3): 402–424, doi : 10.1007 / s00453-007-9112-8 , MR 2482112 , S2CID 12675654.
- ^ 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.
- ↑ a b Diestel (2012) , págs. 105-106.
- ^ Mac Lane, S. (1937), "Una condición combinatoria para gráficas planas" (PDF) , Fundamenta Mathematicae , 28 : 22–32, doi : 10.4064 / fm-28-1-22-32.
- ^ Veblen, Oswald (1912), "Una aplicación de ecuaciones modulares en el análisis situs", Annals of Mathematics , Second Series, 14 (1): 86–94, doi : 10.2307 / 1967604 , JSTOR 1967604.
- ^ 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.
- ^ Horton, JD (1987), "Un algoritmo de tiempo polinomial para encontrar la base de ciclo más corto de un gráfico", SIAM Journal on Computing , 16 (2): 358–366, doi : 10.1137 / 0216026.
- ^ 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.
- ^ Mehlhorn, Kurt ; Michail, Dimitrios (2006), "Implementación de algoritmos de base de ciclo mínimo" , ACM Journal of Experimental Algorithmics , 11 : 2.5, doi : 10.1145 / 1187436.1216582 , S2CID 6198296.
- ^ Kavitha, Telikepalli; Mehlhorn, Kurt ; Michail, Dimitrios; Paluch, Katarzyna E. (2008), "Analgoritmo para base de ciclo mínimo de gráficos ", Algorithmica , 52 (3): 333–349, doi : 10.1007 / s00453-007-9064-z , MR 2452919.
- ^ Kavitha, Telikepalli; Liebchen, Christian; Mehlhorn, Kurt ; Michail, Dimitrios; Rizzi, Romeo; Ueckerdt, Torsten; Zweig, Katharina A. (2009), "Bases de ciclo en gráficos: caracterización, algoritmos, complejidad y aplicaciones" , Computer Science Review , 3 (4): 199–243, doi : 10.1016 / j.cosrev.2009.08.001.
- ^ Amaldi, Edoardo; Iuliano, Claudio; Rizzi, Romeo (2010), "Algoritmos deterministas eficientes para encontrar una base de ciclo mínimo en gráficos no dirigidos", Programación de enteros y optimización combinatoria: 14ª Conferencia Internacional, IPCO 2010, Lausana, Suiza, 9-11 de junio de 2010, Actas , Notas de conferencias en Computer Science, 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, MR 2661113.
- ^ 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.
- ^ Galbiati, Giulia; Amaldi, Edoardo (2004), "Sobre la aproximabilidad del problema básico 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 computadora Science, 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.
- ^ 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áficas planas", SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi : 10.1137 / S0895480190177042 , MR 1285579.
- ^ 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 superficie", Proc. 32a Int. Symp. Geometría computacional , Leibniz International Proceedings in Informatics (LIPIcs), 51 , Schloss Dagstuhl, págs. 22: 1–22: 16, arXiv : 1411.7055 , doi : 10.4230 / LIPIcs.SoCG.2016.22.
- ^ Liebchen, Christian (2007), "Optimización periódica del horario en el transporte público", Procedimientos de investigación operativa , 2006 : 29–36, doi : 10.1007 / 978-3-540-69995-8_5 , ISBN 978-3-540-69994-1.
- ^ Cassell, AC; De Henderson, JC; Kaveh, A. (1974), "Bases de ciclo para el análisis de flexibilidad de estructuras", Revista internacional de métodos numéricos en ingeniería , 8 (3): 521–528, Código bibliográfico : 1974IJNME ... 8..521C , doi : 10.1002 /nme.1620080308.
- ^ 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 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, S2CID 14936510.
- ^ Aguiar, Derek; Istrail, Sorin (2012), "HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data", Journal of Computational Biology , 19 (6): 577–590, doi : 10.1089 / cmb.2012.0084 , PMC 3375639 , PMID 22697235.
- ^ 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.
- ^ Gotsman, Craig; Kaligosi, Kanela; Mehlhorn, Kurt ; Michail, Dimitrios; Pyrga, Evangelia (2007), "Bases de ciclo 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 , MR 2359763.
- ^ Mayo, John W .; Steinbeck, Christoph (2014). "Percepción de anillo eficiente para el kit de desarrollo químico" . Revista de Cheminformatics . 6 (3): 3. doi : 10.1186 / 1758-2946-6-3 . PMC 3922685 . PMID 24479757 .
- ^ Downs, GM; Gillet, VJ; Holliday, JD; Lynch, MF (1989). "Una revisión de los algoritmos de percepción del anillo para gráficos químicos". J. Chem. Inf. Computación. Sci. 29 (3): 172–187. doi : 10.1021 / ci00063a007 .
- ^ Zamora, A. (1979). "Un algoritmo para encontrar el conjunto más pequeño de anillos más pequeños". J. Chem. Inf. Computación. Sci. 16 (1): 40–43. doi : 10.1021 / ci60005a013 .