92
правки
Изменения
м
{{Определение|definition=Двудольный граф <tex>G = (L, R, E) \ (L</tex> и <tex>R</tex> {{---}} левая и правая доли графов, <tex>E</tex> {{---}} множество ребер<tex>)</tex> называется <tex>(n, m, d)-</tex>'''экспандером''' (расширяющимся графом), если <tex>|L| Определения расширений = n, |R| = m</tex>, степень всех вершин в доле <tex>L</tex> равна <tex>d</tex>, и выполняются следующие свойства расширения:* Для любого множества <tex>S \subset L, |S| \leqslant \dfrac{n}{1000d}</tex> множество соседей (соседи <tex>S</tex> лежат в <tex>R</tex>) достаточно велико: <tex>|Г(S)| > \dfrac{7}{8}d|S|</tex>.* Для любого множества <tex>S \subset L</tex>, такого что <tex>|S| \leqslant \dfrac{n}{2}</tex>, множество соседей немного больше самого множества <tex>S</tex>, а именно, <tex>|Г(S)| > \dfrac{9}{8}|S|</tex>.}}''Граф-экспандер'' — это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: ''рёберный расширитель'', ''вершинный расширитель'', и ''спектральный расширитель''. '''Замечание:''' Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
Нет описания правки
'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') - в комбинаторике сильно разреженный граф, при этом связность определяется по вершинам, дугам или спектру.Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: ''рёберный расширитель'', ''вершинный расширитель'', и ''спектральный расширитель''. '''Замечание:''' Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.== Основные определения ===== Однородный (комбинаторный) экспандер ===
{{Определение
|definition=
для достаточно больших четных <tex>d = d(\epsilon)</tex> существует однородный(комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.
}}
=== Двудольный экспандер ===
{{Определение
|definition=
Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.
}}
===Реберное расширение===
''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
*[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)]
*[http://www.tcs.tifr.res.in/~prahladh/teaching/05spring/lectures/lec1.pdf лекции Синтии Дворка]
*[S. Hoory, N. Linial, A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, vol. 43, Number 4, Oct. 2006, pp.439 561.]
*[ H. Buhrman, P.B. Miltersen, J. Radhakrishnan, S. Venkatesh. Are Bitvectors optimal? SIAM J. Comput., 31(6):1723–1744, 2002.]
