ТГиК-2019-Лекция-23.12.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Матроиды

Вспомним определение матроида. Пара \(<X, U> \) - матроид.

Обязательно должны выполняться следующие условия:

1) \( \varnothing \in U \)

2) \( A \in U, B \subseteq A \Longrightarrow B \in U \)

3) \( A, B \in U, |B|>|A| \Longrightarrow \exists x \in B \backslash A : A \cup \left \{ x \right \} \in U \)

Важное определение для матроидов - база матроида. База матроида - это максимальное по включению множество

Пример. Пусть есть некоторое подмножество \(A\) множества \(U\) такое, что в него нельзя ничего добавить\(\mbox{:} \forall x \in X \mbox{ } A \cup \left \{ x \right \} \not\in U \) Тогда \(A\) - максимальное по включению множество.

Теорема о равномощности матроидов

Все базы матроида равномощны

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

Доказательство проведём от противного.

1) Пусть \(A, B \) - произвольные базы матроида, причём \(|B| > |A| \).

2) По 3 свойству можно найти в \(B\) некоторый элемент такой, что если добавить его в \(A\), то мы останемся в U\( \mbox{: } \exists b \in B \backslash A \mbox{: } A \cup \left \{ b \right \} \in U \).

3) Следовательно, так как в \(A\) можно добавить элемент, \(A\) не максимальное множество по включению. То есть \(A\) - не база. Получили противоречие. Значит, все базы матроида равномощны в силу произвольного выбора.

Применение матроидов

Введём весовую функцию \( \omega \mbox{: } X \longrightarrow R \). Необходимо найти базу наибольшего веса. Для этого используем жадный алгоритм

Шаг 0. \(A_0 = \varnothing\)

Шаг i+1. \(A_{i+1} = A_I \cup \left \{ a_i \right \} \)

То есть на каждом шаге мы к имеющемуся множеству добавляем элемент \(a_i\) - элемент с максимальным весом, такой, что добавление его не выводит за пределы U, т.е. \( a_i = arg \mbox{ } max \mbox{ } \omega (a) \mbox{, где } a \in X \backslash A_i , A_i \cup \left \{ a \right \} \in U \)

Алгоритм прекращается, когда подходящее \(a_i\) не находится.

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

Теорема: жадный алгоритм корректен тогда и только тогда, когда \(<X, U> \) - матроид

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

\(\Longrightarrow \)

1) Докажем, что если \(<X, U> \) - не матроид, то алгоритм некорректен.

Пусть \(<X, U> \) - не матроид. Так как это не матроид, то какое-то из 3 свойств нарушено. 1 свойство не рассматривается.

2) Пусть нарушено второе свойство (\( A \in U, B \subseteq A \Longrightarrow B \in U \)).

Пусть сначала второе свойство выполнено. Например, в матроиде находятся подмножества \(A_0, A_1, A_2, A_3, A_4 \) множества \(A_5 \). Нарушим второе свойство, убрав подмножество \(A_3 \). Тогда алгоритм не создаст базу, то есть жадный алгоритм некорректен. Получим противоречие.

3) Пусть нарушено третье свойство ( \( A, B \in U, |B|>|A| \Longrightarrow \exists x \in B \backslash A : A \cup \left \{ x \right \} \in U \))

Введём \(X = A \sqcup B \), где \(A\) и \(B\) разных размеров\(\mbox{: } |B| = m > |A| = n \). Пусть \(U = 2^A \cup 2^B \) - объединение всех подмножеств данных двух множеств. Заметим, что свойство 2 выполняется.

4) Пусть \( \forall a \in A \mbox{ } \omega (a) = x, \forall b \in B \mbox{ } \omega (b) = x - \varepsilon \), где \(\varepsilon > 0 \)

5) Так как вес элементов А больше, то жадный алгоритм вернёт множество А с \( \omega (A) = xn \)

6) В то же время, \( \omega (B) = xm - \varepsilon m \)

