Please use this identifier to cite or link to this item:
http://hdl.handle.net/2445/185604
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Benseny, Antoni | - |
dc.contributor.author | Sabater Rojas, Lluı́s | - |
dc.date.accessioned | 2022-05-17T07:21:54Z | - |
dc.date.available | 2022-05-17T07:21:54Z | - |
dc.date.issued | 2021-06-20 | - |
dc.identifier.uri | http://hdl.handle.net/2445/185604 | - |
dc.description | Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2021, Director: Antoni Benseny | ca |
dc.description.abstract | [en] The aim of the project is the study of maximal matchings in graphs, both in unweighted graphs and in weighted graphs. For the case of the graphs that are not weighted, we will see how Edmond's algorithm works, which will allows us to find a maximum cardinality matching. After studying the case without weights, we will introduce a few concepts of linear programming in order to be able to solve the weighted case, where we will look for maximum weight matchings. Finally, we will see the applications of these results when finding approximations (one upper bound and one lower bound) in polynomial time for the Travelling Salesman Problem, we will use Christofides’ algorithm to find an upper bound. | ca |
dc.format.extent | 53 p. | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | cat | ca |
dc.rights | cc-by-nc-nd (c) Lluı́s Sabater Rojas, 2021 | - |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/es/ | * |
dc.source | Treballs Finals de Grau (TFG) - Matemàtiques | - |
dc.subject.classification | Algorismes computacionals | ca |
dc.subject.classification | Treballs de fi de grau | - |
dc.subject.classification | Teoria de grafs | ca |
dc.subject.classification | Programació (Matemàtica) | ca |
dc.subject.other | Computer algorithms | en |
dc.subject.other | Bachelor's theses | - |
dc.subject.other | Graph theory | en |
dc.subject.other | Mathematical programming | en |
dc.title | Algorismes i aplicacions d’aparellaments maximals en grafs | ca |
dc.type | info:eu-repo/semantics/bachelorThesis | ca |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | ca |
Appears in Collections: | Treballs Finals de Grau (TFG) - Matemàtiques |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tfg_sabater_rojas_lluis.pdf | Memòria | 724.73 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License