Introducción a la teoría de matroides

Simple item page
dc.contributor.advisorOlaya León, Wilson
dc.contributor.authorRugeles Triana, Iván Mauricio
dc.date.accessioned2024-03-04T01:15:09Z
dc.date.available2021
dc.date.available2024-03-04T01:15:09Z
dc.date.created2021
dc.date.issued2021
dc.description.abstractEn este trabajo se hace una introducción a la teoría de Matroides. Se presentarán algunas de las definiciones más usadas para referirse a una matroide, donde se incluyen resultados de la teoría de grafos, transversalese independencia lineal, todas ellas como sistemas axiomáticos. Mostraremos que todas estas definiciones son equivalentes, fenómeno conocido como criptomorfismo. También se mostrará una aplicación de la teoría de Matroides para solucionar problemas de optimización sobre grafos (algoritmo Greedy). En el primer capítulo se presentan los conceptos básicos de la teoría de grafos, espacios vectoriales y teoría de transversales, estos resultados serán utilizados para definir Matroides; en el segundo capítulo mostraremos los diferentesmodos de definir Matroides sin perder la esencia de la independencia lineal introducida por Whitney. Para finalizar, enel tercer capítulo, mostraremos la aplicación más conocida en la teoría de matroides, que permite solucionar algunos delos problemas de optimización sobre grafos, en este caso los problemas de optimización más usados son de maximizaro minimizar, donde el algoritmo que usaremos es óptimo cuando cumple los axiomas que definen a una matroide, encaso contrario el algoritmo no es óptimo. La forma como organizamos la presentación de este trabajo permite comprender de una manera sencilla la noción del termino matroide y su importancia en aplicaciones de optimización sobre grafos.
dc.description.abstractenglishIn this work an introduction to the theory of Matroids is made. We will present some of the most useddefinitions to refer to a matroid, including results from graph theory, transversals and linear independence, all of themas axiomatic systems. We will show that all these definitions are equivalent, a phenomenon known as cryptomorphism. We will also show an application of Matroid theory to solve optimization problems on graphs (Greedy algorithm). In the first chapter the basic concepts of graph theory, vector spaces and transversal theory are presented, these resultswill be used to define Matroids; in the second chapter we will show the different ways of defining Matroids withoutlosing the essence of linear independence introduced by Whitney. Finally, in the third chapter, we will show the bestknown application in matroid theory, which allows to solve some of the optimization problems on graphs, in this casethe most used optimization problems are to maximize or minimize, where the algorithm that we will use is optimalwhen it fulfills the axioms that define a matroid, otherwise the algorithm is not optimal. The way we organize the presentation of this work allows to understand in a simple way the notion of the term matroid and its importance in optimization applications on graphs.
dc.description.degreelevelPregrado
dc.description.degreenameMatemático
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/41321
dc.language.isospa
dc.publisherUniversidad Industrial de Santander
dc.publisher.facultyFacultad de Ciencias
dc.publisher.programMatemáticas
dc.publisher.schoolEscuela de Matemáticas
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.subjectIndependencia Lineal
dc.subjectGrafos
dc.subjectTransversales
dc.subjectMatroides
dc.subjectAlgoritmo Vo- Raz.
dc.subject.keywordLinear Independence
dc.subject.keywordGraphs
dc.subject.keywordTraversals
dc.subject.keywordMatroids
dc.subject.keywordGreedy Algorithm.
dc.titleIntroducción a la teoría de matroides
dc.title.englishIntroduction to matroid theory
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:
228.05 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Documento.pdf
Size:
323.79 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Nota de proyecto.pdf
Size:
7.03 KB
Format:
Adobe Portable Document Format
Download
Collections
Matemáticas