This thesis correlates two important graph theory ideas, Kruskal's greedy algorithm and Hall's marriage theorem, with matroid theory. Kruskal's algorithm is related to the situations in which a matroid exists. Also, Hall's marriage theorem is proved in graph theory and set systems contexts and a matroid theory analogue, Rado's theorem, is described.
Identifier / keyword
Pure sciences; Greedy; Marriage; Matroid theory
Two well-known graph theory results and their relationship to matroid theory
MAI 49/06M, Masters Abstracts International
Place of publication
Country of publication
Hetzel, Andrew; Smith, David
Tennessee Technological University
United States -- Tennessee
Dissertations & Theses
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.