106
правок
Изменения
→Определение
==Определение==
''Экспандер '' — это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: ''рёберный расширитель'', ''вершинный расширитель'', и ''спектральный расширитель''.
Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
===Реберное расширение===
''Рёберное расширение '' (также ''изопериметрическое число '' или константа Чигера) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
<tex>h(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}</tex>,
где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>n/2</tex> вершин и <tex>∂(S)</tex> — ''граничные дуги '' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.
===Вершинное расширение===
''Вершинное изопериметрическое число '' <tex>h_{out}(G)</tex> (также ''вершинное раширение'') графа <tex>G</tex> определяется как
<tex>h_{out}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},</tex>
где <tex>∂_{out}(S)</tex> — ''внешняя граница '' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>, имеющих как минимум одного соседа в S. В варианте этого определения (называемом ''уникальным соседним расширением'') <tex>∂_{out}(S)</tex> заменяется на множество вершин из <tex>V</tex> с ''точностью одним '' соседом из <tex>S</tex>.
''Вершинное изопериметрическое число '' <tex>h_{in}(G)</tex> графа <tex>G</tex> определяется как
<tex>h_{in}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|},</tex>
где <tex>∂_{in}(S)</tex> — ''внутренняя граница '' <tex>S</tex>, то есть множество вершин <tex>S</tex>, имеющих как минимум одного соседа в <tex>V(G)\setminus S</tex>.
===Спектральное расширение===
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\tfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>−1</tex> и <tex>1</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения матрицы Кирхгофа. Для направленного графа используются сингулярные значения матрицы сопряжения A, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
==Конструирование==
Существуют три основные стратегии создания семейств графов расширений[6]. Первая стратегия — алгебраическая и теоретико-групповая, вторая — аналитическая, использующая аддитивную комбинаторику, и третья — комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
