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

Abstract

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.