Изменения

* === Графовый матроид ===Типичным примером задачи, которая решается с помощью жадного алгоритма, является поиск остовного дерева. Остовное дерево — это база в графовом матроиде. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]

* === Матроид паросочетаний ===Еще одной типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с трансверсальным матроидом. Решается эта задача с помощью [[Алгоритм Кунадля поиска максимального паросочетания| Алгоритма КунвКуна]].

=== Другие примеры Матричный матроид ===Последней задачей, которую мы рассмотрим, будет нахождение максимального количества линейно независимых строк в матрице. Рассмотрим матрицу с действительными кэффициентами <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>

Рассмотрим матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Докажем, что <tex>M = \langle E, I \rangle</tex> — матроид.  == См. также ==