ВЕДИ СЕБЯ КВАЗИСЛУЧАЙНО. ЧАСТЬ II

Вчера мы закончили на вопросе: есть ли алгоритмы построения квазислучайных графов? Оказывается, есть. Например, граф Пэли.

Алгоритм полностью детерминированный, но на выходе будет квазислучайный граф для честной монетки. Как строить такое? Подробнее можно почитать в Википедии. Но давайте разберём на примере 9.

1️⃣ Сначала надо выбрать число вершин. Это должно быть число, которое является степенью простого числа, и так, чтобы остаток от деления на 4 был 1. Например, 9: это 3² и 9 mod 4 = 1.

2️⃣ Дальше строится поле F9, F — поле Галуа (А что тут непонятного? Монада — это моноид в категории эндофункторов (с)).

Вершины для F9 (расширение F3) — это 9 элементов вида a + bi, где a и b берутся из {0, 1, 2}. Само поле строим по правилу i² = −1 = 2 (это та самая «мнимая единица», как у комплексных чисел): складываем покоординатно по модулю 3, а i² всюду заменяем на 2.

(0,0) = 0 (вершина 0)
(1,0) = 1 (вершина 1)
(2,0) = 2 (вершина 2)
(0,1) = i (вершина 3)
(0,2) = 2i (вершина 4)
(1,1) = 1+i (вершина 5)
(1,2) = 1+2i (вершина 6)
(2,1) = 2+i (вершина 7)
(2,2) = 2+2i (вершина 8)

3️⃣ Возводим все эти числа во вторую степень (не забываем i² = 2 и модуль 3):

(0,0) → 0
(1,0) → 1
(2,0) → 1
(0,1) → 2
(0,2) → 2
(1,1) → 2i
(1,2) → i
(2,1) → i
(2,2) → 2i

Собираем уникальные значения {1, 2, i, 2i} (ноль не очень интересен).

4️⃣ Дальше для каждой пары вершин a и b рисуем ребро, если a-b попадает в {1, 2, i, 2i}.

Например:

1 − 0 = 1 — попадает!
2+2i − 0 = 2+2i — не попадает
2+2i − (1+2i) = 1 — попадает!

И так для каждой уникальной пары.

Финальный граф нарисовала для вас на картинке. Вершины поставила, чтобы было красиво. Такое вполне можно программировать!

Граф похож на случайный же? Ставьте 🔥, если да.

#бабанюра_программирует