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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =  
 
|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>
+
  <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>. Иначе говоря, мы считаем что носители матроидов <tex>M_1</tex> и <tex>M_2</tex> не пересекаются.
 
}}
 
}}
 
{{Лемма
 
{{Лемма

Версия 21:00, 10 мая 2011

Определение:
[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]\mid A \mid \lt \mid B \mid \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]\mid A_1 \mid \lt \mid B_1 \mid[/math] или [math]\mid A_2 \mid \lt \mid B_2 \mid[/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]