Теорема о базах - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:15:04Z

rollbackEdits.php mass rollback

185.220.102.8 в 05:51, 1 сентября 2022

2022-09-01T05:51:15Z

Daviondk: Исправил русскую "С" на

2018-12-20T15:49:57Z

Исправил русскую "С" на

217.118.78.124 в 10:27, 13 декабря 2018

2018-12-13T10:27:58Z

Flyingleafe: Убрал все ненужные леммы

2015-06-16T14:32:56Z

Убрал все ненужные леммы

Flyingleafe: /* Источники информации */

2015-06-15T16:53:26Z

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

Flyingleafe в 15:31, 15 июня 2015

2015-06-15T15:31:10Z

Flyingleafe: Сильная теорема о базах дописана

2015-06-15T15:20:18Z

Сильная теорема о базах дописана

Flyingleafe: Лемма о циклах

2015-06-15T11:41:19Z

Лемма о циклах

Flyingleafe в 21:04, 11 июня 2015

2015-06-11T21:04:20Z

← Предыдущая		Версия 16:15, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|id=definition		\|id=definition

← Предыдущая		Версия 05:51, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|id=definition		\|id=definition

@@ Строка 46: / Строка 46: @@
 Значит, <tex>y \in B_2 \setminus B_1</tex>, что и требовалось.
-Докажем теперь, что <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. Пусть это не так, тогда <tex>\exists C'</tex> - цикл, <tex>C \subseteq (B_2 \setminus y) \cup x</tex>, причем <tex>С' \ne C</tex>, ведь <tex>y \in C</tex>. Но мы уже установили, что <tex>C</tex> {{---}} единственный цикл в <tex>B_2 \cup x</tex> {{---}} противоречие. Значит, <tex>(B_2 \setminus y) \cup x</tex> {{---}} база.
+Докажем теперь, что <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. Пусть это не так, тогда <tex>\exists C'</tex> - цикл, <tex>C \subseteq (B_2 \setminus y) \cup x</tex>, причем <tex>C' \ne C</tex>, ведь <tex>y \in C</tex>. Но мы уже установили, что <tex>C</tex> {{---}} единственный цикл в <tex>B_2 \cup x</tex> {{---}} противоречие. Значит, <tex>(B_2 \setminus y) \cup x</tex> {{---}} база.
 }}

@@ Строка 51: / Строка 51: @@
 == См. также ==
 * [[Аксиоматизация матроида базами]]
 == Источники информации ==

@@ Строка 28: / Строка 28: @@
 # Из теоремы о равномощности баз следует, что <tex>\neg (B_1 \subset B_2)</tex> и <tex>\neg (B_2 \subset B_1)</tex>. А с условием <tex>B_1 \ne B_2</tex> получаем <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>. <br>
 # По второй аксиоме [[Определение матроида|определения матроида]] <tex>\forall b_1 \in B_1</tex> верно, что <tex>(B_1 \setminus b_1) \in I</tex>. <br>По теореме о равномощности баз <tex>|B_2|>|B_1 \setminus b_1|</tex>. <br>Значит по третьей аксиоме [[Определение матроида|определения матроида]] <tex>\exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in I</tex>. <br>А так как <tex>|(B_1 \setminus b_1) \cup b_2| = |B_1| \:</tex>  и <tex>B_1</tex> — база, то <tex>(B_1 \setminus b_1) \cup b_2 \in \mathcal{B}</tex>, что и требовалось доказать.
 }}
@@ Строка 67: / Строка 37: @@
 такой, что <tex>(B_1 \setminus x) \cup y \in \mathcal{B}</tex> и <tex>(B_2 \setminus y) \cup x \in \mathcal{B}</tex>
 |proof=
-Рассмотрим <tex>x \in B_1 \setminus B_2</tex>. Так как <tex>B_2</tex> - база, <tex>B_2 \cup x \notin I</tex>, а значит, по лемме, <tex>\exists ! \ C</tex> - цикл,  <tex>C \subseteq B_2 \sup x</tex>, причем <tex>x \in C</tex>.<br>
+Рассмотрим <tex>x \in B_1 \setminus B_2</tex>. Так как <tex>B_2</tex> - база, <tex>B_2 \cup x \notin I</tex>, а значит, <tex>\exists ! \ C</tex> - цикл,  <tex>C \subseteq B_2 \cup x</tex>, причем <tex>x \in C</tex>. (см. пункт 3 [[Двойственный_матроид|теоремы о двойственном матроиде]])<br>
 Так как <tex>C</tex> {{---}} цикл, <tex>r(C) = r(C \setminus x)</tex>, а значит, <tex>x \in \langle C \setminus x \rangle</tex>.<br>
