Графы-расширители — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
* [https://users.mccme.ru/anromash/courses/expanders-notes-2014.pdf Экспандеры: конструкции и приложения] | * [https://users.mccme.ru/anromash/courses/expanders-notes-2014.pdf Экспандеры: конструкции и приложения] | ||
* [https://ru.wikibrief.org/wiki/Expander_graph Расширительный граф на вики-бриф] | * [https://ru.wikibrief.org/wiki/Expander_graph Расширительный граф на вики-бриф] | ||
| − | * [https://nplus1.ru/material/2020/04/06/abel Расширьтесь, граф] | + | * [https://nplus1.ru/material/2020/04/06/abel Расширьтесь, граф], [https://www.youtube.com/watch?v=-jcZu4hDstA] |
=== Разрез / Edge-CUT . === | === Разрез / Edge-CUT . === | ||
| Строка 52: | Строка 52: | ||
[[File:пример-семейства-расширителей-01.png|right|256px]] | [[File:пример-семейства-расширителей-01.png|right|256px]] | ||
| − | * Вершины <m>\{0,\dots,p | + | * ''p'' — простое |
| + | * Вершины <m>\{0,\dots,p-1\}</m> | ||
* Соединим | * Соединим | ||
| − | ** <m>a\neq 0</m> c ←→ | + | ** <m>a \neq 0</m> c ←→ |
*** <m>a\pm 1 \bmod p</m> | *** <m>a\pm 1 \bmod p</m> | ||
*** <m>a^{-1} \bmod p</m> | *** <m>a^{-1} \bmod p</m> | ||
** <m>a = 0</m> c ←→ | ** <m>a = 0</m> c ←→ | ||
*** <m>0, 1, p-1</m> | *** <m>0, 1, p-1</m> | ||
| + | |||
| + | === Расширители хорошо моделируют реальность. === | ||
| + | [[File:]] | ||
| + | |||
| + | Модели, где надо минимизировать «бутылочные горла» | ||
| + | * Транспорт | ||
| + | * Мозг | ||
| + | * Интернет | ||
| + | * Социальные сети | ||
Текущая версия на 09:39, 16 апреля 2024
- Заголовок
- Графы-расширители
- Автор
- Стас Фомин
- Нижний колонтитул
- Графы-расширители
- Дополнительный нижний колонтитул
- Стас Фомин, 09:39, 16 апреля 2024
Содержание
Источники .
- Книги
- Графы-расширители и их применения в теории кодирования,
- Экспандеры: конструкции и приложения
- Расширительный граф на вики-бриф
- Расширьтесь, граф, [1]
Разрез / Edge-CUT .
- См. MAX-CUT
«Относительная трудноразрезаемость» .
- «Сложно разрезать при минимуме ребер»
- Это «экспандеры/расширители»
Термины .
Для подмножества S вершин G,
- граница/boundary S →
- тут
— «константа реберного расширения» (Cheeger)
- Ищем такие графы G, чтобы был минимум ребере при большой
- малая h — бутылочные горлышки
- большая — сложно разрезать
«поженим разнополные компании».
- Два полных графа
- «синие/зеленые», «парни/девушки»
- Начнем их «женить» по очереди, получая графы , , … ,
Семейство расширителей.
Пример семейства расширителей.
- p — простое
- Вершины
- Соединим
- c ←→
- c ←→
- c ←→
Расширители хорошо моделируют реальность.
[[File:]]
Модели, где надо минимизировать «бутылочные горла»
- Транспорт
- Мозг
- Интернет
- Социальные сети