Графы-расширители — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
[[File:женим-разнополые-компании-K3.pdf|256px|page=1|right]] | [[File:женим-разнополые-компании-K3.pdf|256px|page=1|right]] | ||
| − | * Два полных графа <m>K_n</m | + | * Два полных графа <m>K_n</m> |
** «синие/зеленые», «парни/девушки» | ** «синие/зеленые», «парни/девушки» | ||
* Начнем их «женить» по очереди, получая графы <m>G_0</m>, <m>G_1</m>, … , <m>G_n</m> | * Начнем их «женить» по очереди, получая графы <m>G_0</m>, <m>G_1</m>, … , <m>G_n</m> | ||
| − | * <m>h(G_0)=0, h(G_1)=1/n, h(G_2)=2/n, ..., | + | * <m>h(G_0)=0, h(G_1)=1/n, h(G_2)=2/n, ..., h(G_n)=n/n=1</m> |
Версия 09:03, 16 апреля 2024
- Заголовок
- Графы-расширители
- Автор
- Стас Фомин
- Нижний колонтитул
- Графы-расширители
- Дополнительный нижний колонтитул
- Стас Фомин, 09:39, 16 апреля 2024
Содержание
Источники .
- Книги
- Графы-расширители и их применения в теории кодирования,
- Экспандеры: конструкции и приложения
- Расширительный граф на вики-бриф
- Расширьтесь, граф
Разрез / Edge-CUT .
- См. MAX-CUT
«Относительная трудноразрезаемость» .
- «Сложно разрезать при минимуме ребер»
- Это «экспандеры/расширители»
Термины .
Для подмножества S вершин G,
- граница/boundary S →
- тут
— «константа реберного расширения» (Cheeger)
- Ищем такие графы G, чтобы был минимум ребере при большой
- малая h — бутылочные горлышки
- большая — сложно разрезать
«поженим разнополные компании».
- Два полных графа
- «синие/зеленые», «парни/девушки»
- Начнем их «женить» по очереди, получая графы , , … ,