Минимальное остовное дерево

В 1926 году брненский математик Отакар Борувка напечатал в журнале для электротехников заметку о том, как соединить проводами множество пунктов, потратив меньше всего провода. Способ он показал на картинке с точками. Каждая точка соединяется с ближайшей — получается тринадцать ломаных. Каждая ломаная соединяется кратчайшим проводом с ближайшей ломаной — их остаётся четыре. Ещё раз — и сеть одна. Ниже тот же способ на настоящей карте: 675 городов и сёл Южноморавского края по справочнику GeoNames. Переключайте способ построения и смотрите на полоску под картой — она показывает, в каком порядке кладутся провода.

Между 675 сёлами можно протянуть 227 475 проводов, а сеть, которая связывает их все, обходится 674 проводами общей длиной 1570,5 км. Все три способа находят именно её, провод в провод, но идут к ней по-разному, и полоска это выдаёт. У Краскала она растёт ровной горкой: провода идут от коротких к длинным. У Прима это частокол: сеть расползается от Брно и берёт то короткий провод, то длинный — какой ближе к краю пятна. У Борувки пять горок — пять раундов: кусков сети было 675, после первого раунда 203, потом 57, 16, 4 и один. Самый длинный провод сети — 5,64 км, от Брно до Моравани: городские районы Брно в справочник не вошли, и центру не к кому подключиться ближе. История задачи и сеть, которую можно проложить руками, — в главе курса «Жадность и электричество».

Идея

Дан связный граф с весами на рёбрах — сёла и все возможные провода между ними с длинами. Нужно выбрать часть рёбер так, чтобы по ним можно было добраться из любой вершины в любую, а сумма весов была наименьшей. В лучшем наборе нет циклов: из любого цикла можно выбросить ребро, и связность сохранится, а вес уменьшится — длины положительны. Связный граф без циклов — дерево, поэтому ответ называют остовным деревом, а самое лёгкое — минимальным. У дерева на V вершинах ровно V − 1 ребро.

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

Разделение вершин на две непустые группы называют разрезом, а рёбра, которые идут из группы в группу, — рёбрами разреза. Два утверждения ниже — всё, что нужно знать, чтобы доказать любой из трёх алгоритмов. Для простоты считаем все веса различными; как обойтись без этого, сказано в разделе про Борувку.

Свойство разреза говорит, какие рёбра брать, свойство цикла — какие выбрасывать. Единственность объясняет, почему все три алгоритма в сцене нашли одну и ту же сеть: расстояния между сёлами различны, и минимальная сеть одна.

Три способа взять самое лёгкое ребро

Краскал (1956). Перебираем рёбра от лёгких к тяжёлым и берём ребро, если его концы ещё в разных кусках сети. Почему можно: пусть ребро (u, v) соединяет разные куски. Разрез «кусок, где лежит u, против всего остального» не пересекает ни одно из уже рассмотренных рёбер: концы такого ребра лежали бы в разных кусках и в тот момент, когда до него дошла очередь, — куски только растут, — и Краскал бы его взял. Значит, (u, v) — самое лёгкое ребро разреза. Проверку «в разных ли кусках» делает система непересекающихся множеств. В Моравии Краскалу хватило 3231 самого короткого провода из 227 475 — 1,4%: все провода сети не длиннее 5,64 км, и дальше можно не смотреть.

Прим (1957), а до него Ярник (1930). Сеть растёт от одной вершины: на каждом шаге берём самое лёгкое ребро из уже построенного куска наружу. Разрез «кусок против остальных», его самое лёгкое ребро — свойство разреза дословно. Для каждой вершины снаружи храним самое лёгкое ребро от куска к ней; когда кусок поглощает вершину, её соседи обновляют свои значения. Это почти алгоритм Дейкстры: там вершину ведёт сумма пути от старта, здесь — длина одного ребра до куска. Подробно — в статье об алгоритме Прима.

Борувка (1926). Раунд: каждый кусок сети одновременно находит своё самое лёгкое ребро наружу, и все найденные рёбра добавляются разом. Каждое из них — самое лёгкое ребро разреза «свой кусок против остальных», так что все они верны. Каждый кусок сливается хотя бы с одним соседом, поэтому кусков после раунда хотя бы вдвое меньше, а раундов не больше log₂ V; в Моравии их пять при log₂ 675 ≈ 9,4. Внутри раунда куски ничего друг о друге не знают, и поэтому идея Борувки лежит в основе параллельных и распределённых алгоритмов для этой задачи.

