Графы-расширители — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии этого же участника)
Строка 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 . ===
Строка 37: Строка 37:
 
=== «поженим разнополные компании». ===
 
=== «поженим разнополные компании». ===
  
[[File:женим-разнополые-компании-K3.pdf|256px|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, ..., $h(G_n)=n/n=1 </m>
+
* <m>h(G_0)=0, h(G_1)=1/n, h(G_2)=2/n, ..., h(G_n)=n/n=1</m>
 +
 
 +
=== Семейство расширителей. ===
 +
 
 +
[[File:expander-definition.png|center]]
 +
 
 +
=== Пример семейства расширителей. ===
 +
 
 +
[[File:пример-семейства-расширителей-01.png|right|256px]]
 +
 
 +
* ''p'' — простое
 +
* Вершины <m>\{0,\dots,p-1\}</m>
 +
* Соединим
 +
** <m>a \neq 0</m> c ←→
 +
*** <m>a\pm 1 \bmod p</m>
 +
*** <m>a^{-1} \bmod p</m>
 +
** <m>a = 0</m> c ←→
 +
*** <m>0, 1, p-1</m>
 +
 
 +
=== Расширители хорошо моделируют реальность. ===
 +
[[File:]]
 +
 
 +
Модели, где надо минимизировать «бутылочные горла»
 +
* Транспорт
 +
* Мозг
 +
* Интернет
 +
* Социальные сети

Текущая версия на 09:39, 16 апреля 2024

Заголовок

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

Стас Фомин, 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:]]

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

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