-<tex>C \setminus x \subseteq (B_1 \cup C) \setminus x</tex>, так что по пункту 1 леммы о замыкании: <tex>x \in \langle (B_1 \cap C) \setminus x \rangle</tex>.<br>
+<tex>C \setminus x \subseteq (B_1 \cup C) \setminus x</tex>, так что по 1 свойству [[Оператор замыкания для матроидов|оператора замыкания]]: <tex>x \in \langle (B_1 \cap C) \setminus x \rangle</tex>.<br>
-Тогда по пункту 2 той же леммы имеем: <tex>\langle (B_1 \cap C) \setminus x \rangle = \langle B_1 \cap C \setminus x \rangle = X</tex> (т. к. <tex>B_1</tex> - база).<br>
+Тогда по 3 свойству [[Оператор замыкания для матроидов|оператора замыкания]] имеем: <tex>\langle (B_1 \cap C) \setminus x \rangle = \langle B_1 \cap C \setminus x \rangle = X</tex> (т. к. <tex>B_1</tex> - база).<br>
 Из этого следует, что <tex>\exists B'</tex> {{---}} база, такая, что <tex>B' \subseteq (B \cap C) \setminus x</tex>.<br>
 Множество <tex>B_1 \setminus x </tex> независимо, и <tex>|B_1 \setminus x| < |B'|</tex>, a значит (по 3 аксиоме матроидов): <tex>\exists y \in B' \setminus (B_1 \setminus x) : (B_1 \setminus x) \cup y \in \mathcal{B}</tex>.<br>
@@ Строка 76: / Строка 46: @@
 Значит, <tex>y \in B_2 \setminus B_1</tex>, что и требовалось.
-Докажем теперь, что <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. Это следует из пункта 2 леммы 2: <tex>y \in C \subseteq B_2 \cup x, \; B_2 \cup x \notin I \Rightarrow (B_2 \setminus y) \cup x \in I</tex>, а значит {{---}} база.
+Докажем теперь, что <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. Пусть это не так, тогда <tex>\exists C'</tex> - цикл, <tex>C \subseteq (B_2 \setminus y) \cup x</tex>, причем <tex>С' \ne C</tex>, ведь <tex>y \in C</tex>. Но мы уже установили, что <tex>C</tex> {{---}} единственный цикл в <tex>B_2 \cup x</tex> {{---}} противоречие. Значит, <tex>(B_2 \setminus y) \cup x</tex> {{---}} база.
 }}

@@ Строка 85: / Строка 85: @@
 * [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf Chandra Chekuri: Combinatorial Optimization, Lecture 14 - Introduction to Matroids]
 * [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture16.pdf Chandra Chekuri: Combinatorial Optimization, Lecture 16 - Base Exchange Properties]
 [[Категория:Алгоритмы и структуры данных]]
 [[Категория:Матроиды]]

@@ Строка 21: / Строка 21: @@
 о базах
 |statement= Пусть <tex>M</tex> — матроид и <tex>\mathcal{B}</tex> — семейство его баз. Тогда: <br>
-) <tex>\mathcal{B} \ne \varnothing</tex>; <br>
+# <tex>\mathcal{B} \ne \varnothing</tex>; <br>
-) если <tex>B_1, B_2 \in \mathcal{B}</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>;<br>
+# если <tex>B_1, B_2 \in \mathcal{B}</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>;<br>
-) если <tex>B_1, B_2 \in \mathcal{B}</tex>, то для <tex>\forall b_1 \in B_1 \: \exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in \mathcal{B}</tex>.
+# если <tex>B_1, B_2 \in \mathcal{B}</tex>, то для <tex>\forall b_1 \in B_1 \: \exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in \mathcal{B}</tex>.
 |proof=
