Теорема о циклах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Циклом''' в матроиде называется множество, не являющееся независимым, каждое подмножество которого является независимым.  
+
'''Циклом''' (англ. '''circuit''') в матроиде называется множество, не являющееся независимым, каждое подмножество которого является независимым.  
 
}}
 
}}
  
Строка 8: Строка 8:
 
о циклах
 
о циклах
 
|statement=  
 
|statement=  
−
Пусть <tex>M</tex> {{---}} матроид и <tex>Ccl</tex> {{---}} семейство его циклов. Тогда: <br/>
+
Пусть <tex>M</tex> {{---}} матроид и <tex>\mathfrak{C}</tex> {{---}} семейство его циклов. Тогда:
−
1) <tex>\varnothing \notin Ccl</tex>; <br/>
+
# <tex>\varnothing \notin \mathfrak{C}</tex>
−
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/>
+
# Если <tex>C_1, C_2 \in \mathfrak{C}</tex> и <tex>C_1 \ne C_2</tex>, то <tex>C_1 \nsubseteq C_2</tex> и <tex>C_2 \nsubseteq C_1</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>
+
# Если <tex>C_1, C_2 \in \mathfrak{C}, C_1 \ne C_2</tex> и <tex>p \in C_1 \cap C_2</tex>, то существует <tex>C \in \mathfrak{C}</tex> такой, что <tex>C \subseteq (C_1 \cup C_2) \setminus p.</tex>
 
|proof=
 
|proof=
−
1) Из [[Определение матроида|определения матроида]] (первой аксиомы) <tex>\varnothing \in I</tex>, где <tex>I</tex> {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin Ccl</tex>. <br/>
+
# Из [[Определение матроида|определения матроида]] (первой аксиомы) <tex>\varnothing \in I</tex>, где <tex>I</tex> {{---}} семейство независимых множеств матроида <tex>M</tex>. Откуда <tex>\varnothing \notin \mathfrak{C}</tex>.  
−
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/>
+
# От противного. Из определения цикла: если <tex>C_1 \subset C_2</tex>, то <tex>C_1 \in I</tex>. Значит <tex>C_1 \notin \mathfrak{C}</tex>. Противоречие. Аналогично <tex>C_2 \nsubseteq C_1</tex>.  
−
3) От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</tex> независимо.<br/>
+
# От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</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>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><br/>
+
#: <tex>|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \ge |A| + 1 + 1 - 1 = |A| + 1 > |A|.</tex>
−
Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо. <br/>
+
#: Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо.  
−
Поскольку <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>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>.  
−
Получаем: <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> получаем противоречие.  
+
#: Получаем: <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> получаем противоречие.  
 
}}
 
}}
  
 +
== Источники информации ==
 +
* [[wikipedia:en:Matroid#Bases_and_circuits | Wikipedia {{---}} Matroid]]
 +
* [[wikipedia:ru:Матроид#Аксиоматическое определение | Википедия {{---}} Матроид]]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]

Версия 23:27, 5 июня 2014

Определение:
Циклом (англ. 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 \ge |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| \le |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]

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_циклах&oldid=37699»