92
правки
Изменения
м
→Однородный (комбинаторный) экспандер
|definition=
'''Однородный (комбинаторный) экспандер''' называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d {{---}} степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие:
для <tex>\ \forall S \subseteq V, \ |S| \leq n/2 \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
}}
'''Замечание:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.
