106
правок
Изменения
→Определение
<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>∂\partial(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.
===Вершинное расширение===
<tex>h_{out}(G) = \min_{0 < |S|\le \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>, имеющих как минимум одного соседа в S. В варианте этого определения (называемом ''уникальным соседним расширением'') <tex>∂_\partial_{\text{out}}(S)</tex> заменяется на множество вершин из <tex>V</tex> с ''точностью одним'' соседом из <tex>S</tex>.
''Вершинное изопериметрическое число'' <tex>h_{in}(G)</tex> графа <tex>G</tex> определяется как
