Редактирование: Графы-экспандеры

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') {{---}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|граф]], при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность.  
+
Граф-экспандер (или расширяющийся граф, англ. ''expander graph'') {{---}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|граф]], при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность.  
 
}}
 
}}
  
Строка 9: Строка 9:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Множество соседей''' (англ. ''set of neighbors'') для множества вершин <tex>S</tex> называется <tex>\Gamma(S) = \{v: \exists w \in S:\ (v, w) \in E\}</tex>.
+
Множество соседей для множества вершин <tex>S</tex> называется <tex>\Gamma(S) = \{v: \exists w \in S:\ (v, w) \in E\}</tex>.
 
}}
 
}}
 
'''Замечание:''' в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\forall S: S \supseteq \Gamma(S)</tex>.
 
'''Замечание:''' в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\forall S: S \supseteq \Gamma(S)</tex>.
Строка 34: Строка 34:
 
|definition=
 
|definition=
 
'''Однородный (комбинаторный) экспандер''' (англ. ''combinatorial expander'') называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d {{---}} степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие:  
 
'''Однородный (комбинаторный) экспандер''' (англ. ''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| \leqslant \cfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
+
для <tex>\ \forall S: S \subseteq V, \ |S| \leq \tfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
 
}}
 
}}
 
'''Замечание:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.  
 
'''Замечание:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.  
Строка 43: Строка 43:
 
Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к <tex>1</tex>) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.
 
Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к <tex>1</tex>) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.
  
Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <tex>S</tex> (состоящее из не более, чем <tex>\cfrac{n}{2}</tex> вершин), все соседи которого лежат в некотором множестве <tex>T</tex>, состоящем из <tex>\lfloor (1 + \epsilon)|S|\rfloor</tex> вершин.
+
Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <tex>S</tex> (состоящее из не более, чем <tex>\tfrac{n}{2}</tex> вершин), все соседи которого лежат в некотором множестве <tex>T</tex>, состоящем из <tex>\lfloor (1 + \epsilon)|S|\rfloor</tex> вершин.
  
Зафиксируем некоторые множества вершин <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>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} \leqslant \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} \leq \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>.
+
Поскольку мы выбираем <tex>\tfrac{d}{2}</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>\bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>.
 
Таким образом,  
 
Таким образом,  
  
Вероятность, что свойство экспандерности графа нарушено небольше <tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>,
+
Вероятность, что свойство экспандерности графа нарушено <tex>\leq \sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>,
где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>\cfrac{n}{2}</tex> и по всем множествам <tex>T</tex> размера <tex>\lfloor(1 + \epsilon)|S|\rfloor</tex>.
+
где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>\tfrac{n}{2}</tex> и по всем множествам <tex>T</tex> размера <tex>\lfloor(1 + \epsilon)|S|\rfloor</tex>.
  
 
Оценим сумму:
 
Оценим сумму:
  
<tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}} \leqslant \sum\limits_{s = 1}^{\tfrac{n}{2}} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}}</tex>. <tex>(1)</tex>
+
<tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}} \leq \sum\limits_{s = 1}^{\tfrac{n}{2}} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}}</tex>. <tex>(1)</tex>
  
 
Каждый биномиальный коэффициент <tex>\dbinom{k}{n}</tex> можно оценить сверху величиной <tex>\bigg(\cfrac{ne}{k}\bigg)^{k}</tex>. Тогда
 
Каждый биномиальный коэффициент <tex>\dbinom{k}{n}</tex> можно оценить сверху величиной <tex>\bigg(\cfrac{ne}{k}\bigg)^{k}</tex>. Тогда
Строка 69: Строка 69:
 
<tex>\sum\limits_{s = 1}^{\tfrac{n}{2}} \bigg[\bigg(\cfrac{s}{n}\bigg)^{\tfrac{d}{2} - 2 - \epsilon} \cdot (1 + \epsilon)^{\tfrac{d}{2}} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s</tex>. <tex>(2)</tex>
 
<tex>\sum\limits_{s = 1}^{\tfrac{n}{2}} \bigg[\bigg(\cfrac{s}{n}\bigg)^{\tfrac{d}{2} - 2 - \epsilon} \cdot (1 + \epsilon)^{\tfrac{d}{2}} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s</tex>. <tex>(2)</tex>
  
Заметим, что <tex>s \leqslant \cfrac{n}{2}</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое
+
Заметим, что <tex>s \leq \tfrac{n}{2}</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое
<tex>d = d(\epsilon)</tex>, чтобы выражение в квадратных скобках в правой части <tex>(2)</tex> было меньше <tex>\cfrac{1}{2}</tex> при всех значениях <tex>\epsilon</tex>. Следовательно, сумма <tex>(1)</tex> меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами <tex>(n, d, \epsilon)</tex>.
+
<tex>d = d(\epsilon)</tex>, чтобы выражение в квадратных скобках в правой части <tex>(2)</tex> было меньше <tex>\tfrac{1}{2}</tex> при всех значениях <tex>\epsilon</tex>. Следовательно, сумма <tex>(1)</tex> меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами <tex>(n, d, \epsilon)</tex>.
 
}}
 
}}
  
Строка 76: Строка 76:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Двудольный экспандер''' (англ. ''Bipartite expander'') называется [[Двудольные графы|двудольный граф]] <tex>G = (L,\ R,\ E)\ (L</tex> и <tex>R</tex> {{---}} вершины левой и правой доли соответственно, <tex>E</tex> {{---}} ребра графа <tex>G</tex>) с параметрами <tex>(n,\ m,\ d,\ e)\ (n = |L|,\ m = |R|,\ d</tex> - степень всех вершин в левой доле), если выполняется условие: для <tex>\forall S: S \subseteq L \ |S| \leqslant k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
+
'''Двудольный экспандер''' называется [[Двудольные графы|двудольный граф]] <tex>G = (L,\ R,\ E)\ (L</tex> и <tex>R</tex> {{---}} вершины левой и правой доли соответственно, <tex>E</tex> {{---}} ребра графа <tex>G</tex>) с параметрами <tex>(n,\ m,\ d,\ e)\ (n = |L|,\ m = |R|,\ d</tex> - степень всех вершин в левой доле), если выполняется условие: для <tex>\forall S: S \subseteq L \ |S| \leq k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
 
}}
 
}}
 
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.  
 
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.  
  
