Теорема о циклах

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Циклом (англ. circuit) в матроиде называется множество, не являющееся независимым, каждое подмножество которого является независимым.


Теорема (о циклах):
Пусть [math]M[/math] — матроид и [math]\mathfrak{C}[/math] — семейство его циклов. Тогда:
  1. [math]\varnothing \notin \mathfrak{C}[/math]
  2. Если [math]C_1, C_2 \in \mathfrak{C}[/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 \mathfrak{C}, C_1 \ne C_2[/math] и [math]p \in C_1 \cap C_2[/math], то существует [math]C \in \mathfrak{C}[/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 \mathfrak{C}[/math].
  2. От противного. Из определения цикла: если [math]C_1 \subset C_2[/math], то [math]C_1 \in I[/math]. Значит [math]C_1 \notin \mathfrak{C}[/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 \geqslant |A| + 1 + 1 - 1 = |A| + 1 \gt |A|.[/math]
    Отсюда путем многократного применения третьей аксиомы матроидов получим [math]\exists B: A \subset B[/math] и [math]|B| = |D|[/math], причем [math]B[/math] — независимо.
    Поскольку [math]C_1[/math] — цикл, [math]C_1 \nsubseteq B[/math]. Значит, найдется хотя бы один элемент в [math]C_1 \setminus A[/math], не лежащий в [math]B[/math]. Следовательно в [math]B[/math] лежит не более чем [math]|C_1 \setminus A| - 1[/math] элементов из этого множества. Аналогично в [math]B[/math] лежит не более чем [math]|C_2 \setminus A| - 1[/math] элементов из множества [math]C_2 \setminus A[/math] .
    Получаем: [math]|B| \leqslant |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1[/math] . А поскольку [math]|B| = |D|[/math] получаем противоречие.
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]