Изменения

'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') {{- --}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|граф]], при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: ''[[Графы-экспандеры#Реберное расширение|рёберный расширитель'']], ''[[Графы-экспандеры#Вершинное расширение|вершинный расширитель'']], и ''[[Графы-экспандеры#Спектральное расширение|спектральный расширитель'']].

'''Замечание:''' Несвязный [[Основные определения теории графов#Ориентированные графы|граф ]] не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. [[Основные определения теории графов#Часто используемые графы|Полный граф ]] имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.

'''Однородный (комбинаторный) экспандер''' называется [[Основные определения теории графов#Ориентированные графы|граф ]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d - степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие:

Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число меньшее 1. Тогда для всех достаточно больших четных <tex>d = d(\epsilon)</tex> и всех <tex>n</tex> существует однородный(комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</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 \subseteq L \ |S| \leq k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.