Материал из Викиконспекты
| Теорема (о циклах): |
Пусть [math]M(E)[/math] — матроид и [math]Ccl[/math] — семейство его циклов. Тогда:
1) [math]\varnothing \notin Ccl[/math];
2) Если [math]C_1, C_2 \in Ccl[/math] и [math]C_1 \ne C_2[/math], то [math]C_1 \nsubseteq C_2[/math] и [math]C_2 \nsubseteq C_1[/math];
3) Если [math]C_1, C_2 \in Ccl, C_1 \ne C_2[/math] и [math]p \in C_1 \cap C_2[/math], то существует [math]C \in Ccl[/math] такой, что [math]C \subseteq (C_1 \cup C_2) \setminus p.[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
1) Из определения матроида (первой аксиомы) [math]\varnothing \in I[/math], где [math]I[/math] — семейство независимых множеств матроида [math]M[/math]. Откуда [math]\varnothing \notin Ccl[/math].
2) От противного. Из определения цикла: если [math]C_1 \subset C_2[/math], то [math]C_1 \in I[/math]. Значит [math]C_1 \notin Ccl[/math]. Противоречие. Аналогично [math]C_2 \nsubseteq C_1[/math].
3) От противного. Пусть [math]D = (C_1 \cup C_2) \setminus p[/math] независимо.
Обозначим [math]A = C_1 \cap C_2[/math]. Покажем, что [math]|A| \lt |D|[/math]. Из предыдущего пункта очевидным образом следует, что [math]|C_1 \setminus C_2| \gt 0[/math] и [math]|C_2 \setminus C_1| \gt 0[/math].
[math]|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \ge |A| + 1 + 1 - 1 = |A| + 1 \gt |A|[/math] |
| [math]\triangleleft[/math] |
