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

Ссылки сюда (1) →

Slide Show

Заголовок

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

Автор

Стас Фомин

Нижний колонтитул

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

Дополнительный нижний колонтитул

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

Источники .

• Википедия

Книги

• Графы-расширители и их применения в теории кодирования,
• Экспандеры: конструкции и приложения
• Расширительный граф на вики-бриф
• Расширьтесь, граф, [1]

Разрез / Edge-CUT .

• См. MAX-CUT

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

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

Термины .

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

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

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

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

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

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

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

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

• p — простое
• Вершины
• Соединим
  • c ←→
  • c ←→

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

[[File:]]

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

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

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

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

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