Теорема о циклах — различия между версиями
| Строка 3: | Строка 3: | ||
о циклах | о циклах | ||
|statement= | |statement= | ||
| − | Пусть <tex>M | + | Пусть <tex>M</tex> {{---}} матроид и <tex>Ccl</tex> {{---}} семейство его циклов. Тогда: <br/> |
1) <tex>\varnothing \notin Ccl</tex>; <br/> | 1) <tex>\varnothing \notin Ccl</tex>; <br/> | ||
2) Если <tex>C_1, C_2 \in Ccl</tex> и <tex>C_1 \ne C_2</tex>, то <tex>C_1 \nsubseteq C_2</tex> и <tex>C_2 \nsubseteq C_1</tex>; <br/> | 2) Если <tex>C_1, C_2 \in Ccl</tex> и <tex>C_1 \ne C_2</tex>, то <tex>C_1 \nsubseteq C_2</tex> и <tex>C_2 \nsubseteq C_1</tex>; <br/> | ||
3) Если <tex>C_1, C_2 \in Ccl, C_1 \ne C_2</tex> и <tex>p \in C_1 \cap C_2</tex>, то существует <tex>C \in Ccl</tex> такой, что <tex>C \subseteq (C_1 \cup C_2) \setminus p.</tex> | 3) Если <tex>C_1, C_2 \in Ccl, C_1 \ne C_2</tex> и <tex>p \in C_1 \cap C_2</tex>, то существует <tex>C \in Ccl</tex> такой, что <tex>C \subseteq (C_1 \cup C_2) \setminus p.</tex> | ||
|proof= | |proof= | ||
| − | 1) Из [[Определение матроида|определения матроида]] (первой аксиомы) <tex>\varnothing \in I</tex>, где <tex>I</tex> | + | 1) Из [[Определение матроида|определения матроида]] (первой аксиомы) <tex>\varnothing \in I</tex>, где <tex>I</tex> {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin Ccl</tex>. <br/> |
2) От противного. Из определения цикла: если <tex>C_1 \subset C_2</tex>, то <tex>C_1 \in I</tex>. Значит <tex>C_1 \notin Ccl</tex>. Противоречие. Аналогично <tex>C_2 \nsubseteq C_1</tex>. <br/> | 2) От противного. Из определения цикла: если <tex>C_1 \subset C_2</tex>, то <tex>C_1 \in I</tex>. Значит <tex>C_1 \notin Ccl</tex>. Противоречие. Аналогично <tex>C_2 \nsubseteq C_1</tex>. <br/> | ||
3) От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</tex> независимо.<br/> | 3) От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</tex> независимо.<br/> | ||
Обозначим <tex>A = C_1 \cap C_2</tex>. Покажем, что <tex>|A| < |D|</tex>. Из предыдущего пункта очевидным образом следует, что <tex>|C_1 \setminus C_2| > 0</tex> и <tex>|C_2 \setminus C_1| > 0</tex>. | Обозначим <tex>A = C_1 \cap C_2</tex>. Покажем, что <tex>|A| < |D|</tex>. Из предыдущего пункта очевидным образом следует, что <tex>|C_1 \setminus C_2| > 0</tex> и <tex>|C_2 \setminus C_1| > 0</tex>. | ||
| − | <tex>|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \ge |A| + 1 + 1 - 1 = |A| + 1 > |A|</tex> | + | <tex>|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \ge |A| + 1 + 1 - 1 = |A| + 1 > |A|</tex><br/> |
| + | Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо. <br/> | ||
| + | Поскольку <tex>C_1</tex> {{---}} цикл, <tex>C_1 \nsubseteq B</tex>. Значит, найдется хотя бы один элемент в <tex>C_1 \setminus A</tex>, не лежащий в <tex>B</tex>. Значит в <tex>B</tex> лежит не более чем <tex>|C_1 \setminus A| - 1</tex> элементов из этого множества. Аналогично в <tex>B</tex> лежит не более чем <tex>|C_2 \setminus A| - 1</tex> элементов из множества <tex>C_2 \setminus A</tex>. <br/> | ||
| + | Получаем: <tex>|B| \le |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1</tex>. А поскольку <tex>|B| = |D|</tex> получаем противоречие. | ||
}} | }} | ||
Версия 07:11, 17 мая 2011
| Теорема (о циклах): |
Пусть — матроид и — семейство его циклов. Тогда: 1) ; |
| Доказательство: |
|
1) Из определения матроида (первой аксиомы) , где — семейство независимых множеств матроида . Откуда . |