Код

Три алгоритма на всей Моравии. Провода сортируются один раз; Краскал идёт по ним, пока не наберёт 674 провода, Борувка в каждом раунде проходит по ним снова, пока у каждого куска не найдётся провод наружу. Прим написан без кучи: для полного графа массив «лучший провод до сети» выгоднее, почему — в следующем разделе. В конце программа проверяет, что три сети совпали.

Граф дорог устроен иначе: у перекрёстка две-три улицы, а не 674 соседа. Здесь Прим с кучей — то, что нужно: каждая улица один раз попадает в кучу и один раз из неё выходит. Устаревшие записи, как и в Дейкстре, не ищут, а выбрасывают, когда всплывут, — ленивое удаление.

Из 1294,2 км улиц центра Алматы хватило бы 769,7 км — 59,5%, чтобы с любого перекрёстка можно было доехать до любого. Самый длинный кусок такой сети — 3053 м; это та же улица, которая в статье о системе непересекающихся множеств последней сливала город в одно целое, когда улицы открывались от коротких к длинным. Совпадение не случайное: там работал тот же Краскал.

Сколько это стоит

Для полного графа, где E ≈ V²/2, строки таблицы расходятся сильнее, чем кажется. Краскалу нужно посчитать и отсортировать все пары, Приму с кучей — положить в кучу провод к каждой оставшейся вершине на каждом шаге, а Приму с массивом — только обновить одно число на вершину. Замер на n случайных точках квадрата:

На тысяче точек Прим без кучи быстрее Краскала в 4 раза на Python и в 5 раз на Go, а Прима с кучей — в 8 и 16 раз. Это не новость: в 1959 году Дейкстра в той же заметке, где описан его кратчайший путь, предпочёл такой вариант именно из-за плотной таблицы расстояний — Краскалу, писал он, нужно хранить и сортировать все n(n − 1)/2 проводов сразу, а его способу — не больше n. Роберт Прим двумя годами раньше подчёркивал то же: его процедура никогда не обращается больше чем к двум строкам таблицы расстояний.

Для точек на плоскости есть способ лучше любой строки таблицы. Минимальное остовное дерево всегда лежит внутри триангуляции Делоне, в которой меньше 3n рёбер, а строится она за O(n log n). Так что для 675 сёл достаточно рассмотреть пару тысяч проводов, а не двести с лишним тысяч. В теории история шла дальше: в 1995 году Дэвид Каргер, Филип Клейн и Роберт Тарьян нашли случайный алгоритм с линейным ожидаемым временем — на шагах Борувки и случайных подграфах, в 2000-м Бернард Шазель — детерминированный за O(E α(E, V)), а в 2002-м Сет Петти и Виджая Рамачандран построили детерминированный алгоритм, оптимальность которого доказана, но время работы которого до сих пор не выражено формулой.

Ловушка: по сети — не кратчайшим путём

Минимальное остовное дерево экономит общую длину проводов и ничего не обещает про расстояния между отдельными сёлами. Электричеству всё равно, каким путём течь, а вот если по той же сети прокладывать дороги, получится плохо. Коснитесь двух сёл: цветная линия — путь по проводам, пунктир — по прямой, оранжевым выделен самый длинный провод на пути.

От Брно до Микулова по проводам 87,4 км — вдвое больше, чем 43,4 км по прямой. До Бланско, которое в 18,8 км к северу, путь по сети тянется на 110,3 км: Брно подключено к сети одним проводом — к Моравани, к югу от города, — и всё остальное достигается в обход. Среди сёл, которые стоят дальше 20 км друг от друга, хуже всех пара Бенешов — Бржезина на севере края: 20,9 км по прямой и 253,3 км по проводам. Для кратчайших путей нужен другой инструмент — алгоритм Дейкстры и его дерево кратчайших путей, у которого общая длина больше, зато путь от корня до каждой вершины кратчайший.

Зато у пути по остову есть своё, другое достоинство, и оно спрятано в оранжевом проводе.

