34
правки
Изменения
Нет описания правки
}}
== Примеры ===== Простейшие примеры задач === * Типичным примером задачи, которая решается с помощью жадного алгоритма, является поиск остовного дерева. Остовное дерево — это база в графовом матроиде. Данная задача решается с помощью [http://informatics[Алгоритм Краскала| алгоритма Краскала]] * Еще одной типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с трансверсальным матроидом.mccmeРешается эта задача с помощью [[Алгоритм Куна| Алгоритма Кунв]].ru === Другие примеры ======= Матричный матроид ==== Рассмотрим матрицу с действительными кэффициентами <tex>[a_{ij}]</modtex>. Пусть <tex>E</statementstex> — множество её строк, <tex>I</viewtex> — семейство множеств линейно независимых строк.php?idДокажем, что <tex>M =3580| informatics:mccme:ru:Остовное дерево]\langle E, I \rangle</tex> — матроид.
== См. также ==
