Графы-экспандеры - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:29:40Z

rollbackEdits.php mass rollback

80.82.78.13 в 04:40, 1 сентября 2022

2022-09-01T04:40:35Z

Stelnov: /* Теорема о паросочетаниях */

2017-12-22T15:39:08Z

‎Теорема о паросочетаниях

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

2017-12-22T15:32:30Z

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

Stelnov: /* Маргулис-Габбер-Галил */

2017-12-22T15:30:37Z

‎Маргулис-Габбер-Галил

Stelnov: /* Маргулис-Габбер-Галил */

2017-12-22T15:08:40Z

‎Маргулис-Габбер-Галил

Stelnov в 15:05, 22 декабря 2017

2017-12-22T15:05:01Z

Stelnov: /* Двудольный экспандер */

2017-12-22T15:00:17Z

‎Двудольный экспандер

Stelnov в 14:53, 22 декабря 2017

2017-12-22T14:53:14Z

Внесённые изменения

Stelnov в 14:31, 22 декабря 2017

2017-12-22T14:31:44Z

← Предыдущая		Версия 16:29, 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 Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 04:40, 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 Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

@@ Строка 130: / Строка 130: @@
 Рассмотрим два случая:
+# <tex>\forall S: S \supseteq L, |S| \neq 0</tex> строго расширяется, то есть <tex>|\Gamma(S)| > |S|</tex>. Выберем <tex>\forall x: x \supset V(L) : (x, y) \in E</tex>. Тогда рассмотрим двудольный граф <tex>G^{*}</tex>, у которого левая доля <tex>L^{*} = L \diagdown {x}</tex>, а правая <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S: S \supset L</tex> удовлетворяет строгому неравенству теоремы, то каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, поскольку только одна вершина <tex>y</tex> была удалена из <tex>R</tex>. Следовательно, по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро (x, y) что дает совершенное паросочетание.
-. <tex>\forall S: S \supseteq L, |S| \neq 0</tex> строго расширяется, то есть <tex>|\Gamma(S)| > |S|</tex>.
+# Пусть <tex>\exists\ T \in L, \ |T| \neq 0</tex> такое, что <tex>|\Gamma(T)| = |T|</tex>. Рассмотрим порожденные графы <tex>G_{1} = T \cup \Gamma(T)</tex> и <tex>G_{2} = L \diagdown T \cup R \diagdown \Gamma(T)</tex>. По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использовано непосредственно на <tex>G_{2}</tex>). Пусть <tex>S \supseteq L \diagdown T</tex>, тогда: <tex>\Gamma_{G_{2}}(S) = \Gamma_{G}(S \cup T) \diagdown \Gamma_{G}(T) \ \Rightarrow</tex> <tex>|\Gamma_{G_{2}}| \geqslant |S \cup T| - |T| = |S|</tex> Неравенство верно, поскольку <tex>S \cup T</tex> удовлетворяет <tex>|\Gamma_{G}(S \cup T)| \geqslant |S \cup T|</tex> и по предположению <tex>|\Gamma_{G}(T)| = |T|</tex>. Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.
 }}

@@ Строка 263: / Строка 263: @@
 *[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%B0%D0%BD%D0%B4%D0%B5%D1%80_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) Экспандер (теория графов)]
 *[https://compsciclub.ru/courses/expanders/2017-spring/classes/ Экспандеры и их применения (курс CS club)]
 *[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf Экспандеры: конструкции и приложения]
 *[https://www.mccme.ru/~anromash/courses/expanders2009.pdf Определения и несколько примеров применений]

@@ Строка 175: / Строка 175: @@
 Существуют три основные стратегии создания семейств графов расширений. Первая стратегия {{---}} алгебраическая и теоретико {{---}} групповая, вторая {{---}} аналитическая, использующая аддитивную комбинаторику, и третья {{---}} комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
 ===Маргулис-Габбер-Галил===
-[[Алгебра|Алгебраическое]] конструирование, основанное на графах Кэли<ref>[[wikipedia:Cayley_graph|Wikipedia {{---}} граф Кэли]]</ref>, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером и Галилом <ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref>. Для любого натурального <tex>n</tex> строим граф, <tex>G_{n}</tex> со множеством вершин <tex>\mathbb Z _{n}\times \mathbb {Z} _{n}</tex>, где <tex>\mathbb {Z} _{n}=\cfrac{\mathbb Z}{n \mathbb Z}</tex> . Для любой вершины <tex>(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будут
+[[Алгебра|Алгебраическое]] конструирование, основанное на графах Кэли<ref>[[wikipedia:Cayley_graph|Wikipedia {{---}} граф Кэли]]</ref>, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером и Галилом <ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref>.
 <tex>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</tex>
 Выполняется следующая теорема:

@@ Строка 107: / Строка 107: @@
 <tex>\sum\limits_{s = 1}^{k}
 \bigg[\cfrac{ne}{s} \cdot
-\bigg(\cfrac{e^{(1 - \epsilon)/\epsilon} \cdot
+\bigg(\cfrac{e^{\tfrac{1 - \epsilon}{\epsilon}} \cdot
 (1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigg]^{s}
 </tex>.
-Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leqslant \cfrac{1}{2}</tex>. Тогда выражение в квадратных скобках не превосходит <tex>\cfrac{ne}{2 ^ {\epsilon d}}</tex>. Остаётся выбрать <tex>d > \cfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем <tex>\cfrac{ne}{2^{\epsilon d}} < \cfrac{1}{2}</tex>.
+Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{\tfrac{1 - \epsilon}{\epsilon}} \cdot (1 - \epsilon)sd}{m} \leqslant \cfrac{1}{2}</tex>. Тогда выражение в квадратных скобках не превосходит <tex>\cfrac{ne}{2 ^ {\epsilon d}}</tex>. Остаётся выбрать <tex>d > \cfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем <tex>\cfrac{ne}{2^{\epsilon d}} < \cfrac{1}{2}</tex>.
 Таким образом, для выбранных значений параметров сумм не превосходят <tex>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>.

@@ Строка 34: / Строка 34: @@
 |definition=
 '''Однородный (комбинаторный) экспандер''' (англ. ''combinatorial expander'') называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d {{---}} степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие:
-для <tex>\ \forall S: S \subseteq V, \ |S| \leq \cfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
+для <tex>\ \forall S: S \subseteq V, \ |S| \leqslant \cfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
 }}
 '''Замечание:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.
@@ Строка 47: / Строка 47: @@
 Зафиксируем некоторые множества вершин <tex>S</tex> и <tex>T</tex>. Зафиксируем номер перестановки <tex>\pi_{i}</tex>. Вероятность того, что для каждой вершины <tex>v \in S</tex> второй конец ребра {<tex>v, pi_{i}(v)</tex>} попадёт в <tex>T</tex>, равна
-<tex>\cfrac{|T|}{n} \cdot \cfrac{|T| - 1}{n - 1} \cdot \ldots \cdot \cfrac{|T| - |S| + 1}{n - |S| + 1} \leq \bigg(\cfrac{|T|}{n}\bigg)^{|S|}</tex>.
+<tex>\cfrac{|T|}{n} \cdot \cfrac{|T| - 1}{n - 1} \cdot \ldots \cdot \cfrac{|T| - |S| + 1}{n - |S| + 1} \leqslant \bigg(\cfrac{|T|}{n}\bigg)^{|S|}</tex>.
 Поскольку мы выбираем <tex>\cfrac{d}{2}</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>\bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>.