34
правки
Изменения
Нет описания правки
Радо-Эдмондса
|statement=
На носителе [[Определение матроида | матроида]] <tex>M = \langle X, I \rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Пусть <tex>A \in I</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k</tex>. Возьмем <tex>x: A \cup x \in I</tex>, <tex>x \notin A</tex>, <tex>\omega (x)</tex> {{---}} минимальна.
<br> Тогда <tex>A \cup x</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
|proof=
жадный алгоритм поиска базы минимального веса
|statement=
Пусть на носителе матроида <tex>M = \langle X, I \rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Для любого <tex>A \subset X</tex> выполнено: <tex>\omega(A) = \sum\limits _{x \in A} \omega(x)</tex>. Тогда [[Определение матроида| база ]] минимального веса матроида <tex>M</tex> ищется жадно.
|proof=
Пусть <tex>n = |X|</tex>¸ а <tex>m</tex> — время, за которое выполняется проверка множества на независимость.
=== Графовый матроид ===
Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это [[Определение матроида| база]] в графовом [[Определение матроидаПримеры матроидов#.D0.93.D1.80.D0.B0.D1.84.D0.BE.D0.B2.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| графовом матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма один в один копирует код алгоритма поиска базы минимального веса, который был приведен выше.
=== Матроид паросочетаний ===
Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с [[Примеры матроидов#.D0.A2.D1.80.D0.B0.D0.BD.D1.81.D0.B2.D0.B5.D1.80.D1.81.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| трансверсальным матроидом]]. Решается эта задача с помощью [[Алгоритм Куна для поиска максимального паросочетания| алгоритма Куна]].
=== Матричный матроид ===
Рассмотрим задачу о нахождение максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — [[Примеры матроидов#.D0.9C.D0.B0.D1.82.D1.80.D0.B8.D1.87.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| матричный матроид]]. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss MAXimal :: algo :: Метод Гаусса]</ref>
== См. также ==
