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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
<tex>M_2 = \langle X, I_2 \rangle</tex>,  
 
<tex>M_2 = \langle X, I_2 \rangle</tex>,  
  
<tex>M = M_1 \cup M_2 = \langle X, I = {A | A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2} \rangle</tex>.
+
<tex>M = M_1 \cup M_2 = \langle X, I = \{A | A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle</tex>.
  
 
Для простоты мы считаем, что носители в обоих матроидах одинаковы, если не так, то дополним их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами.
 
Для простоты мы считаем, что носители в обоих матроидах одинаковы, если не так, то дополним их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами.
Строка 10: Строка 10:
  
 
Определим ещё несколько матроидов, которые нам понадобятся:  
 
Определим ещё несколько матроидов, которые нам понадобятся:  
<tex>M_{\oplus} = M_1 \oplus M_2 \langle (X \times {1}) \cup (X \times {2}), I = {A | A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2} \rangle</tex>,
+
<tex>M_{\oplus} = M_1 \oplus M_2 \langle (X \times {1}) \cup (X \times {2}), I = \{A | A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle</tex>,
 
Из предыдущей темы ([[Объединение матроидов, доказательство того, что объединение является матроидом]];) мы знаем, что  
 
Из предыдущей темы ([[Объединение матроидов, доказательство того, что объединение является матроидом]];) мы знаем, что  
для <tex>P_1((x, y)) = x</tex> - <tex>P_1(M_{\oplus}) = M</tex>, поэтому матроид <tex>M_{P_1} = \langle I_{P_1} = {A | |P_1(A)| = |A|} \rangle</tex>.
+
для <tex>P_1((x, y)) = x</tex> - <tex>P_1(M_{\oplus}) = M</tex>, поэтому матроид <tex>M_{P_1} = \langle I_{P_1} = \{A | |P_1(A)| = |A|\} \rangle</tex>.
  
  

Версия 04:23, 18 мая 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 | 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]M_{\oplus} = M_1 \oplus M_2 \langle (X \times {1}) \cup (X \times {2}), I = \{A | A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle[/math], Из предыдущей темы (Объединение матроидов, доказательство того, что объединение является матроидом;) мы знаем, что для [math]P_1((x, y)) = x[/math] - [math]P_1(M_{\oplus}) = M[/math], поэтому матроид [math]M_{P_1} = \langle I_{P_1} = \{A | |P_1(A)| = |A|\} \rangle[/math].


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