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

ТРИУМФАЛЬНОЕ ВОЗВРАЩЕНИЕ ГРАФОВ, ДЕРЕВЬЕВ И ОТВЕРСТИЙ

Я мог бы обойти вниманием ту часть рекомбинации, где вы делите удвоенный округ на два, но не стану, поскольку это позволит мне вернуть двух персонажей из предыдущей части книги. Прежде всего, участки для голосования в избирательном округе, подобно кинозвездам или атомам в углеводородах, образуют сеть, или граф, если пользоваться термином Джеймса Джозефа Сильвестра. Территории – это вершины графа, и если они граничат друг с другом, то соответствующие вершины соединены ребром. Если участки выглядят так:

то граф так:

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

Если определить в одну группу A, B, и C, а в другую D, E и F, то все хорошо:

Однако, если взять C, D и F, то останутся A, B и E, которые не образуют связный округ.

Здесь мы оказались на краю целого кипящего кратера в теории графов. Джон Уршел, нападающий клуба «Балтимор Рэйвенс»[656], в 2017 году ушел из спорта и занялся этой темой, поскольку она всегда была ему интересна. Одна из его первых работ[657] после ухода из футбола посвящалась разбиению графов на две связные компоненты с помощью теории собственных значений, о которых мы говорили в главе 12.

Существует масса способов разбить граф на части. Когда он маленький, как представленный выше, можно просто перечислить все возможные разбиения и выбрать одно из списка наугад. Но если граф будет больше, то составлять списки всевозможных разбиений труднее. Есть трюк для случайного выбора, и в нем поучаствуют наши старые знакомые. Предположим, Акбар и Джефф играют в такую игру: по очереди убирают по одному ребру из графа, и проигрывает тот, кто разбивает граф на отдельные компоненты. Например, в графе выше Акбар может убрать ребро AF, Джефф – ребро DF, затем Акбар мог бы удалить ребро EF (но не AB, потому что тогда вершина A отделится от графа, и он проиграет!). После этого Джефф может удалить BF, и теперь Акбар в тупике: какое бы ребро он ни стер, граф разделится на две не связанные между собой части.

Мог ли Акбар сыграть умнее и победить? Нет, потому что у этой игры есть секретное свойство: если оба игрока будут стремиться не делить граф на части, то совершенно неважно, какие ходы вы делаете: игра всегда закончится после четырех ходов, и Акбар всегда проиграет. На самом деле неважно, насколько велика сеть: количество ходов в игре фиксировано. Для этой величины даже есть изящная формула:

число ребер – число вершин + 1.

В начале игры у нас 6 вершин и 9 ребер, так что 9–6 + 1 = 4. В конце игры остается только 5 ребер, и это число уменьшается до 0. То, что осталось от нашей сети, имеет весьма специальную форму: в получившемся графе нет ни одного цикла, хотя в исходном графе вы могли пройти по циклу от A к B, к F и обратно к A. Если бы в графе был какой-нибудь цикл, то вы могли бы удалить одно из его ребер, но граф не распался бы на части. Поэтому в оставшемся в результате нашей игры графе нет никаких циклов, а граф без циклов – это дерево.

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

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

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

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

(1 – 1/2) (1 – 1/8) (1 – 1/32) (1 – 1/128)…

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

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

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

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

Я хочу сделать одну оговорку. Существует огромная разница между случайным блужданием посредством метода ReCom на пространстве карт и случайным блужданием с помощью тасований на пространстве способов расположить карты в колоде в каком-то порядке. Во втором случае мы имеем теорему о семи тасованиях, где под теоремой я подразумеваю именно теорему: есть математическое доказательство, что определенного количества тасований (шести!) достаточно, чтобы добраться до любого возможного порядка карт, и, сверх того, с помощью нескольких тасований (семи!) можно обеспечить примерно одинаковую вероятность всех расположений карт в колоде. Когда дело касается округов, никаких теорем нет. О геометрии разбиений на округа мы знаем гораздо меньше, чем о геометрии тасований. Пространство всех разбиений может выглядеть, скажем, так:

В этом случае, начав с одного конца, вы потенциально можете долгое время случайно блуждать по одной части, прежде чем доберетесь до другого конца перешейка. Может даже оказаться, что пространство всех разбиений может быть разделено на две (или даже больше) отдельные части. А вдруг там есть неоткрытая страна возможных карт Северной Каролины, принципиально отличная от всех, когда-либо предлагавшихся математиками, компьютерами или недобросовестными политиками; и вполне может быть, что для этих карт десять республиканских мест из тринадцати – как раз самое обычное дело. Если мы не можем исключить такую вероятность, то имеем ли мы право говорить, что нынешняя карта с мошенническим построением границ – это выброс?

Да, насколько я понимаю. Мы не можем с абсолютной уверенностью знать, существует ли где-нибудь некое секретное хранилище альтернативных карт, но мы знаем, что на практике, если взять карту Северной Каролины, составленную законодательным собранием, и начать ее менять, то она становится менее республиканской, что бы вы с ней ни делали. Такой эксперимент дает четкое подтверждение – в любом значимом статистическом смысле, – что эта карта сфальсифицирована. Это не доказательство мошенничества картографов. Если уж на то пошло, то таким доказательством не являлись бы даже их электронные письма или заявления, прямо утверждающие, что они подтасовывают разбиение; в конце концов, нет никакого доказательства в евклидовом смысле, что они на самом деле не пытались просто набрать: «Давайте приступим к делу и начертим карты, которые беспристрастно отражают волю людей», но их пальцы соскользнули, и вместо этого получилось: «Давайте проведем границы этого штата так, чтобы мы не могли проиграть». Это доказательство в смысле закона, но не в смысле геометрии.