7) Очевидно, если \( \omega (B) > \omega (A)\), жадный алгоритм проигрывает. При каких \(\varepsilon \) это происходит?

\( xm - \varepsilon m > xn \), откуда \( \varepsilon < x \frac{m-n}{m} \)
\(\Longleftarrow \)

1) Пусть жадный алгоритм построил некоторую базу \(\left \{ a_1, a_2, ..., a_k \right \} \), а база \(\left \{ b_1, b_2, ..., b_k \right \} \) - оптимальная база, то есть правильный ответ.

2) Для удобства положим, что они упорядочены, то есть \( \omega (a_i) \ge \omega (a_{i+1}) \) и \( \omega (b_i) \ge \omega (b_{i+1}) \)

3) Пусть \( \omega (b_{i+1}) > \omega (a_{i+1}) (*)\)

4) По свойству 2 матроида \( \left \{ a_1, a_2, ..., a_i \right \} \in U \) и \( \left \{ b_1, b_2, ..., b_{i+1} \right \} \in U \)

5) По свойству 3 матроида \( \exists b_j \in B_{i+1} \backslash A_i : \mbox{ } a_i \cup \left \{ b_j \right \} \in U; \omega (b_j) \ge \omega (b_{i+1}) \)

6) Согласно жадному алгоритму \( \omega (a_{i+1}) \ge \omega (b_j) \ge \omega (b_{i+1}) \)

Получили противоречие с \((*)\). Следовательно, жадный алгоритм возвращает базу с максимальным весом

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

рис.1

Пусть рассматривается граф \( G = <V, E> \). Тогда \( <E,U> \) - матроид, где \(U\) - ациклические множества рёбер. Примеры представлены на рис.1.

Проверим свойства матроида.

1) Очевидно

2) Если убрать одно ребро, циклы не образуются. Следовательно, свойство 2 выполняется

3) Докажем справедливость свойства 3.

3.1) Пусть есть два ациклические множества рёбер \(A \mbox{ и } B, |B| > |A| \) и свойство 3 не выполняется, то есть \( \forall b \in B \backslash A : A \cup \left \{ b \right \} \) содержит цикл.

3.2) В то же время \( \forall b \in B \backslash A \) соединяют вершины из одной компоненты связности \(A\). Следовательно, все компоненты связности \(B\) находятся внутри компонент связности \(A\)

3.3) Любая компонента связности \(A\) - дерево. Дерево содержит \(n\) рёбер, если в нём \(n+1\) вершин. Компоненты связности \(B\), принадлежащие компонентам связности \(A\), содержит \( \le n \) рёбер.

Следовательно, \( |B| \le |A| \). Получим противоречие.

Задача максимального (минимального) остовного подграфа. Алгоритм Крускала

Подграф - остовной, если он содержит все вершины, но при этом не содержит циклов. Обычно задача минимального остовного графа на практике задаётся следующим образом: есть n городов и стоимость строительства каждой дороги между этими городами. Требуется выбрать дороги так, чтобы общая сумма строительства была минимальной.

Один из способов решения данной задачи - жадный алгоритм Крускала.

Алгоритм Крускала

Шаг 0. \(A_0 = \varnothing\)

Шаг 1. \(A_1 = \left \{ arg \mbox{ } max \mbox{ } \omega (e), e \in E \right \}\)

Шаг i+1. \( A_{i+1} = A_i \cup \left \{ e_i \right \} \), причём \(e_i\) с максимальным весом такое, что при добавлении этого элемента \(A_{i+1} \) получится без циклов.

Как мы сможем проверить, что при добавлении элемента циклов не появится? Пусть ребро \(e_i\) соединяет вершины \(v\) и \(u\). При добавлении ребра цикла не будет, если эти вершины будут находиться в разных компонентах связности.

DSU подходит для хранения компонент связности. DSU было изучено здесь

Root(x)==Root(y) \( \Longrightarrow \) x,y находятся в одном подмножестве.

Вывод: добавляем ребро \(e_i\) и запускаем unite