Разрез / Edge-CUT
- См. MAX-CUT
«Относительная трудноразрезаемость»
- «Сложно разрезать при минимуме ребер»
- Это «экспандеры/расширители»
Термины
Для подмножества S вершин G,
- граница/boundary S →
- тут
— «константа реберного расширения» (Cheeger)
- Ищем такие графы G, чтобы был минимум ребере при большой
- малая h — бутылочные горлышки
- большая — сложно разрезать
«поженим разнополные компании»
- Два полных графа
- «синие/зеленые», «парни/девушки»
- Начнем их «женить» по очереди, получая графы , , … ,
Семейство расширителей
Пример семейства расширителей
- p — простое
- Вершины
- Соединим
- c ←→
- c ←→
- c ←→