Rivera Sánchez, Vanessa de Jesús and Martínez Hernández, Gerson Manuel (2022) Generalización del grafo de panqueques. Diploma thesis, Universidad de El Salvador.

Preview

Text TESIS FINAL.pdf Available under License Creative Commons Attribution Non-commercial. Download (5MB) | Preview

Abstract

En computación el ordenamiento de datos cumple un rol importante en la recolección de información, uno de los principales métodos de ordenamiento es el problema de los panqueques. Este consiste en ordenar una pila desordenada de panqueques de mayor a menor diámetro realizando la operación con una espátula para invertir el orden, es decir, dada una operación se le denomina reversión de prefijos o prefix-resersal en inglés. Ahora si se añade una variación al problema anterior se tiene el problema de los panqueques quemados, que consiste en ordenar una pila de panqueques desordenada pero con la diferencia que cada panqueque tiene un lado quemado. Además de ordenar cada panqueque por su tamaño debe cumplir que el lado quemado del panqueque quede en la parte de abajo. Estos métodos buscan ordenar con el menor número de reversiones posibles. Iniciando nuestra investigación con los concepto generales como: generalización del grupo simétrico denotado por S(m; n), donde el conjunto de vértices son permutaciones cuyos símbolos tiene m signos. Las permutaciones se denominará como permutaciones multisignos y el conjunto de aristas que se denotará por E(m; n) de la forma (tp;tp r�i), y a la generalización del grafo de panqueques denotaremos por G(m; n) donde m representa la cantidad de signos que posee un símbolo de una permutación y n representa el número de símbolos que posee una permutación. Luego con el estudio de los grafos de panqueques y grafo de panqueques quemados se refleja que los prefix-reversal, jugarán un papel importante para realizar la verificación de la existencia de los ciclos en el grafo G(3; n) donde a través de un algoritmo de búsqueda, se concluye que dicho grafo contiene todos los ciclos de longitud ` con 3 � ` � 3 n n!, verificando así que cumple ser Hamiltoniano y pancíclico. Finalizando con el estudio de la generalización del grafo de panqueques G(m; n) donde para estudiar el caso n � 4 se inicia el estudio con apoyo de un algoritmo de búsqueda donde se concluye la existencia del ciclo Hamiltoniano, pero no la existencia de la totalidad de los ciclos de longitud `con m � ` � m n n!.

Actions (login required)

View Item