Матроиды Лекция 12

Введение Даны система множеств (E, F ), то есть конечное множество E, F 2 E и стоимостная функция c : F R, найти элемент из F, стоимость которого минимальна или максимальна. Далее мы предположим, что c модулярная функция множества, то есть c : E R и c(X) = Σ e X c(e).

Независимая система Определение 12.1 Система множеств (E, F ) называется независимой системой, если (M1) F ; (M2) Если X Y и Y F, то X F. Элементы F называются независимыми, элементы 2 E \ F зависимыми.

Циклы, базы Минимальные зависимые множества называются циклами. Максимальные независимые множества называются базами. Для X E максимальное независимое подмножество X называется базой X.

Ранг, замыкание Определение 12.2 Пусть (E, F ) независимая система. Для X E определим ранг X как r(X) := max{|Y| : Y X, Y F }. Далее, определим замыкание X как σ(X) := { y E: r(X {y}) = r(X)}.

Задача «Максимизация независимой системы» Дано: (E, F ) и c : E R. Найти: X F такую, что c(X) = Σ e X c(e) максимально.

Задача «Минимизация независимой системы» Дано: (E, F ) и c : E R. Найти базу B такую, что c(B) минимально.

Замечание Отметим, что в определении примеров описанных задач имеется некоторая неопределенность. Дано: (E, F ) и c : E R. Предполагается, что множество E и функция c задаются, как обычно списком элементов и списком значений, а подмножество F задается с помощью оракула, который определяет для данного подмножества F E, принадлежит F F или нет.

Задача «Независимое множество максимального веса» Дано: Граф G и веса c : V(G) R. Найти: независимое множество X в G максимального веса. E = V(G) и F = {F E: F независимое множество X в G}.

Задача Коммивояжера Дано: Полный граф G и веса c : E(G) R +. Найти: гамильтонов цикл в G минимального веса. E = E(G) и F = {F E: F подмножество Гамильтонового цикла в G}.

Задача «Кратчайший путь» Дано: Орграф G, веса c : E(G) R + и s, t V(G) так что t достижимо из s. Найти: кратчайший s-t-путь в G относительно c. E = E(G) и F = {F E: F подмножество s-t-пути}.

Задача «О рюкзаке» Дано: Неотрицательные числа c i, w i (1 i n), и k. Найти: подмножество S {1,..., n} такое, что Σ j S w j k и Σ j S c j максимальна. E = {1,..., n} и F = {F E: Σ j S w j k }.

Задача «Минимальное остовное дерево» Дано: Связный граф G и веса c : E(G) R. Найти: остовное дерево в G минимального веса. E = E(G) и F множество лесов в G.

Задача «Минимальное дерево Штейнера» Дано: Связный граф G, веса c : E(G) R +, и множество T V(G) терминалов. Найти: Дерево Штейнера для T, то есть дерево S с T V(S) и E(S) E(G) такое, что c(E(S)) минимально. E = E(G) и F = {F E: F подмножество дерева Штейнера для T}.

Задача «Максимальный взвешенный ориентированный лес» Дано: Орграф G и веса c : E(G) R. Найти: ориентированный лес в G максимального веса. E = E(G) и F множество ориентированных лесов в G.

Задача «Паросочетание максимального веса» Дано: Граф G и веса c : E(G) R. Найти: паросочетание максимального веса в G. E = E(G) и F множество паросочетаний в G.

Матроид Определение 12.3 Независимая система называется матроидом, (M3) если X, Y F и |X| > |Y|, то существует x X \ Y с Y {x} F.

Матроиды Утверждение 12.4 Следующие системы независимости (E, F ) являются матроидами: a) E множество столбцов матрицы A над некоторым полем, и F : = {F E: столбцы в E линейно независимые над этим полем}. b) E множество ребер некоторого графа G и F : = {F E: (V(G),F) лес}. c) E конечное множество, k целое и F : = {F E: |F| k}. d) E множество ребер некоторого графа G, S независимое множество в G, k s целые (s S) и F : = {F E: |δ F (s)| k s для всех s S }. e) E множество ребер некоторого орграфа G, S V(G), k s целые (s S) и F : = {F E: |δ - F (s)| k s для всех s S }.

Доказательство b) Пусть X, Y F и Y {x} F для всех x X\Y. Покажем, что | X | | Y |. p – число связных компонент в (V(G), X). q – число связных компонент в (V(G), Y). Для каждого ребра x = {v,w}, v и w лежат в одной компоненте связности (V(G), Y) каждая компонента связности (V(G), X) лежит в какой- то компоненте связности (V(G), Y) p q. V(G) – X = p q = V(G) – Y | X | | Y |.