-) Следует из первой аксиомы [[Определение матроида|определения матроида]]. <br>
+# Следует из первой аксиомы [[Определение матроида|определения матроида]]. <br>
-) Из теоремы о равномощности баз следует, что <tex>\neg (B_1 \subset B_2)</tex> и <tex>\neg (B_2 \subset B_1)</tex>.
+# Из теоремы о равномощности баз следует, что <tex>\neg (B_1 \subset B_2)</tex> и <tex>\neg (B_2 \subset B_1)</tex>. А с условием <tex>B_1 \ne B_2</tex> получаем <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>. <br>
-А с условием <tex>B_1 \ne B_2</tex> получаем <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>. <br>
+# По второй аксиоме [[Определение матроида|определения матроида]] <tex>\forall b_1 \in B_1</tex> верно, что <tex>(B_1 \setminus b_1) \in I</tex>. <br>По теореме о равномощности баз <tex>|B_2|>|B_1 \setminus b_1|</tex>. <br>Значит по третьей аксиоме [[Определение матроида|определения матроида]] <tex>\exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in I</tex>. <br>А так как <tex>|(B_1 \setminus b_1) \cup b_2| = |B_1| \:</tex>  и <tex>B_1</tex> — база, то <tex>(B_1 \setminus b_1) \cup b_2 \in \mathcal{B}</tex>, что и требовалось доказать.
 }}
 Для доказательства сильной теоремы о базах нам понадобится альтернативное определение оператора замыкания.
 {{Определение
 |definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Тогда '''замыкание''' (англ. ''closure'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex>\langle A \rangle \subseteq X</tex> такое, что <tex>\langle A \rangle = \mathcal {f} x \in X \; |\; r(A \cup x) = r(A) \mathcal {g}</tex>, где <tex>r: 2^X \to \mathbb{N}</tex> - [[Ранговая_функция,_полумодулярность|ранговая функция]]
@@ Строка 44: / Строка 41: @@
 |about=о свойствах замыкания
 |statement=
-) Если <tex>A \subseteq B</tex>, то <tex>\langle A \rangle \subseteq \langle B \rangle</tex> <br>
+. Если <tex>A \subseteq B</tex>, то <tex>\langle A \rangle \subseteq \langle B \rangle</tex><br>
-) Если <tex>e \in \langle A \rangle</tex>, то <tex>\langle A \cup e \rangle = \langle A \rangle</tex>
+. Если <tex>e \in \langle A \rangle</tex>, то <tex>\langle A \cup e \rangle = \langle A \rangle</tex>
 |proof=
-) Рассмотрим <tex>e \in \langle A \rangle</tex>. По полумодулярности ранговой функции имеем:
+# Рассмотрим <tex>e \in \langle A \rangle</tex>. По полумодулярности ранговой функции имеем: <br> <tex>r(A \cup e) + r(B) \geqslant r((A \cup e) \cap B) + r(B \cup e) \geqslant r(A) + r(B \cup e)</tex>. <br> По определению замыкания, <tex>r(A \cup e) = r(A)</tex>, следовательно, <tex>r(B) \geqslant r(B \cup e)</tex>, но <tex>r(B \cup e) \geqslant r(B)</tex> (по определению ранговой функции), значит, <br><tex>r(B) = r(B \cup e)</tex>, что, в свою очередь, значит, что <tex>e \in \langle B \rangle</tex>.<br> В силу произвольности <tex>e: \langle A \rangle \subseteq \langle B \rangle</tex>.
+# По пункту 1 очевидно, что <tex>\langle A \rangle \subseteq \langle A \cup e \rangle</tex>. Докажем обратное: <tex>\langle A  \cup e \rangle \subseteq \langle A \rangle</tex>.<br>Рассмотрим <tex>f \in \langle A \cup e \rangle</tex>. По полумодулярности ранговой функции имеем: <br><tex>r(A \cup e) + r(A \cup f) \geqslant r(A \cup e \cup f) + r((A \cup e) \cap (A \cup f)) \geqslant r(A \cup e \cup f) + r(A)</tex>.<br>Но  <tex>r(A \cup e) = r(A)</tex> (так как <tex>e \in \langle A \rangle</tex>), значит, <tex>r(A \cup f) \geqslant r(A \cup e \cup f)</tex>, что в свою очередь влечет <tex>r(A \cup f) = r(A \cup e \cup f)</tex>.<br>Но так как <tex>f \in  \langle A \cup e \rangle</tex> и <tex>e \in \langle A \rangle</tex>, <tex>r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)</tex>.<br>Следовательно, по определению, <tex>f \in \langle A \rangle</tex>. <br>В силу произвольности <tex>f: \langle A \cup e \rangle \subseteq \langle A \rangle</tex>.
 }}
@@ Строка 70: / Строка 53: @@
 |statement=
 Пусть <tex>M = \langle X, I \rangle</tex> — матроид, <tex>A \in I, a \notin A, A \cup a \notin I</tex>. Тогда: <br>
-) <tex>\exists ! \ C \subseteq A \cup a</tex> — цикл <br>
+# <tex>\exists ! \ C \subseteq A \cup a</tex> — цикл <br>
-) <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
+# <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
 |proof=
