Mostrar el registro sencillo del ítem

dc.contributor.advisorGarcía Marco, Ignacio 
dc.contributor.advisorPineda Ramos, José Fabrizio
dc.contributor.authorOval Trujillo, Zulema
dc.date.accessioned2021-06-24T12:01:02Z
dc.date.available2021-06-24T12:01:02Z
dc.date.issued2021
dc.identifier.urihttp://riull.ull.es/xmlui/handle/915/24111
dc.description.abstractEl objetivo principal de este trabajo es el estudio del problema de la coloraci´on de grafos haciendo uso de herramientas combinatorias y algebraicas. Comenzamos por la obtenci´on de cotas superiores e inferiores del n´umero crom´atico de un grafo y aportando algoritmos de coloraci´on (no necesariamente ´optima) de grafos. Tras esto, estudiamos la coloraci´on de grafos planares y demostramos varias versiones d´ebiles del Teorema de los cuatro colores, el cual establece que un grafo planar es 4-coloreable. Por ´ultimo caracterizamos la propiedad de que un grafo sea k-coloreable en t´erminos de la pertenencia de un cierto polinomio a un ideal. De este resultado deducimos un algoritmo que determina el n´umero crom´atico de un grafo. Incluimos una implementaci´on en singular del algoritmo propuesto.es
dc.description.abstractThe main objective of this work is the study of the graph coloring problem using combinatorial and algebraic tools. We begin by obtaining the upper and lower bounds on the chromatic number of a graph and providing coloring algorithms (not necessarily optimal) of graphs. After this, we study the coloring of planar graphs and prove some weaker versions of the Four Color Theorem, which states that a planar graph is 4-colorable. Finally, we characterize k-colorability of graphs in terms of the membership of a certain polynomial to an ideal. From this result we deduce an algorithm that determines the chromatic number of a graph. We include an implementation in singular of the proposed algorithm.en
dc.format.mimetypeapplication/pdf
dc.language.isoes
dc.rightsLicencia Creative Commons (Reconocimiento-No comercial-Sin obras derivadas 4.0 Internacional)
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.es_ES
dc.subjectColoración
dc.subjectGrafo planar
dc.subjectTeorema Combinatorio de los ceros
dc.titleColoración de Grafos
dc.typeinfo:eu-repo/semantics/bachelorThesis


Ficheros en el ítem

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

Licencia Creative Commons (Reconocimiento-No comercial-Sin obras derivadas 4.0 Internacional)
Excepto si se señala otra cosa, la licencia del ítem se describe como Licencia Creative Commons (Reconocimiento-No comercial-Sin obras derivadas 4.0 Internacional)