Упражнение 12.1 Доказать пункты a), c), d), e) утверждения 12.4.

Независимая система Теорема 12.5 Пусть (E, F ) независимая система. Тогда следующие утверждения эквивалентны: (M3) Если X, Y F и |X| > |Y|, то существует x X \ Y с Y { x} F. (M3) Если X, Y F и |X| = |Y| + 1, то существует x X \ Y с Y { x} F. (M3) Для любого X E, все базы X имеют одинаковую мощность.

Нижний ранг Определение 12.6 Пусть (E, F ) независимая система. Для X E определим нижний ранг X как (X) := min{|Y|: Y X, Y F и Y {x} F для всех x X \ Y}. Ранговое отношение (E, F ):

Ранг и нижний ранг 2. E = E(G) и F = {F E: F подмножество гамильтонового цикла в G}. 1. E = E(G) и F множество лесов в G. r(X) = 3, (X) = 3, q(E, F ) = 1 r(X) = 4, (X) = 3, q(E, F ) = ) 2)

Ранговое отношение Утверждение 12.7 Пусть (E, F ) независимая система. Тогда q(E, F ) 1. (E, F ) матроид тогда и только тогда, когда q(E, F ) = 1.

Задача «Максимизация независимой системы» Дано: (E, F ) и c : E R. Найти: X F такую, что c(X) = Σ e X c(e) максимально.

Независимый оракул (E, F ) Дано множество F E. Оракул дает ответ принадлежит оно F (F F ) или нет.

Жадный алгоритм «Бери Лучший» Input: Независимая система (E, F ), заданная независимым оракулом и веса c : E R +. Output: Множество F F. 1) Упорядочим E = {e 1, e 2,..., e n } так, что c(e 1 )... c(e n ). 2)Set F :=. 3)For i := 1 to n do: If F {e i } F then set F := F {e i }.

Базисный Оракул Дано множество F E. Оракул дает ответ содержит F базу или нет.

Жадный алгоритм «Выбрось худший» Input: Независимая система (E, F ), заданная базисным оракулом и веса c : E R +. Output: Базис F системы (E, F ). 1) Упорядочим E = {e 1, e 2,..., e n } так, что c(e 1 )... c(e n ). 2)Set F := E. 3)For i := 1 to n do: If F \{e i } содержит базу then F := F\{e i }.

Оракулы Полиномиальная эквивалентность оракулов Задача «Коммивояжера» Задача «Кратчайший путь»

«Бери Лучший» Theorem 12.8 (Jenkyns [1976], Korte & Hausmann [1978]) Пусть (E, F ) независимая система. Для c : E R + обозначим через G(E, F,c) стоимость решения, найденного алгоритмом «Бери лучший» для задачи «Максимизация независимой системы». Тогда для всех c : E R +. Более того, существует стоимостная функция на которой нижняя оценка достигается.

Доказательство (определения) E={e 1, e 2,…, e n }, c : E R+ и c(e 1 ) c(e 2 ) … c(e n ). G n решение найденное алгоритмом «Бери Лучший». O n оптимальное решение. Определим E j = {e 1, e 2,…, e j }, G j = G nE j, O j = O nE j. Положим d n = c(e n ) и d j = c(e j ) – c(e j+1 ), j = 1,…n – 1. Так как O j F, то | O j | r(E j ). Так как G j база E j, то | G j | (E j ).

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

Доказательство (окончание) Покажем, что нижняя граница точна. Выберем F E и базы B 1 и B 2, такие что Определим Упорядочим e 1, e 2,…, e n, так что c(e 1 ) c(e 2 ) … c(e n ) и B 1 = {e 1,…, e |B 1 | }. Тогда G(E, F,c) = | B 1 | и OPT(E, F,c) = | B 2 |.

Теорема Эдмондса-Радо Теорема 12.9 (Rado[1957], Edmonds[1971]) Независимая система является матроидом тогда и только тогда, когда алгоритм «Бери лучший» находит оптимальное решение задачи максимизации независимой системы (E, F, c) для всех стоимостных функций c : E R +.

Упражнение 12.2 Доказать, что все независимые системы приведенные в лекции кроме введенной для Задачи «Минимальное остовное дерево» не являются матроидами.

Упражнение 12.3 Пусть G – граф, K – натуральное число и пусть F содержит те подмножества ребер E(G), которые являются объединением K лесов. Доказать, что (E(G), F т ) это матроид.