34
правки
Изменения
Нет описания правки
== Теорема Радо-Эдмондса ==
{{Теорема
|about=
Тогда верны два неравенства:
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) \ge geqslant \omega (B) \Rightarrow \omega (A) \ge geqslant \omega (B) - \omega (y)</tex>,<br><tex>\omega (B \setminus y) = \omega (B) - \omega (y) \ge geqslant \omega (A)</tex>.
Заметим, что величина <tex>\omega (A)</tex> с двух сторон ограничивает величину <tex>\omega (B) - \omega (y)</tex>. Значит, эти величины равны:
== Жадный алгоритм поиска базы минимального веса ==
Обозначим: <br><tex>n = |X|</tex> <br><tex>m =</tex> время, за которое мы проверяем на независимость. <br>
{{Теорема
|about=
|proof=
Псевдокод алгоритма:
<tex>B \leftarrow \varnothing</tex>
'''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>|X|n-1</tex> '''do'''
'''if''' <tex>B \cup X[i] \in I</tex>
<tex>B \leftarrow B \cup X[i]</tex>
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
Алгоритм работает за <tex>O(|X| m \cdot n \log(|X|)n)</tex>. На сортировку элементов из <tex>X</tex> по возрастанию весов уходит <tex>O(|X| n \log(|X|)n)</tex> и <tex>O(|X|n)</tex> шагов цикла, каждый из которых работает <tex>O(1m)</tex> времени (. Однако, если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>, асимптотика алгоритма будет <tex>O(n \log n).</tex>
}}
== Примеры задач ==
* [http://informatics.mccme.ru/mod/statements/view.php?id=3580| informatics:mccme:ru:Остовное дерево]
== Источники информации ==
* [[wikipedia:ru:Жадный алгоритм Радо — Эдмондса | Википедия — Жадный алгоритм Радо-Эдмондса]]
* [http://www.mathematik.hu-berlin.de/~wilhelm/greedy-vortrag.pdf| Greedy Algorithm And Edmonds Matroid Intersection Algorithm]
* [http://habrahabr.ru/post/120343/| Habrahabr:Жадные алгоритмы]
== Смотрите также ==
* [[Теорема о базах]]
* [[Теорема Эдмондса-Лоулера]]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