-) Докажем единственность. <br>
+# Докажем единственность. <br>Так как <tex>A \cup a \notin I</tex>, найдется цикл <tex>C_1 \subseteq A \cup a</tex>. Пусть существует и другой цикл <tex>C_2 \subseteq A \cup a, C_2 \neq C_1</tex>. <br>Тогда, так как <tex>A \in I</tex>, <tex> a \in C_1</tex> и <tex>a \in C_2</tex>. Из [[Теорема о циклах|теоремы о циклах]] заключаем, что в таком случае <tex>\exists C</tex> - цикл, <tex>C \subseteq C_1 \cap C_2 \setminus a</tex>. <br>Но это невозможно, так как <tex>C_1 \cap C_2 \setminus a \subseteq A \in I</tex>, следовательно, предположение неверно, и <tex>C_2 = C_1</tex>.
-Так как <tex>A \cup a \notin I</tex>, найдется цикл <tex>C_1 \subseteq A \cup a</tex>. Пусть существует и другой цикл <tex>C_2 \subseteq A \cup a, C_2 \neq C_1</tex>. <br>
+# Пусть <tex>\exists b \in C</tex>, такой, что <tex>(A \cup a) \setminus b \notin I</tex>. Значит, <tex>(A \cup a) \setminus b</tex> содержит цикл <tex>C' \neq C</tex>. <br> Но тогда его содержит и <tex>A \cup a</tex>, что противоречит пункту 1 леммы. Следовательно, <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
 }}
@@ Строка 90: / Строка 69: @@
 Рассмотрим <tex>x \in B_1 \setminus B_2</tex>. Так как <tex>B_2</tex> - база, <tex>B_2 \cup x \notin I</tex>, а значит, по лемме, <tex>\exists ! \ C</tex> - цикл,  <tex>C \subseteq B_2 \sup x</tex>, причем <tex>x \in C</tex>.<br>
 Так как <tex>C</tex> {{---}} цикл, <tex>r(C) = r(C \setminus x)</tex>, а значит, <tex>x \in \langle C \setminus x \rangle</tex>.<br>
-<tex>С \setminus x \subseteq (B_1 \cup C) \setminus x</tex>, так что по пункту 1 леммы о замыкании: <tex>x \in \langle (B_1 \cap C) \setminus x \rangle</tex>.<br>
+<tex>C \setminus x \subseteq (B_1 \cup C) \setminus x</tex>, так что по пункту 1 леммы о замыкании: <tex>x \in \langle (B_1 \cap C) \setminus x \rangle</tex>.<br>
 Тогда по пункту 2 той же леммы имеем: <tex>\langle (B_1 \cap C) \setminus x \rangle = \langle B_1 \cap C \setminus x \rangle = X</tex> (т. к. <tex>B_1</tex> - база).<br>
 Из этого следует, что <tex>\exists B'</tex> {{---}} база, такая, что <tex>B' \subseteq (B \cap C) \setminus x</tex>.<br>

@@ Строка 32: / Строка 32: @@
 Значит по третьей аксиоме [[Определение матроида|определения матроида]] <tex>\exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in I</tex>. <br>
 А так как <tex>|(B_1 \setminus b_1) \cup b_2| = |B_1| \:</tex>  и <tex>B_1</tex> — база, то <tex>(B_1 \setminus b_1) \cup b_2 \in \mathcal{B}</tex>, что и требовалось доказать.
 }}
 {{Лемма
 |id=lemma_1
 |statement=
 Пусть <tex>M = \langle X, I \rangle</tex> — матроид, <tex>A \in I, a \notin A, A \cup a \notin I</tex>. Тогда: <br>
-) <tex>\exists ! \ C \in A \cup a</tex> — цикл <br>
+) <tex>\exists ! \ C \subseteq A \cup a</tex> — цикл <br>
 ) <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
 |proof=
@@ Строка 53: / Строка 85: @@
 |about=
 Сильная теорема о базах
-|statement=  Пусть <tex>M</tex> — матроид и <tex>\mathcal{B}</tex> — семейство его баз. Тогда <tex>\forall B_1, B_2 \in \mathcal{B} : \forall x \in B_1 \setminus B_2 : \exists y \in B_2 \setminus B_1</tex>
+|statement=  Пусть <tex>M = \langle X, I \rangle</tex> — матроид и <tex>\mathcal{B}</tex> — семейство его баз. Тогда <tex>\forall B_1, B_2 \in \mathcal{B} : \forall x \in B_1 \setminus B_2 : \exists y \in B_2 \setminus B_1</tex>
 такой, что <tex>(B_1 \setminus x) \cup y \in \mathcal{B}</tex> и <tex>(B_2 \setminus y) \cup x \in \mathcal{B}</tex>
-|proof=TBD
+|proof=
 }}