Объединение матроидов, проверка множества на независимость — различия между версиями
Строка 49: | Строка 49: | ||
# <tex>\varnothing \in I_1</tex> <br /><tex> \varnothing = f(\varnothing) \in I_1 </tex> | # <tex>\varnothing \in I_1</tex> <br /><tex> \varnothing = f(\varnothing) \in I_1 </tex> | ||
− | # <tex>B \subset A, A \in I_1 \Rightarrow B \in I_1</tex><br /><tex>A \in I_1</tex>, значит <tex> | + | # <tex>B \subset A, A \in I_1 \Rightarrow B \in I_1</tex><br /><tex>A \in I_1</tex>, значит <tex>\exists S, S \in I</tex>, такое, что <tex> A = f(S)</tex>. <tex>B = f(S \setminus f^{-1} (A \setminus B)), (S \setminus f^{-1} (A \setminus B)) \subset S \Rightarrow (S \setminus f^{-1} (A \setminus B)) \in I</tex>. Значит <tex>B \in I_1</tex>. |
− | # Пусть <tex> A \in I_1, A = f(S), B \in I_1, B = f(T), |A| > |B|</tex>. Докажем, что <tex> | + | # Пусть <tex> A \in I_1, A = f(S), B \in I_1, B = f(T), |A| > |B|</tex>. Докажем, что <tex>\exists y \in A \setminus B, B \cup \{ y \} \in I_1</tex><br /><tex>A = f(S) \Rightarrow \exists S_1 \subset S, A = f(S_1), |S_1| = |A| </tex>.<br /><tex>B = f(T) \Rightarrow \exists T_1 \subset T, B = f(T_1), |T_1| = |B| </tex>.<br /><tex>S_1 \in I, T_1 \in I</tex> по второй аксиоме для <tex>M</tex>.<br /><tex> |S_1| > |T_1| </tex>, значит по третьей аксиоме для <tex>M</tex>, <tex>\exists x \in S_1 \setminus T_1, T_1 \cup \{ x \} \in I</tex>. Следовательно <tex>f(T_1 \cup \{ x \}) \in I_1</tex>.<br /><tex>f(T_1 \cup \{ x \}) = f(T_1) \cup f(x) = B \cup f(x)</tex> Значит <tex>\exists y = f(x) \in A \setminus B , B \cup \{ y \} \in I_1</tex> |
}} | }} | ||
Версия 18:44, 11 декабря 2018
Определение: |
Пусть аксиомам независимости, следовательно, — матроид, для которого служит набором независимых множеств. Этот матроид называется объединением матроидов (англ. matroid union) и , и обозначается | и — два матроида на множестве элементов с наборами независимых множеств и . Положим . Множество удовлетворяет
Обычно термин «объединение» применяется, когда носители прямой суммой матроидов.
в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого и не перестанут быть матроидами. Если в и носители непересекающиеся, то это будет являтьсяВерны следующие утверждения про объединение матроидов:
- Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.
- В отличие от пересечения матроидов, объединение двух конечных матроидов (англ. finite matroid) всегда является матроидом, однако объединение двух бесконечных матроидов (англ. infinite matroid) не обязательно будет им.
- Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечением матроидов.
Содержание
Проверка множества на независимость
Задача: |
Дан матроид | . Необходимо проверить, является ли некоторое множество независимым, то есть, лежит ли оно в .
Для решения этой задачи преобразуем каждый элемент множества в матроиде в , а каждый элемент множества в матроиде в . Мы получили два матроида и .
Определим функцию
: , при этом , а для множества выполняется . Тогда функция на носителях матроидов и будет являться естественным отображением , где .Затем определим два матроида, которые нам далее понадобятся:
- — прямая сумма двух матроидов (носители матроидов и при пересечении будут давать пустое множество).
- — в данном случае будет содержать такие независимые множества, что мощность любого множества из будет равна мощности множества, получаемого функцией над , то есть не будет содержать одновременно и .
Теперь перейдём к нашей задаче.
Множество ранговая функция . Можно заметить, что в матроиде выполняется . Таким образом, мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов и . С помощью алгоритма построения базы в пересечении матроидов найдем размер максимального подмножества в пересечении наборов независимых множеств матроидов.
является независимым, еслиДоказательство того, что обединение матроидов является матродидом
Определение: |
и — матроиды. Тогда . |
Лемма: |
— матроид, . Тогда является матроидом. |
Доказательство: |
Докажем аксиомы независимости для .
|
Теорема: |
Объединение матроидов является матроидом. |
Доказательство: |
Рассмотрим матроиды леммы знаем, что является матроидом. Пусть , такая, что , . Тогда по лемме — матроид, в котором независимым множествам соответствуют объединения независимых множеств в и . То есть . | и из определения объединения матроидов. Из
См. также
Источники информации
- Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. — Лекции по теории графов
- Chandra Chekuri — Combinatorial Optimization
- Michel X. Goemans — Advanced Combinatorial Optimization
- Wikipedia — Matroid