92
правки
Изменения
м
→Конструирование
==Конструирование==
Существуют три основные стратегии создания семейств графов расширений. Первая стратегия — {{---}} алгебраическая и теоретико{{---}} групповая, вторая — {{---}} аналитическая, использующая аддитивную комбинаторику, и третья — {{---}} комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
===Маргулис-Габбер-Галил===
[[Алгебра|Алгебраическое]] конструирование, основанное на графах Кэли<ref>[[wikipedia:Cayley_graph|Wikipedia {{---}} граф Кэли]]</ref>, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером и Галилом <ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref>. Для любого натурального <tex>n</tex> строим граф, <tex>G_{n}</tex> со множеством вершин <tex>\mathbb Z _{n}\times \mathbb {Z} _{n}</tex>, где <tex>\mathbb {Z} _{n}=\mathbb Z /n \mathbb Z</tex> . Для любой вершины <tex>(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будут
