Written by: emcd123
For: Undergraduate Thesis for Mathematical Science at NUIG(National University of Ireland Galway)
A matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid, the most significant being in terms of independent sets, bases, circuits,etc.
Our primary target is to explain the connection between matroids and the greedy algorithm. The Greedy algorithm is an interesting characterization of matroids in that it arises frequently in problems related to combinatorial optimzation. For example the well known graph optimization problem: finding the minimum spanning tree. Leading to a connection between Kruskal’s algorithm and matroids.
https://en.wikipedia.org/wiki/Matroid https://en.wikipedia.org/wiki/Independence_system https://en.wikipedia.org/wiki/Greedy_algorithm https://en.wikipedia.org/wiki/Weighted_matroid https://en.wikipedia.org/wiki/Spanning_tree https://en.wikipedia.org/wiki/Depth-first_search https://en.wikipedia.org/wiki/Minimum_spanning_tree https://en.wikipedia.org/wiki/Kruskal's_algorithm
Will be written in Perl, Python, SageMath
Written in LaTeX
All LaTex can be found in LaTeXPdfs folder.
LaTeX
Can be run from https://www.sharelatex.com/
Or using TeX/ TeXmaker http://www.xm1math.net/texmaker/
Perl
See https://www.perl.org/ for information on how to run Perl(5 not 6)
Ptyhon
Can be run in the python interpreter Installed from https://www.python.org/
SageMath
Can be installed from http://doc.sagemath.org/html/en/installation/
Or run in the CoCalc(SageMath cloud service) https://cocalc.com
What is a matroid by James Oxley
Matroid Theory by James Oxley
Graphs, Networks and Algorithms by Dieter Jungnickel
Also, expository notes from NUIG linear algebra seminars