92
правки
Изменения
м
Нет описания правки
{{Определение|definition=Граф-экспандер (или расширяющийся граф, англ. ''expander graph'') {{---}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|граф]], при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: [[Графы-экспандеры#Реберное расширение|рёберный расширитель]], [[Графы-экспандеры#Вершинное расширение|вершинный расширитель]], и [[Графы-экспандеры#Спектральное расширение|спектральный расширитель]].}}
Любой связный граф является экспандером, однако различные связные [[Основные определения теории графов#Ориентированные графы|графы]] имеют различные параметры расширителя. [[Основные определения теории графов#Часто используемые графы|Полный граф]] имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
Множество соседей для множества вершин <tex>S</tex> называется <tex>\Gamma(S) = \{v: \exists w \in S:\ (v, w) \in E\}</tex>.
}}
'''Замечание:''' в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\forall S: S \supseteq \Gamma(S)</tex>.
=== Однородный (комбинаторный) экспандер ===
{{Определение
|definition=
'''Однородный (комбинаторный) экспандер''' называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d {{---}} степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие:
для <tex>\ \forall S: S \subseteq V, \ |S| \leq n/2 \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
}}
'''Замечание:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.
{{Определение
|definition=
'''Двудольный экспандер''' называется [[Двудольные графы|двудольный граф]] <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: S \subseteq L \ |S| \leq k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
}}
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
<tex>Prob[</tex>свойство экспандерности графа нарушено<tex>] \leq \ \sum_{S, T}^{}(\cfrac{|T|}{m})^{sd}</tex>,
где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leq k \ \forall T: T \subset R \ |T| = (1 - \epsilon)d|S| </tex>. Оценим данную сумму сверху:
<tex>\sum_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* (\cfrac{(1 - \epsilon)sd}{m})^{sd}</tex>.
|statement=
Пусть <tex>G</tex> {{---}} [[Двудольные графы|двудольный граф]].
<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S: S \supseteq L |S| \leq \Gamma(S)</tex>.
|proof=
Будем доказывать по индукции
Рассмотрим два случая:
1. <tex>\forall S: S \supseteq L, |S| \neq 0</tex> строго расширяется, то есть <tex>|\Gamma(S)| > |S|</tex>.
Выберем <tex>\forall x: x \supset V(L) : (x, y) \in E</tex>. Тогда рассмотрим двудольный граф <tex>G^{*}</tex>, у которого левая доля <tex>L^{*} = L \diagdown {x}</tex>, а правая <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S: S \supset L</tex> удовлетворяет строгому неравенству теоремы, то каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, поскольку только одна вершина <tex>y</tex> была удалена из <tex>R</tex>. Следовательно, по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро (x, y) что дает совершенное паросочетание.
2. Пусть <tex>\exists\ T \in L, \ |T| \neq 0</tex> такое, что <tex>|\Gamma(T)| = |T|</tex>.
