Прямая сумма матроидов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
Пусть <tex>A = A_1 \cup A_2</tex>, <tex>B = B_1 \cup B_2</tex>. Тогда <tex>|A_1| < |B_1|</tex> или <tex>|A_2| < |B_2|</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>. Второй случай аналогичен первому.
 
Пусть <tex>A = A_1 \cup A_2</tex>, <tex>B = B_1 \cup B_2</tex>. Тогда <tex>|A_1| < |B_1|</tex> или <tex>|A_2| < |B_2|</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>. Второй случай аналогичен первому.
 
}}
 
}}
 +
 +
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Матроиды]]

Версия 13:23, 2 мая 2014

Определение:
[math]M_1 = \langle X_1, I_1 \rangle [/math] и [math] M_2 = \langle X_2, I_2 \rangle [/math] — матроиды. Тогда [math] 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 [/math]. Иначе говоря, мы считаем, что носители матроидов [math]M_1[/math] и [math]M_2[/math] не пересекаются.
Лемма:
Прямая сумма матроидов является матроидом.
Доказательство:
[math]\triangleright[/math]

Докажем аксиомы независимости для [math] I [/math].

1. [math]\varnothing \in I[/math]

[math] A_1 = \varnothing \in I_1, A_2 = \varnothing \in I_2 \Rightarrow A_1 \cup A_2 = \varnothing \in I [/math]

2. [math]A \subset B, B \in I \Rightarrow A \in I[/math]

Пусть [math]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[/math]. [math]A_1 \subset B_1[/math], значит по второй аксиоме для [math]I_1[/math], [math]A_1 \in I_1[/math]. Аналогично [math]A_2 \in I_2[/math]. Значит [math]A_1 \cup A_2 \in I[/math].

3. [math]|A| \lt |B| \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I[/math]

Пусть [math]A = A_1 \cup A_2[/math], [math]B = B_1 \cup B_2[/math]. Тогда [math]|A_1| \lt |B_1|[/math] или [math]|A_2| \lt |B_2|[/math]. В первом случае по третьей аксиоме для [math] I_1[/math], [math]\mathcal {9} x \in B_1 \setminus A_1, A_1 \cup \mathcal{f} x \mathcal {g} \in I_1 [/math]. Значит [math] A_1 \cup \mathcal{f} x \mathcal {g} \cup A_2 \in I[/math]. Второй случай аналогичен первому.
[math]\triangleleft[/math]