Изменения
Новая страница: «== Определение 1 == {{Определение |definition = <tex>M_1 = \langle X_1, I_1 \rangle </tex> и <tex> M_2 = \langle X_2, I_2 \rangle </tex> —…»
== Определение 1 ==
{{Определение
|definition =
<tex>M_1 = \langle X_1, I_1 \rangle </tex> и <tex> M_2 = \langle X_2, I_2 \rangle </tex> — матроиды. Тогда <tex> M_1 \oplus M_2 = \langle X = X_1 \times \mathcal {f} 1 \mathcal {g} \cup X_2 \times \mathcal {f} 2 \mathcal {g}, I = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2 \mathcal {g} \rangle </tex>
}}
{{Лемма
|statement = Прямая сумма матроидов является матроидом.
|proof =
Докажем аксиомы независимости для <tex> I </tex>.
1. <tex>\varnothing \in I</tex>
<tex> A_1 = \varnothing \in I_1, A_2 = \varnothing \in I_2 \Rightarrow A_1 \cup A_2 = \varnothing \in I </tex>
2. <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
Пусть <tex>B = B_1 \cup B_2, B_1 \in I_1, B_2 \in I_2, A = A_1 \cup A_2, A_1 \subset B_1, A_2 \subset B_2</tex>. <tex>A_1 \subset B_1</tex>, значит по второй аксиоме для <tex>I_1</tex>, <tex>A_1 \in I_1</tex>. Аналогично <tex>A_2 \in I_2</tex>. Значит <tex>A_1 \cup A_2 \in I</tex>.
3. <tex>\mid A \mid < \mid B \mid \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
Пусть <tex>A = A_1 \cup A_2</tex>, <tex>B = B_1 \cup B_2</tex>. Тогда <tex>\mid A_1 \mid < \mid B_1 \mid</tex> или <tex>\mid A_2 \mid < \mid B_2 \mid</tex>. В первом случае из третьей аксиомы для <tex> I_1</tex>, <tex>\mathcal {9} x \in B_1 \setminus A_1, A_1 \cup \mathcal{f} x \mathcal {g} \in I_1 </tex>. Значит <tex> A_1 \cup \mathcal{f} x \mathcal {g} \cup A_2 \in I</tex>. Для второго случая аналогично.
}}
{{Определение
|definition =
<tex>M_1 = \langle X_1, I_1 \rangle </tex> и <tex> M_2 = \langle X_2, I_2 \rangle </tex> — матроиды. Тогда <tex> M_1 \oplus M_2 = \langle X = X_1 \times \mathcal {f} 1 \mathcal {g} \cup X_2 \times \mathcal {f} 2 \mathcal {g}, I = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2 \mathcal {g} \rangle </tex>
}}
{{Лемма
|statement = Прямая сумма матроидов является матроидом.
|proof =
Докажем аксиомы независимости для <tex> I </tex>.
1. <tex>\varnothing \in I</tex>
<tex> A_1 = \varnothing \in I_1, A_2 = \varnothing \in I_2 \Rightarrow A_1 \cup A_2 = \varnothing \in I </tex>
2. <tex>A \subset B, B \in I \Rightarrow A \in I</tex>
Пусть <tex>B = B_1 \cup B_2, B_1 \in I_1, B_2 \in I_2, A = A_1 \cup A_2, A_1 \subset B_1, A_2 \subset B_2</tex>. <tex>A_1 \subset B_1</tex>, значит по второй аксиоме для <tex>I_1</tex>, <tex>A_1 \in I_1</tex>. Аналогично <tex>A_2 \in I_2</tex>. Значит <tex>A_1 \cup A_2 \in I</tex>.
3. <tex>\mid A \mid < \mid B \mid \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex>
Пусть <tex>A = A_1 \cup A_2</tex>, <tex>B = B_1 \cup B_2</tex>. Тогда <tex>\mid A_1 \mid < \mid B_1 \mid</tex> или <tex>\mid A_2 \mid < \mid B_2 \mid</tex>. В первом случае из третьей аксиомы для <tex> I_1</tex>, <tex>\mathcal {9} x \in B_1 \setminus A_1, A_1 \cup \mathcal{f} x \mathcal {g} \in I_1 </tex>. Значит <tex> A_1 \cup \mathcal{f} x \mathcal {g} \cup A_2 \in I</tex>. Для второго случая аналогично.
}}
