Unit:
Department of Informatics and TelecommunicationsΠληροφορική
Author:
PAPAMICHAIL MERKOURIOS CHRISTOS
Supervisors info:
Σταύρος Κολλιόπουλος, καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Original Title:
ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΜΗΤΡΟΕΙΔΩΝ
Translated title:
INTRODUCTION TO MATROID THEORY
Summary:
In this thesis we present an introduction to Matroid Theory through some key results from
the literature. We study the notion of independence, through the discrete structure of the
matroid. We will see how the independence is presented in Graph Theory and Linear
Algebra and prove some fundamental properties of the independent sets. Next, we
axiomatize these properties stating different independence structures or matroid
representations and prove their equivalence. Lastly, we examine the connection between
matroids and optimization problems, where we define the greedy algorithm. There, we
prove that the algorithm’s optimality depends on how close the input is to a matroid.
Main subject category:
Science
Keywords:
matroid, linear indepentance, greedy algorithm, discrete structure, optimazation, linear algebra, graph theory