'''Замечание 2:''' в приложениях как правило используют двудольные экспандеры с <tex>\epsilon < \cfrac{1}{2}</tex>, а для применения в теории кодирования (для построения экспандерных кодов) часто требуются двудольные экспандеры с ещё меньшими значениями <tex>\epsilon</tex>.
+
'''Замечание 2:''' в приложениях как правило используют двудольные экспандеры с <tex>\epsilon < \tfrac{1}{2}</tex>, а для применения в теории кодирования (для построения экспандерных кодов) часто требуются двудольные экспандеры с ещё меньшими значениями <tex>\epsilon</tex>.
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число. Тогда для <tex>\forall \ n</tex> и <tex>k \leqslant n</tex> найдется <tex>d = O(\log n)</tex> и <tex>m = O(dk)</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.
+
Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число. Тогда для <tex>\forall \ n</tex> и <tex>k \leq n</tex> найдется <tex>d = O(\log n)</tex> и <tex>m = O(dk)</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.
 
|proof=
 
|proof=
 
Выберем случайный граф, то есть для <tex>\forall \ v \in L</tex> случайно и независимо выбираем <tex>d</tex> соседей в <tex>R</tex> (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.  
 
Выберем случайный граф, то есть для <tex>\forall \ v \in L</tex> случайно и независимо выбираем <tex>d</tex> соседей в <tex>R</tex> (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.  
Строка 90: Строка 90:
 
Граф не является экспандером, если <tex>\exists T \subset R: \ |T| = (1 - \epsilon)d|S|</tex> и <tex>\exists S \subset L: \ \Gamma(S) = T</tex>.
 
Граф не является экспандером, если <tex>\exists T \subset R: \ |T| = (1 - \epsilon)d|S|</tex> и <tex>\exists S \subset L: \ \Gamma(S) = T</tex>.
  
Поскольку при случайном выборе графа мы приводим все <tex>nd</tex> рёбер случайно и независимо, то для <tex>\forall</tex> ребра вероятность того, что его правый конец окажется в фиксированном множестве <tex>T</tex>, равна <tex>\cfrac{|T|}{m}</tex>. Следовательно, вероятность, что свойство экспандерности графа нарушено <tex> \leqslant \ \sum\limits_{S, T}\bigg(\cfrac{|T|}{m}\bigg)^{sd}</tex>,  
+
Поскольку при случайном выборе графа мы приводим все <tex>nd</tex> рёбер случайно и независимо, то для <tex>\forall</tex> ребра вероятность того, что его правый конец окажется в фиксированном множестве <tex>T</tex>, равна <tex>\cfrac{|T|}{m}</tex>. Следовательно, вероятность, что свойство экспандерности графа нарушено <tex> \leq \ \sum\limits_{S, T}\bigg(\cfrac{|T|}{m}\bigg)^{sd}</tex>,  
  
где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leqslant k \ \forall T: T \subset R \ |T| = (1 - \epsilon)d|S| </tex>. Оценим данную сумму сверху:
+
где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leq k \ \forall T: T \subset R \ |T| = (1 - \epsilon)d|S| </tex>. Оценим данную сумму сверху:
  
 
<tex>\sum\limits_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}</tex>.
 
<tex>\sum\limits_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}</tex>.
Строка 103: Строка 103:
 
