92
правки
Изменения
м
→Реберное расширение
== Определения расширений ==
===Реберное расширение===
''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера<ref>[https://en.wikipedia.org/wiki/Cheeger_constant]</ref>) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
<tex>h(G) = \min\limits_{0 < |S|\leqslant \frac{n}{2}} \fraccfrac{|\partial_{\text{out}}(S)|}{|S|}</tex>,
где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>n/2</tex> вершин и <tex>\partial(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.
