O algoritmo ganancioso: uma introdução à teoria dos matroides

• Ano de defesa: 2023
• Autor(a) principal: Inácio Neto, Raimundo
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Matroides; Dependência linear; Matrizes (matemática); Teoria dos grafos; Algoritmo ganancioso; Matroids; Linear dependence; Matrices (mathematics); Graph theory; Greedy algorithm
• Link de acesso: http://www.repositorio.ufc.br/handle/riufc/70588

In Mathematics, a matroid is a structure presented as a general framework for the concept of linear independence. It is, therefore, naturally linked to Linear Algebra, but also to Graph Theory, the greedy algorithm and Geometry. (For various queries related to representation). This work aims to explicitly establish the relationship between this structure and the greedy algorithm. Starting from problems that require an optimized solution, we define the concept of matroid and its properties. Next, relations with matrices and graphs will be demonstrated, as well as some types of matroids, through theorems and examples. Finally, the theorem that consolidates the connection with the algorithm will be demonstrated.