Форма реальности. Скрытая геометрия стратегии, информации, общества, биологии и всего остального

Сколько отверстий в этой сети? Это в каком-то смысле вопрос запутанный – подобно вопросу о количестве отверстий в соломинке или в брюках. Однако я уже дал вам на него ответ – в точности написанное выше число: количество ребер минус количество вершин плюс 1. Каждый раз, вырезая ребро из цикла, вы избавляетесь от одного отверстия. Когда больше вырезать нечего, у вас остается граф без отверстий вообще: дерево. Это не просто метафора, а фундаментальный инвариант для любых видов пространства под названием эйлерова характеристика; она очень, очень, очень примерно говорит вам о количестве отверстий[658]. Мы уже встречались с ней, когда считали отверстия в соломинках и штанах. Свои эйлеровы характеристики есть у соломинок, сетей и моделей 26-мерного пространства-времени из теории струн: единая теория охватывает все геометрии – от скромных до космических.

Итак, мы вернулись к геометрии деревьев. Дерево, которое получается в конце описанной игры с вырезанием ребер, называется остовным: остовное дерево графа – это дерево с теми же вершинами и с максимальным вырезанным числом ребер. Такие объекты встречаются в математике постоянно. Если вы построите остовное дерево для квадратной решетки (вроде улиц Манхэттена), то получится нечто знакомое под названием лабиринт. Белые линии на рисунке – это ребра[659]. Если у вас есть под рукой карандаш, то можете убедиться, что лабиринт связный: вы можете проложить путь от любой точки до другой, не покидая белых линий. По сути, существует только один маршрут, который можно проложить без возвращения.

Вы можете также изобразить остовное дерево, где вершины будут точками, а ребра – отрезками прямых; это больше похоже на то, как мы рисовали граф для разбиения избирательных участков.

У большинства графов сколько-нибудь приличного размера не одно остовное дерево, а много. Физик XIX века Густав Кирхгоф вывел формулу для их количества, однако она не отвечает на все возникающие вопросы, так что даже спустя столетие в этой области ведутся активные исследования. Здесь есть регулярность и структура. Например, сколько тупиков в случайном лабиринте? Конечно, чем больше лабиринт, тем больше в нем тупиков, но что, если мы зададимся вопросом, какую долю от мест в лабиринте занимают тупики? Очень крутая теорема Манны, Дхара и Мажумдара[660] 1992 года показывает, что при увеличении размеров лабиринта эта доля не сходится ни к 1, ни к 0, а по какой-то причине стремится к числу (8 / π²) (1–2 / π), чуть менее 0,3. Вы можете подумать, что число остовных деревьев в случайном графе будет более или менее случайным числом. Нет. Моя коллега Мелани Матчетт Вуд доказала в 2017 году[661], что если ваш граф выбирается случайным образом[662], то количество остовных деревьев будет четным с чуть большей вероятностью, чем нечетным. Точнее говоря, вероятность того, что количество остовных деревьев нечетно, будет бесконечным произведением:

(1 – ¹/₂) (1 – ¹/₈) (1 – ¹/₃₂) (1 – ¹/₁₂₈)…

где знаменатель каждой дроби вчетверо больше предыдущего. Снова геометрическая прогрессия! Это произведение примерно равно 0,419, то есть довольно далеко от 0,5. Такая асимметрия – признак какой-то более глубокой геометрической структуры на совокупности всех остовных деревьев; оказывается, существует осмысленный способ сказать, когда последовательность остовных деревьев образует арифметическую прогрессию![663]

Но чтобы объяснить это, мне пришлось бы углубиться в захватывающие подробности, а мы еще не спасли демократию. Поэтому вернемся к нашим избирательным округам.

Как только у вас в руках окажется остовное дерево, разделить сеть на части не составит труда: просто сделайте проигрывающий ход, убрав ребро и разъединив граф. Любой ваш выбор разделит граф на две части; если немножко постараться, то можно найти ребро, которое делает их примерно равными по размеру. (Если не выходит, возьмите другое дерево и начните заново.) Получится приблизительно такая картинка: и слева, и справа одну из частей я выделил, а другую – нет.

Теперь вы более или менее знаете, как работает ReCom[664]: берете удвоенный округ, выбираете наугад остовное дерево (например, проведя игру со случайным удалением ребер[665]), выбираете в нем случайное ребро, режете его – и ваш граф распадается ровно на два новых округа.