Графы-расширители

Материал из DISCOPAL
Перейти к: навигация, поиск
Заголовок

Графы-расширители
Автор
Стас Фомин
Нижний колонтитул
Графы-расширители
Дополнительный нижний колонтитул

Стас Фомин, 09:39, 16 апреля 2024

Источники .

Книги

Разрез / Edge-CUT .

Edge-cut-01.png

«Относительная трудноразрезаемость» .

Edge-cut-01.png
  • «Сложно разрезать при минимуме ребер»
    • Это «экспандеры/расширители»

Термины .

Edge-cut-01.png

Для подмножества S вершин G,

  • граница/boundary S
    • тут

— «константа реберного расширения» (Cheeger)

  • Ищем такие графы G, чтобы был минимум ребере при большой
    • малая h — бутылочные горлышки
    • большая — сложно разрезать

«поженим разнополные компании».

Женим-разнополые-компании-K3.pdf
  • Два полных графа
    • «синие/зеленые», «парни/девушки»
  • Начнем их «женить» по очереди, получая графы , , … ,

Семейство расширителей.

Expander-definition.png

Пример семейства расширителей.

Пример-семейства-расширителей-01.png
  • p — простое
  • Вершины
  • Соединим
    • c ←→
    • c ←→

Расширители хорошо моделируют реальность.

[[File:]]

Модели, где надо минимизировать «бутылочные горла»

  • Транспорт
  • Мозг
  • Интернет
  • Социальные сети

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.