Restricciones planares de problemas duros un estudio de caso

Simple item page
dc.contributor.advisorMontoya Arguello, Juan Andrés
dc.contributor.authorRamos Chaux, Jonnathan Alfredo
dc.date.accessioned2024-03-03T18:38:31Z
dc.date.available2011
dc.date.available2024-03-03T18:38:31Z
dc.date.created2011
dc.date.issued2011
dc.description.abstractLos grafos son estructuras matemáticas útiles en labores de modelado dentro de diversas áreas del conocimiento. En particular, el isomorfismo de grafos brinda la posibilidad de extender propiedades de interés, que se sabe presentes en un grafo, a otro, gracias a la existencia de una función denominada de isomorfismo que a cada vértice de un grafo le asigna como imagen un vértice en el otro grafo de modo tal que la relación de adyacencia es preservada. Dados dos grafos, saber si son isomorfos (problema del isomorfismo de grafos) es un problema que a día de hoy no puede ser resuelto por una máquina determinista en tiempo polinomial. Sin embargo, es sabido que clases específicas como la que agrupa a los grafos planos puede ser solucionada de manera eficiente. En este proyecto se estudia el problema del isomorfismo de grafos centrando la atención, particularmente, en su complejidad computacional y en la versión del problema restringida a grafos planos. También es estudiado un algoritmo que puede ser implementado capaz de, dados dos grafos planos como entrada, decidir si los grafos del input son isomorfos en un tiempo . La metodología utilizada por el algoritmo consiste en la generación de un código único que identifica cada grafo de modo tal que dos grafos serán isomorfos si y solo si dichos códigos son iguales.
dc.description.abstractenglishGraphs are mathematical structures useful in modeling labors within various fields of knowledge. In particular, the graph isomorphism provides the possibility of extending properties of interest from one graph to another, thanks to assigns to each vertex of a graph, as image, a vertex in the other graph such that the adjacency relation is preserved from one graph to another. Given two graphs, knowing if they are isomorphic (graph isomorphism problem) is a problem that cannot be solved by a deterministic Turing machine in polynomial time. However, it is known that to specific classes, such as planar graphs, the problem can be solved efficiently. In this Project, the graph isomorphism problem is studied focusing the attention, particularly, on their computational complexity and the version of the problem restricted to planar graphs. It is also considered an algorithm, which can be implemented and capable to, given two planar graphs as input, decide in units of time if they are isomorphic. The methodology used by the algorithm consists in construct a unique code that identifies each graph such that two graphs are isomorphic if and only if their codes are the same.
dc.description.degreelevelPregrado
dc.description.degreenameIngeniero de Sistemas
dc.format.mimetypeapplication/pdf
dc.identifier.instnameUniversidad Industrial de Santander
dc.identifier.reponameUniversidad Industrial de Santander
dc.identifier.repourlhttps://noesis.uis.edu.co
dc.identifier.urihttps://noesis.uis.edu.co/handle/20.500.14071/25192
dc.language.isospa
dc.publisherUniversidad Industrial de Santander
dc.publisher.facultyFacultad de Ingenierías Fisicomecánicas
dc.publisher.programIngeniería de Sistemas
dc.publisher.schoolEscuela de Ingeniería de Sistemas e Informática
dc.rightshttp://creativecommons.org/licenses/by/4.0/
dc.rights.accessrightsinfo:eu-repo/semantics/openAccess
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)
dc.rights.licenseAttribution-NonCommercial 4.0 International (CC BY-NC 4.0)
dc.rights.urihttp://creativecommons.org/licenses/by-nc/4.0
dc.subjectIsomorfismo de Grafos
dc.subjectComplejidad Computacional
dc.subjectComputación Teórica
dc.subjectProblemas Intermedios.
dc.subject.keywordGraph isomorphism
dc.subject.keywordComputational complexity
dc.subject.keywordTheoretical Computing
dc.subject.keywordRestrictions
dc.subject.keywordHard Problems.
dc.titleRestricciones planares de problemas duros un estudio de caso
dc.title.englishPlanar restrictions of hard problems: a case study
dc.type.coarhttp://purl.org/coar/version/c_b1a7d7d4d402bcce
dc.type.hasversionhttp://purl.org/coar/resource_type/c_7a1f
dc.type.localTesis/Trabajo de grado - Monografía - Pregrado
Files
Original bundle
Now showing 1 - 3 of 3
No Thumbnail Available
Name:
Carta de autorización.pdf
Size:
318.05 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Documento.pdf
Size:
2.22 MB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Nota de proyecto.pdf
Size:
266.71 KB
Format:
Adobe Portable Document Format
Download
Collections
Ingeniería de Sistemas