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 \cfrac{\mathbb Z}{n} \mathbb Z}</tex> . Для любой вершины <tex>(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будут
<tex>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</tex>
