Объединение матроидов, проверка множества на независимость — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.
 
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.
 
Множество <tex>U</tex> - независимо, если <tex>r(U) = |U|</tex>.
 
Множество <tex>U</tex> - независимо, если <tex>r(U) = |U|</tex>.
А можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \in M_{\oplus}, A \in I_{P_1}, P_1(A) \subset U} |U|</tex>.
+
А можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \in I, A \in I_{P_1}, P_1(A) \subset U} |A|</tex>.
 
Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].
 
Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].
  
 
== Литература ==
 
== Литература ==
 
Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
 
Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2

Версия 00:54, 26 июня 2011

Пусть нам даны три матроида:

[math]M_1 = \langle X, I_1 \rangle[/math],

[math]M_2 = \langle X, I_2 \rangle[/math],

[math]M = M_1 \cup M_2 = \langle X, I = \{A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle[/math].

Для простоты мы считаем, что носители в обоих матроидах одинаковы, если не так, то дополним их до объединения, заметим, что от этого [math]M_1[/math] и [math]M_2[/math] не перестанут быть матроидами.

Давайте зададим функцию [math]P_1[/math] : [math] X \times Y \rightarrow X[/math]: [math]P_1((x, y)) = x[/math], а для множества [math]B \in X \times Y[/math] выполняется [math]P_1(B) = \{A \subset X| \forall x \in A[/math] [math]\exists y \in B : P_1(y) = x\}[/math].

Определим ещё несколько матроидов, которые нам понадобятся:

[math]M_{\oplus} = M_1 \oplus M_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),[/math] [math] I = \{A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle[/math].

[math]M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),[/math] [math] I_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle[/math].

Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов. Множество [math]U[/math] - независимо, если [math]r(U) = |U|[/math]. А можно заметить, что в матроиде [math]M[/math] выполняется [math]r(U) = \max\limits_{A \in I, A \in I_{P_1}, P_1(A) \subset U} |A|[/math]. Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов [math]M_{\oplus}[/math] и [math]M_{P_1}[/math]. Мы это уже умеем делать - Алгоритм построения базы в пересечении матроидов.

Литература

Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2