92
правки
Изменения
объединил основные определения и определения расширений
Любой связный граф является экспандером, однако различные связные [[Основные определения теории графов#Ориентированные графы|графы]] имеют различные параметры расширителя. [[Основные определения теории графов#Часто используемые графы|Полный граф]] имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
== Основные определения ==
{{Определение
|definition=
}}
'''Замечание:''' в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\forall S: S \supseteq \Gamma(S)</tex>.
===Вершинное расширение===''Вершинное изопериметрическое число'' <tex>h_{out}(G)</tex> (также ''вершинное раширение'') графа <tex>G</tex> определяется как <tex>h_{out}(G) = \min\limits_{0 < |S|\leqslant \cfrac{n}{2}} \cfrac{|\Gamma_{\text{out}}(S)|}{|S|}</tex>, где <tex>\Gamma_{\text{out}}(S)</tex> — ''внешняя граница'' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>, имеющих как минимум одного соседа в <tex>S</tex>. <tex>\Gamma_{\text{out}}(S) = \{v \in V(G) \diagdown S: \exists w \in S (v, w) \in E\}</tex>. ''Вершинное изопериметрическое число'' <tex>h_{in}(G)</tex> графа <tex>G</tex> определяется как <tex>h_{in}(G) = \min\limits_{0 < |S|\leqslant \cfrac{n}{2}} \cfrac{|\Gamma_{\text{in}}(S)|}{|S|}</tex>, где <tex>\Gamma_{in}(S)</tex> — ''внутренняя граница'' <tex>S</tex>, то есть множество вершин <tex>S</tex>, имеющих как минимум одного соседа в <tex>V(G)\setminus S</tex>. <tex>\Gamma_{in}(S) = \Gamma(S) \diagdown \Gamma_{in}(S)</tex>==== Однородный (комбинаторный) экспандер ====
{{Определение
|definition=
}}
==== Двудольный экспандер ====
{{Определение
|definition=
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
==== теорема о Паросочетаниях ====
{{Теорема
|statement=
}}
===Реберное расширение===
''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера<ref>[[wikipedia:Cheeger_constant|Wikipedia {{---}} константа Чигера]]</ref>) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>n/2</tex> вершин и <tex>\partial(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.
===Спектральное расширение===