\bigg(\cfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot  
 
\bigg(\cfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot  
 
\bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}  
 
\bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}  
\leqslant </tex>
+
\leq </tex>
  
 
<tex>\sum\limits_{s = 1}^{k}  
 
<tex>\sum\limits_{s = 1}^{k}  
 
\bigg[\cfrac{ne}{s} \cdot  
 
\bigg[\cfrac{ne}{s} \cdot  
\bigg(\cfrac{e^{\tfrac{1 - \epsilon}{\epsilon}} \cdot  
+
\bigg(\cfrac{e^{(1 - \epsilon)/\epsilon} \cdot  
 
(1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigg]^{s}
 
(1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigg]^{s}
 
</tex>.
 
</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>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leq \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>.
 
Таким образом, для выбранных значений параметров сумм не превосходят <tex>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>.
Строка 117: Строка 117:
 
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
 
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
  
==== Теорема о паросочетаниях ====
+
==== теорема о Паросочетаниях ====
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
 
Пусть <tex>G</tex> {{---}} [[Двудольные графы|двудольный граф]].
 
Пусть <tex>G</tex> {{---}} [[Двудольные графы|двудольный граф]].
<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S: S \supseteq L \ |S| \leqslant \Gamma(S)</tex>.
+
<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S: S \supseteq L \ |S| \leq \Gamma(S)</tex>.
 
|proof=
 
|proof=
 
Будем доказывать по индукции
 
Будем доказывать по индукции
Строка 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>\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>.
+
1. <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) что дает совершенное паросочетание.
 +
 
 +
2. Пусть <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>.
 
}}
 
}}
  
Строка 153: Строка 168:
 
<tex>\lambda=\max\limits_{0\neq v\perp u} \cfrac{\|Av\|_2}{\|v\|_2},</tex>
 
<tex>\lambda=\max\limits_{0\neq v\perp u} \cfrac{\|Av\|_2}{\|v\|_2},</tex>
  
где <tex>\|v\|_2=\left(\sum\limits_{i=1}^{n} v_i^2\right)^{\tfrac{1}{2}}</tex> {{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
+
где
 +
 
 +
<tex>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{\tfrac{1}{2}}</tex>
 +
 
 +
{{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
  
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\cfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>(-1, 1)</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения <tex>A</tex>, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
+
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\frac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>-1</tex> и <tex>1</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения <tex>A</tex>, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</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>.  
+
[[Алгебра|Алгебраическое]] конструирование, основанное на графах Кэли<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}=\mathbb Z /n \mathbb Z</tex> . Для любой вершины <tex>(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будут
 
 
В качестве множества вершин графа возьмём <tex>V = \mathbb Z _{n}\times \mathbb {Z} _{n}</tex> (таким образом, граф будет содержать <tex>n^{2}</tex> вершин). Каждая вершина <tex>(x, y)</tex> из <tex>\mathbb Z _{n}\times \mathbb {Z} _{n}</tex> соединяется рёбрами со следующими восьмую вершинами:
 
  
 
<tex>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</tex>
 
<tex>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</tex>
 
(все арифметические вычисления производятся по модулю <tex>n</tex>). Таким образом, степень каждой вершины графа равна 8. При достаточно больших <tex>n</tex> в этом графе не будет кратных рёбер.
 
  
 
Выполняется следующая теорема:
 
Выполняется следующая теорема:
Строка 173: Строка 188:
 
<tex>\forall n</tex> граф <tex>G_{n}</tex> второе по величине собственное число удовлетворяет неравенству
 
<tex>\forall n</tex> граф <tex>G_{n}</tex> второе по величине собственное число удовлетворяет неравенству
  
<tex>\lambda(G)\leqslant 5 \sqrt{2}</tex>.
+
<tex>\lambda(G)\leq 5 \sqrt{2}</tex>.
 
}}
 
}}
  
Строка 179: Строка 194:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
[[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] называется графом Рамануджана, если его второе по модулю собственное число <tex> \lambda \leqslant 2\sqrt {d-1} - o(1)</tex>.
+
[[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] называется графом Рамануджана, если его второе по модулю собственное число <tex> \lambda \leq 2\sqrt {d-1} - o(1)</tex>.
 
}}
 
}}
  
