Объединение матроидов, доказательство того, что объединение является матроидом — различия между версиями
Antonova (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 4 промежуточные версии 2 участников) | |||
Строка 2: | Строка 2: | ||
{{Лемма | {{Лемма | ||
− | |statement = <tex>M = \langle X, I \rangle</tex> — матроид, <tex> f \colon X \to Y</tex>. Тогда <tex>M_1 = \langle Y, I_1 = \mathcal \{ f(A) \mid A \in I \mathcal \} \rangle </tex> является матроидом. | + | |statement = <tex>M = \langle X, I \rangle</tex> — [[Определение матроида|матроид]], <tex> f \colon X \to Y</tex>. Также <tex>\exists f^{-1} \colon Y \to X</tex>. Тогда <tex>M_1 = \langle Y, I_1 = \mathcal \{ f(A) \mid A \in I \mathcal \} \rangle </tex> является матроидом. |
|proof = | |proof = | ||
Докажем аксиомы независимости для <tex> I_1 </tex>. | Докажем аксиомы независимости для <tex> I_1 </tex>. | ||
Строка 13: | Строка 13: | ||
{{Теорема | {{Теорема | ||
|statement = [[Объединение матроидов, проверка множества на независимость|Объединение матроидов]] является матроидом. | |statement = [[Объединение матроидов, проверка множества на независимость|Объединение матроидов]] является матроидом. | ||
− | |proof = Рассмотрим матроиды <tex>M_1</tex> и <tex>M_2</tex> из определения объединения матроидов. Из [[Прямая сумма матроидов|леммы]] знаем, что <tex> M_1 \oplus M_2= \langle X = X_1 \times \mathcal \{ 1 \mathcal \} \cup X_2 \times \mathcal \{ 2 \mathcal \}, I = \mathcal \{ A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2 \mathcal \} \rangle </tex> , где <tex> X_1 \times \mathcal \{ i \mathcal \} </tex> — декартово произведение множеств <tex> X_1 </tex> и <tex> \mathcal \{ i \mathcal \} </tex>, является матроидом. Пусть <tex>f \colon X_1 \times \mathcal \{ 1 \mathcal \} \cup X_2 \times \mathcal \{ 2 \mathcal \} \to X_1 \cup X_2 </tex>, такая, что <tex>f(x \times \mathcal \{ 1 \mathcal \}) \rightarrow x </tex>, <tex>f(x \times \mathcal \{ 2 \mathcal \}) \rightarrow x </tex>. Тогда по вышеизложенной лемме <tex> M_3 = \langle X_1 \cup X_2, I_3 = \mathcal \{ f(A) \mid A \in I \mathcal \} \rangle</tex> — матроид, в котором независимым множествам соответствуют объединения независимых множеств в <tex>M_1</tex> и <tex>M_2</tex>. То есть <tex>M_3 = M_1 \cup M_2</tex>. | + | |proof = Рассмотрим матроиды <tex>M_1</tex> и <tex>M_2</tex> из определения [[Объединение матроидов, проверка множества на независимость|объединения матроидов]]. Из [[Прямая сумма матроидов|леммы]] знаем, что <tex> M_1 \oplus M_2= \langle X = X_1 \times \mathcal \{ 1 \mathcal \} \cup X_2 \times \mathcal \{ 2 \mathcal \}, I = \mathcal \{ A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2 \mathcal \} \rangle </tex> , где <tex> X_1 \times \mathcal \{ i \mathcal \} </tex> — декартово произведение множеств <tex> X_1 </tex> и <tex> \mathcal \{ i \mathcal \} </tex>, является матроидом. Пусть <tex>f \colon X_1 \times \mathcal \{ 1 \mathcal \} \cup X_2 \times \mathcal \{ 2 \mathcal \} \to X_1 \cup X_2 </tex>, такая, что <tex>f(x \times \mathcal \{ 1 \mathcal \}) \rightarrow x </tex>, <tex>f(x \times \mathcal \{ 2 \mathcal \}) \rightarrow x </tex>. Тогда по вышеизложенной лемме <tex> M_3 = \langle X_1 \cup X_2, I_3 = \mathcal \{ f(A) \mid A \in I \mathcal \} \rangle</tex> — матроид, в котором независимым множествам соответствуют объединения независимых множеств в <tex>M_1</tex> и <tex>M_2</tex>. То есть <tex>M_3 = M_1 \cup M_2</tex>. |
}} | }} | ||
== См. также== | == См. также== | ||
+ | * [[Определение матроида]] | ||
* [[Объединение матроидов, проверка множества на независимость]] | * [[Объединение матроидов, проверка множества на независимость]] | ||
* [[Алгоритм построения базы в объединении матроидов]] | * [[Алгоритм построения базы в объединении матроидов]] |
Текущая версия на 19:10, 4 сентября 2022
Лемма: |
матроид, . Также . Тогда является матроидом. — |
Доказательство: |
Докажем аксиомы независимости для .
|
Теорема: |
Объединение матроидов является матроидом. |
Доказательство: |
Рассмотрим матроиды объединения матроидов. Из леммы знаем, что , где — декартово произведение множеств и , является матроидом. Пусть , такая, что , . Тогда по вышеизложенной лемме — матроид, в котором независимым множествам соответствуют объединения независимых множеств в и . То есть . | и из определения
См. также
- Определение матроида
- Объединение матроидов, проверка множества на независимость
- Алгоритм построения базы в объединении матроидов