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

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

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

На носителе матроида задана весовая функция . Пусть — множество минимального веса среди независимых подмножеств мощности . Возьмем , , — минимальна.
Тогда — множество минимального веса среди независимых подмножеств мощности .

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

Рассмотрим [math]B \in I[/math] — множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].

Из определения матроида: .

Тогда верны два неравенства:
,
.

Заметим, что величина [math]\omega (A)[/math] с двух сторон ограничивает величину [math]\omega (B) - \omega (y)[/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] так, чтобы после каждого добавления множество оставалось независимым.

Алгоритм работает за . На сортировку элементов из по возрастанию весов уходит . После чего, построение базы выполняется шагов цикла, каждый из которых работает времени. Однако, если считать, что проверка множества на независимость происходит за , асимптотика алгоритма будет

Простейшие примеры задач

informatics:mccme:ru:Остовное дерево

См. также

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

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