106
правок
Изменения
→Конструирование
==Конструирование==
Существуют три основные стратегии создания семейств графов расширений[6]. Первая стратегия — алгебраическая и теоретико-групповая, вторая — аналитическая, использующая аддитивную комбинаторику, и третья — комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
===Маргулис-Габбер-Галил===
Алгебраическое конструирование, основанное на графах Кэли, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером (Gabber) и Галилом (Galil). Для любого натурального <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>, её восемь соседей будут