Представьте дрон, который летает от села к селу и заряжается на каждой остановке. Какая нужна дальность, чтобы долететь из Брно до Микулова? Ровно самый длинный провод на пути по остову: меньше нельзя по теореме, а этого хватает. Из Брно это всегда 5,64 км: ближе соседа у Брно в справочнике нет. Такую задачу с тысячами вопросов предлагает задача о дальности дрона.

Разрезать самые длинные провода

Если из минимального остовного дерева выбросить самый длинный провод, сеть распадётся на две части; если два самых длинных — на три. Получается способ разбить точки на группы: так в начале 1950-х группа математиков — Казимеж Флорек, Юзеф Лукашевич, Юлиан Перкаль, Гуго Штейнгауз и Стефан Зубжицкий — предложила классифицировать данные антропологов и не только. Их таксономия строила кратчайшую «дендриту», связывающую объекты, и делила объекты на группы по её длинным звеньям. Сегодня это называют кластеризацией методом одиночной связи.

Резать провода длиннее d — то же самое, что соединить все пары сёл ближе d и посмотреть на куски: это перколяция из статьи о системе непересекающихся множеств, только порогом служит расстояние. Подвигайте ползунок.

Настоящие данные показывают слабость метода. Первые разрезы отделяют не районы, а одиночек: при пороге чуть меньше 5,64 км от сети отваливается Брно, потом Бржецлав, затем на 5,17 км — единственный заметный кусок, 23 села вокруг Весели-над-Моравой, а дальше снова одиночки. Два больших района, в полторы-две сотни сёл каждый, появляются только при пороге около 3,4 км, и к этому моменту край распадается на 69 кусков, из них 35 — одиночки. Одиночная связь тянет цепочки: два района, между которыми есть хоть одна вереница близких сёл, она считает одним. Поэтому для «районов» обычно берут другие методы — k-средних или DBSCAN, — а одиночную связь — там, где важен именно разрыв, как в задаче о районах электросети.

Где работает

• Проектирование сетей. Электросеть, водопровод, оптоволокно, печатные платы: остовное дерево — первый набросок и ориентир по цене. Настоящая сеть обычно длиннее: линии идут вдоль дорог, а важные узлы соединяют кольцом, чтобы одна авария не обесточила полкрая. А если разрешить развилки не только в сёлах, но и в чистом поле, провода можно сэкономить ещё — это уже задача Штейнера, несравнимо более трудная.
• Кластеризация. Метод одиночной связи в scipy.cluster.hierarchy.linkage, по документации, считается через минимальное остовное дерево за O(n²).
• Изображения. Метод Фельценшвальба и Хаттенлохера (2004) делит снимок на области, перебирая рёбра между соседними пикселями от похожих к непохожим, как Краскал, и сливая области системой непересекающихся множеств.
• Коммивояжёр. Обойдите остов, как обходят дерево в глубину, и пропускайте уже посещённые города: маршрут выйдет не длиннее двух оптимальных, потому что остов не длиннее оптимального маршрута без одного ребра. На этом же построен алгоритм Кристофидеса с гарантией в полтора оптимума — подробнее в статье о коммивояжёре.
• Параллельные вычисления. Раунды Борувки независимы внутри раунда, и на них строят остовы графов, которые не помещаются на одну машину.

Задача, которую открывали снова и снова

Историю Борувки, его друга-энергетика Индржиха Саксла и письма Войтеха Ярника, напечатанного в 1930 году под тем же названием «О некоторой задаче на минимум», подробно рассказывает глава курса. Добавим, что было дальше. В 1938 году Гюстав Шоке описал тот же способ раундов для городов на плоскости. В начале 1950-х его в третий раз открыли — для таксономии. В 1956 году Джозеф Краскал опубликовал свой вариант и, что важно, сослался на Борувку и отметил его доказательство единственности. Через год Роберт Прим из Bell Labs, где проектировали телефонные сети, описал рост от одной вершины, а в 1959-м то же сделал Дейкстра, не зная о Приме. В 1961 году Жорж Соллен рассказал о раундах на семинаре Клода Бержа; рукопись так и не вышла, но книга Бержа и Гуйа-Ури сослалась на неё, и раунды Борувки долго называли алгоритмом Соллена. Эту запутанную историю распутали Рональд Грэм и Павол Хелл в статье 1985 года.

Задачи

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