Registro:
| Documento: | Tesis de Grado |
| Título: | Finding a compatible euler cycle : a fast algorithm |
| Título alternativo: | Un algoritmo rápido para encontrar un camino euleriano compatible en un grafo dirigido |
| Autor: | Candioti, Alejandro Marcelo |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2019 |
| Fecha en portada: | 1 de Diciembre 2019 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Becher, Verónica Andrea |
| Jurado: | Bonomo, Flavia; Lin, Min Chih |
| Idioma: | Inglés |
| Palabras clave: | CICLOS EULERIANOS; SECUENCIAS DE BRUIJN; COLLARES PERFECTOSEULER CYCLE; DE BRUIJN SEQUENCES; PERFECT NECKLACES |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000616_Candioti |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000616_Candioti.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000616_Candioti |
| Ubicación: | Dep.COM 000616 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Candioti, Alejandro Marcelo. (2019). Finding a compatible euler cycle : a fast algorithm. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000616_Candioti |
Resumen:
Un ciclo Euleriano en un grafo G es un camino cerrado que usa todos los arcos de G exactamente una vez. Dos ciclos Eulerianos son compatibles si no comparten ningún camino de longitud 2. Fleischner y Jackson demuestran en 1990 que para todo camino Euleriano en un grafo dirigido de grado mínimo 3, existe otro ciclo Euleriano compatible. El resultado principal de esta tesis es un algoritmo para calcular un ciclo Euleriano compatible a uno dado en un grafo dirigido de grado m´ınimo 3, con complejidad de peor caso O(|E| ∗ log(|V |)) donde |V | y |E| la cantidad de vértices y arcos del grafo. Nuestro algoritmo se basa en las ideas de Lin, Ward, Jain y Skiena de 2011. Un segundo resultado de esta tesis responde una pregunta de Becher y Heiber en 2011 y es un algoritmo para extender una secuencia de Bruijn de orden n a otra de orden n + 1 para alfabetos de 3 o más símbolos. Nuestra solución de este problema se basa en el algoritmo previamente descripto que genera un ciclo Euleriano compatible a otro dado. Esta solución también puede usarse para extender otras secuencias que son variantes de las secuencias de Bruijn, como los llamados collares perfectos.
Abstract:
An Euler cycle of a graph G is a closed path that contains all the edges in G. Two Euler cycles are compatible if they do not share a path of length 2. Fleischner and Jackson proved in 1990 that for every Euler cycle in a directed graph of minimum degree 3 there exists another Euler cycle compatible with it. The main result of this Thesis is an algorithm to calculate an Euler cycle compatible to a given one in a directed graph of minimum degree 3 with worst case time complexity of O(|E| ∗ log(|V |)), where |V | and |E| are the amount of vertices and edges of the graph. Our algorithm is based on the ideas of Lin, Ward, Jain y Skiena in 2011. A second result of this work answers a question proposed by Becher and Heiber in 2011 and is an algorithm to extend a de Bruijn sequence of order n to another de Bruijn sequence of order n + 1 in alphabets with 3 or more symbols. Our solution for this problem is based on the described algorithm that generates an Euler cycle compatible to a given one. This solution can also be used to extend other sequences that are variants of de Bruijn sequences, like the perfect necklaces.
Citación:
---------- APA ----------
Candioti, Alejandro Marcelo. (2019). Finding a compatible euler cycle : a fast algorithm. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000616_Candioti
---------- CHICAGO ----------
Candioti, Alejandro Marcelo. "Finding a compatible euler cycle : a fast algorithm". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2019.https://hdl.handle.net/20.500.12110/seminario_nCOM000616_Candioti
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000616_Candioti.pdf
Distrubución geográfica
