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

Версия 09:25, 16 апреля 2024

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

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

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

@@ Строка 43: / Строка 43: @@
 * Начнем их «женить» по очереди, получая графы <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>
+=== Семейство расширителей. ===
+[[File:expander-definition.png|center]]
+=== Пример семейства расширителей. ===
+[[File:пример-семейства-расширителей-01.png|right|256px]]
+* Вершины <m>\{0,\dots,p(prime)-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>