106
правок
Изменения
м
→Определение
''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
<tex>h(G) = \min_min\limits_{0 < |S|\le leqslant \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}</tex>,
где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>n/2</tex> вершин и <tex>\partial(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.
''Вершинное изопериметрическое число'' <tex>h_{out}(G)</tex> (также ''вершинное раширение'') графа <tex>G</tex> определяется как
<tex>h_{out}(G) = \min_min\limits_{0 < |S|\le leqslant \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},</tex>,
где <tex>\partial_{\text{out}}(S)</tex> — ''внешняя граница'' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>, имеющих как минимум одного соседа в <tex>S</tex>. В варианте этого определения (называемом ''уникальным соседним расширением'') <tex>\partial_{\text{out}}(S)</tex> заменяется на множество вершин из <tex>V</tex> с ''точностью одним'' соседом из <tex>S</tex>.
''Вершинное изопериметрическое число'' <tex>h_{in}(G)</tex> графа <tex>G</tex> определяется как
<tex>h_{in}(G) = \min_min\limits_{0 < |S|\le leqslant \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|},</tex>,
где <tex>∂_\partial_{in}(S)</tex> — ''внутренняя граница'' <tex>S</tex>, то есть множество вершин <tex>S</tex>, имеющих как минимум одного соседа в <tex>V(G)\setminus S</tex>.
===Спектральное расширение===
