=== Графовый матроид ===
Типичным примером Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это [[Определение матроида| база ]] в графовом матроиде. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]].
=== Матроид паросочетаний ===
Еще одной типичной Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с [[Примеры матроидов| трансверсальным матроидом]]. Решается эта задача с помощью [[Алгоритм Куна для поиска максимального паросочетания| Алгоритма Куна]].
=== Матричный матроид ===
Последней Классической задачей, которую мы рассмотрим, будет нахождение максимального количества линейно независимых строк в матрице. Рассмотрим матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — матроид. Задача решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss e-maxx:ru:Метод Гаусса]</ref>
== См. также ==
