Теорема Радо-Эдмондса (жадный алгоритм)

Теорема Радо-Эдмондса

Теорема (Радо-Эдмондса):

На носителе матроида [math]M = \langle X, I \rangle[/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Пусть [math]A \in I[/math] — множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k[/math]. Возьмем [math]x: A \cup x \in I[/math], [math]x \notin A[/math], [math]\omega (x)[/math] — минимальна. Тогда [math]A \cup x[/math] — множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим [math]B \in I[/math] — множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math]. Из определения матроида: [math]\exists y \in B\setminus A : A \cup y \in I[/math]. Тогда верны два неравенства: [math]\omega (A \cup y) = \omega (A) + \omega (y) \geqslant \omega (B) \Rightarrow \omega (A) \geqslant \omega (B) - \omega (y)[/math], [math]\omega (B \setminus y) = \omega (B) - \omega (y) \geqslant \omega (A)[/math]. Заметим, что величина [math]\omega (A)[/math] с двух сторон ограничивает величину [math]\omega (B) - \omega (y)[/math]. Значит, эти величины равны: [math]\omega (A) = \omega (B) - \omega (y) \Rightarrow \omega (A) + \omega (y) = \omega (B)[/math]. Следовательно, [math]\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)[/math]. Таким образом получаем, что если объединить множество [math]A[/math] с [math]x[/math] — минимальным из таких, что [math]A \cup x \in I[/math], — то получим множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].

[math]\triangleleft[/math]

Жадный алгоритм поиска базы минимального веса

Теорема (жадный алгоритм поиска базы минимального веса):

Пусть на носителе матроида [math]M = \langle X, I \rangle[/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Для любого [math]A \subset X[/math] выполнено: [math]\omega(A) = \sum\limits _{x \in A} \omega(x)[/math]. Тогда база минимального веса матроида [math]M[/math] ищется жадно.

Доказательство:

[math]\triangleright[/math]

Пусть [math]n = |X|[/math]¸ а [math]m[/math] — время, за которое выполняется проверка множества на независимость. Псевдокод алгоритма: sort(X) // сортируем элементы по возрастанию веса [math]B \leftarrow \varnothing[/math] for [math]i \leftarrow 0[/math] to [math]n-1[/math] if [math]B \cup X[i] \in I[/math] [math]B \leftarrow B \cup X[i][/math] Рассмотрим шаг алгоритма, на котором мы пытаемся добавить элемент [math]X[i][/math]. Заметим, что если при его добавлении сохраняется независимость множества [math]B[/math], то это элемент минимального веса не из [math]B[/math]. В самом деле, пусть [math]X[j][/math] — элемент минимального веса не из [math]B[/math], который можно добавить к [math]B[/math] с сохранением его независимости, тогда [math]j\lt i[/math]. Но тогда он уже был бы добавлен на [math]j[/math]-ом шаге алгоритма. Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По теореме Радо-Эдмондса множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из [math]X[/math] так, чтобы после каждого добавления множество оставалось независимым. Алгоритм работает за [math]O(n \log n + mn)[/math]. На сортировку элементов из [math]X[/math] по возрастанию весов уходит [math]O(n \log n)[/math]. После чего, построение базы выполняется [math]O(n)[/math] шагов цикла, каждый из которых работает [math]O(m)[/math] времени. Однако, если считать, что проверка множества на независимость происходит за [math]O(1)[/math], асимптотика алгоритма будет [math]O(n \log n)[/math]

[math]\triangleleft[/math]

Примеры

Графовый матроид

Примером задачи, которая решается с помощью жадного алгоритма, является поиск остовного дерева. Остовное дерево — это база в графовом матроиде. Данная задача решается с помощью алгоритма Краскала. Код данного алгоритма совпадает с псевдокодом алгоритма поиска базы минимального веса, который был приведен выше.

Матроид паросочетаний

Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с трансверсальным матроидом. Решается эта задача с помощью алгоритма Куна.

Матричный матроид

Рассмотрим задачу о нахождении максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами [math][a_{ij}][/math]. Пусть [math]E[/math] — множество её строк, [math]I[/math] — семейство множеств линейно независимых строк. Тогда [math]M = \langle E, I \rangle[/math] — матричный матроид. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса

См. также

• Теорема о базах
• Теорема Эдмондса-Лоулера

Источники информации

• Википедия — Жадный алгоритм Радо-Эдмондса
• Greedy Algorithm And Edmonds Matroid Intersection Algorithm
• Habrahabr — Жадные алгоритмы