Изменения
Нет описания правки
'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') - в комбинаторике сильно разреженный граф, при этом связность определяется по вершинам, дугам или спектру.
{{Определение|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>.}}
''Граф-экспандер'' — это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: ''рёберный расширитель'', ''вершинный расширитель'', и ''спектральный расширитель''.
'''Замечание:''' Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
===Реберное расширение===
