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

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

Slide Show

Заголовок

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

Автор

Стас Фомин

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

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

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

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

Источники .

• Википедия

Книги

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

Разрез / Edge-CUT .

• См. MAX-CUT

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

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

Термины .

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

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

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

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

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

• Два полных графа , , … ,

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

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

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