'''Замечание:''' случайный [[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] с <tex>n</tex> вершинами почти является графом Рамануджана, так как выполняется неравенство <tex> \lambda \leqslant 2\sqrt {d-1} + \epsilon</tex> с вероятностью <tex>1 - o(1)</tex> при <tex>n \to \inf</tex>.
+
'''Замечание:''' случайный [[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] с <tex>n</tex> вершинами почти является графом Рамануджана, так как выполняется неравенство <tex> \lambda \leq 2\sqrt {d-1} + \epsilon</tex> с вероятностью <tex>1 - o(1)</tex> при <tex>n \to \inf</tex>.
  
 
==Примеры применения экспандеров==
 
==Примеры применения экспандеров==
 
===Коды, исправляющие ошибки===
 
===Коды, исправляющие ошибки===
С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле <tex>\delta = \cfrac{1}{2000d}</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in \{0, 1\}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, \ldots , x_n</tex> решения этой системы и будут кодовыми словами.
+
С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле <tex>\delta = \tfrac{1}{2000d}</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in \{0, 1\}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, \ldots , x_n</tex> решения этой системы и будут кодовыми словами.
  
 
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
 
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
Строка 199: Строка 214:
  
 
===Хранение множества со сверхбыстрым запросом элементов===
 
===Хранение множества со сверхбыстрым запросом элементов===
Мы организуем хранение m-элементного множества <tex>S \subset \{1, \ldots , n\}</tex> в виде описания <tex>X</tex>, состоящего из <tex>O(m log n)</tex> битов. При этом проверка принадлежности <tex>a \in S</tex> будет производиться чрезвычайно быстро. А именно, мы построим такой вероятностный алгоритм, который по любому входу <tex>a</tex> запрашивает из <tex>X</tex> один бит; если этот бит оказывается равным единице, то алгоритм отвечает, что <tex>a</tex> является элементом <tex>S</tex>; в противном случае алгоритм говорит, что <tex>a</tex> множеству не принадлежит. При этом для каждого <tex>a \in \{1, \ldots , n\}</tex> алгоритм ошибается с вероятностью не более <tex>\cfrac{1}{3}</tex>.
+
Мы организуем хранение m-элементного множества <tex>S \subset \{1, . . . , n\}</tex> в виде описания <tex>X</tex>, состоящего из <tex>O(m log n)</tex> битов. При этом проверка принадлежности <tex>a \in S</tex> будет производиться чрезвычайно быстро. А именно, мы построим такой вероятностный алгоритм, который по любому входу <tex>a</tex> запрашивает из <tex>X</tex> один бит; если этот бит оказывается равным единице, то алгоритм отвечает, что <tex>a</tex> является элементом <tex>S</tex>; в противном случае алгоритм говорит, что <tex>a</tex> множеству не принадлежит. При этом для каждого <tex>a \in \{1, . . . , n\}</tex> алгоритм ошибается с вероятностью не более <tex>1/3</tex>.
  
 
Чтобы построить нужное нам хранилище <tex>X</tex>, мы сначала зафиксируем некоторый экспандер, у которого левая доля <tex>L</tex> состоит из <tex>n</tex> вершин, правая <tex>R</tex> из <tex>k = O(m log n)</tex> вершин, степень всех вершин левой доли одинакова и равна некоторому <tex>d</tex>, и для каждого <tex>A \subset L</tex> размера не более <tex>2m</tex>  
 
Чтобы построить нужное нам хранилище <tex>X</tex>, мы сначала зафиксируем некоторый экспандер, у которого левая доля <tex>L</tex> состоит из <tex>n</tex> вершин, правая <tex>R</tex> из <tex>k = O(m log n)</tex> вершин, степень всех вершин левой доли одинакова и равна некоторому <tex>d</tex>, и для каждого <tex>A \subset L</tex> размера не более <tex>2m</tex>  
  
<tex>|\Gamma(A)| \geqslant \cfrac{7d|A|}{8}</tex>
+
<tex>|\Gamma(A)| \geqslant \frac{7}{8}d|A|</tex>
  
<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены нулями. <tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены нулями.
+
<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены нулями.<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены нулями.
  
Остаётся объяснить, как построить нужную нам разметку правой доли графа. Будем строить её последовательными приближениями. Сначала пометим всех соседей всех вершин из <tex>S</tex> единицами, а все остальные вершины – нулями. На данной разметке наш алгоритм с вероятностью <tex>1</tex> возвращает правильный ответ для всех <tex>a \in S</tex>. Однако для <tex>a</tex> не из <tex>S</tex> проверочный алгоритм может работать неверно. Обозначим T множество всех таких вершин вне <tex>S</tex>, у которых более <tex>\cfrac{d}{3}</tex> соседей помечены единицей. Поменяем разметку: пометим всех соседей <tex>T</tex> нулём. Теперь разметка может стать плохой для части вершин из <tex>S</tex>. Обозначим <tex>S'</tex> множество всех таких вершин из <tex>S</tex>, у которых более <tex>\cfrac{d}{3}</tex> соседей помечены нулями. Далее, поменяем разметку у
+
Остаётся объяснить, как построить нужную нам разметку правой доли графа. Будем строить её последовательными приближениями. Сначала пометим всех соседей всех вершин из <tex>S</tex> единицами, а все остальные вершины – нулями. На данной разметке наш алгоритм с вероятностью <tex>1</tex> возвращает правильный ответ для всех <tex>a \in S</tex>. Однако для <tex>a</tex> не из <tex>S</tex> проверочный алгоритм может работать неверно. Обозначим T множество всех таких вершин вне <tex>S</tex>, у которых более <tex>d/3</tex> соседей помечены единицей. Поменяем разметку: пометим всех соседей <tex>T</tex> нулём. Теперь разметка может стать плохой для части вершин из <tex>S</tex>. Обозначим <tex>S'</tex> множество всех таких вершин из <tex>S</tex>, у которых более <tex>d/3</tex> соседей помечены нулями. Далее, поменяем разметку у
 
всех соседей <tex>S'</tex> на единицы. После этого может вновь возникнуть множество ‘неправильных’ вершин вне <tex>S</tex>, и т.д.
 
всех соседей <tex>S'</tex> на единицы. После этого может вновь возникнуть множество ‘неправильных’ вершин вне <tex>S</tex>, и т.д.
  
 
Чтобы доказать, что данный процесс в конце концов сойдётся, нужно показать, что на каждом шаге число ‘проблемных’ вершин уменьшается в константу раз. Поскольку все шаги аналогичны, достаточно разобрать самый первый: докажем, что <tex>T</tex> в константу раз меньше, чем <tex>S</tex>. Мы воспользуемся тем, что для <tex>S \cup T</tex> выполнено свойство расширения:
 
Чтобы доказать, что данный процесс в конце концов сойдётся, нужно показать, что на каждом шаге число ‘проблемных’ вершин уменьшается в константу раз. Поскольку все шаги аналогичны, достаточно разобрать самый первый: докажем, что <tex>T</tex> в константу раз меньше, чем <tex>S</tex>. Мы воспользуемся тем, что для <tex>S \cup T</tex> выполнено свойство расширения:
  
<tex>\cfrac{7d}{8}(|S|+|T|) \leqslant |\Gamma(S \cup T)| \leqslant d|S| + \cfrac{2d|T|}{3}</tex>
+
<tex>(7/8)d(|S|+|T|) \leqslant |\Gamma(S \cup T)| \leqslant d|S| + (2/3)d|T|</tex>
  
Откуда получаем <tex>|T| \leqslant \cfrac{3|S|}{5}</tex>.
+
Откуда получаем <tex>|T| \leqslant 3/5|S|</tex>.
  
 
==Приложения и полезные свойства==
 
==Приложения и полезные свойства==
 
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
 
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
  
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах<ref>[[wikipedia:Expander_code|Wikipedia {{---}} корректирующие коды]]</ref>, экстракторах, генераторах псевдослучайных чисел<ref>[[wikipedia:Pseudorandom_number_generator|Wikipedia {{---}} генератор псевдослучайных чисел]]</ref>, сетях сортировки<ref>[[wikipedia:Sorting_network|Wikipedia {{---}} Сеть сортировки]]</ref> и компьютерных сетях<ref>[[wikipedia:Computer_network|Wikipedia {{---}} компьютерные сети]]</ref>. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как ''SL''<ref>[[wikipedia:SL_(complexity)|Wikipedia {{---}} SL complexity]]</ref>=''L''<ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref> и [[PCP-теорема|Теорема PCP]]. В криптографии экспандеры используются для создания [[Универсальное семейство хеш-функций|хеш-функций]].
+
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах<ref>[[wikipedia:Expander_code|Wikipedia {{---}} корректирующие коды]]</ref>, экстракторах, генераторах псевдослучайных чисел<ref>[[wikipedia:Pseudorandom_number_generator|Wikipedia {{---}} генератор псевдослучайных чисел]]</ref>, сетях сортировки<ref>[[wikipedia:Sorting_network|Wikipedia {{---}} Сеть сортировки]]</ref> и компьютерных сетях<ref>[[wikipedia:Computer_network|Wikipedia {{---}} компьютерные сети]]</ref>. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как ''SL''<ref>[[wikipedia:SL_(complexity)|Wikipedia {{---}} SL complexity]]</ref>=''L''<ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref> и Теорема PCP<ref>Irit Dinur The PCP theorem by gap amplification // Journal of the ACM. — 2007. — Т. 54, вып. 3. — С. 12. — DOI:10.1145/1236457.1236459</ref>. В криптографии экспандеры используются для создания [[Универсальное семейство хеш-функций|хеш-функций]].
  
 
===Лемма о перемешивании===
 
===Лемма о перемешивании===
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <tex>S,T\subseteq V</tex> число рёбер между <tex>S</tex> и <tex>T</tex> примерно равно числу рёбер в случайном <tex>d</tex>-регулярном графе. Приближение тем лучше, чем меньше <tex>\lambda =\max\{|\lambda _{2}|</tex>,<tex>|\lambda _{n}|\}</tex>. В случайном <tex>d</tex>-регулярном графе, также как и в случайном графе Эрдёша — Реньи<ref>[[wikipedia:Erdős–Rényi model|Wikipedia {{---}} Erdős–Rényi model]]</ref> с вероятностью <tex>{\cfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\cfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S</tex> и <tex>T</tex>.
+
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <tex>S,T\subseteq V</tex> число рёбер между <tex>S</tex> и <tex>T</tex> примерно равно числу рёбер в случайном <tex>d</tex>-регулярном графе. Приближение тем лучше, чем меньше <tex>\lambda =\max\{|\lambda _{2}|</tex>,<tex>|\lambda _{n}|\}</tex>. В случайном <tex>d</tex>-регулярном графе, также как и в случайном графе Эрдёша — Реньи<ref>[[wikipedia:Erdős–Rényi model|Wikipedia {{---}} Erdős–Rényi model]]</ref> с вероятностью <tex>{\tfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\tfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S</tex> и <tex>T</tex>.
  
 
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
 
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
Строка 229: Строка 244:
 
Лемма о перемешивании утверждает, что
 
Лемма о перемешивании утверждает, что
  
<tex>\left|E(S,T)-{\cfrac {d\cdot |S|\cdot |T|}{n}}\right|\leqslant d\lambda {\sqrt {|S|\cdot |T|}}</tex>,
+
<tex>\left|E(S,T)-{\cfrac {d\cdot |S|\cdot |T|}{n}}\right|\leq d\lambda {\sqrt {|S|\cdot |T|}}</tex>,
 
где <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
 
где <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
  
Недавно Билу и Линайл показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(\tfrac{1}{\lambda})))</tex><ref>[[http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf|Lifts, discrepancy and nearly optimal spectral gap]]</ref>.
+
Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(1/\lambda )))</tex><ref>[[http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf|Lifts, discrepancy and nearly optimal spectral gap]]</ref>.
  
 
===Блуждания по экспандеру===
 
===Блуждания по экспандеру===
Строка 248: Строка 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://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://compsciclub.ru/courses/expanders/2017-spring/classes/ Экспандеры и их применения (курс CS club)]
*[https://compsciclub.ru/media/course_class_attachments/expanders-notes-spb-appendix.pdf Приложение к лекциям об экспандерах (CS club)]
 
 
*[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf Экспандеры: конструкции и приложения]
 
*[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf Экспандеры: конструкции и приложения]
 
*[https://www.mccme.ru/~anromash/courses/expanders2009.pdf Определения и несколько примеров применений]
 
*[https://www.mccme.ru/~anromash/courses/expanders2009.pdf Определения и несколько примеров применений]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: