Как найти минимальный разрез графа

Поточная сеть — Теория графов

В этом уроке мы разберем, что такое поточная сеть. Вы узнаете, как строятся такие сети и как диграфы помогают в этом.

Как строится поточная сеть

Представим, что у нас есть диграф и две вершины — источник и сток. У каждого ребра есть вес, который называется его пропускной способностью. Нам нужно пропустить как можно больше материала через диграф от источника к стоку. Это называется потоком, а взвешенный диграф — сетью. Таким образом мы строим сетевой поток.

Например, источник — это

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

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

Общее объем потока, который проходит через сеть, называется величиной потока. Это количество можно найти, если посчитать:

Общий поток, который выходит из источника

Общий поток, который входит в сток

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

Если предположить, что транспортная сеть — это ограничивающий фактор, то нас интересует, сколько сырья мы можем доставить на фабрику.

Многие несвязанные проблемы теории графов можно преобразовать в проблемы сетевых потоков.

Теорема о максимальном потоке и минимальном разрезе

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

Найти максимальный поток и минимальный разрез в графе, продемонстрировав работу алгоритма Форда-Фалкерсона

Н айдем путь, по которому можно увеличить поток и увеличим поток

Е сть еще один путь, по которому можно увеличить поток

Теперь при поиске вершин, в которых можно создать избыток потока, получим

с ледующий граф. Цветом выделены все вершины в которых можно получить избыточный поток. Все ребра, соединяющие помеченные и непомеченные вершины входят в минимальный разрез. Размер разреза равен размеру потока и они равны 25.

Теория графов в Игре Престолов

Недавно, на Geektimes я опубликовал статью, где привёл немного поверхностной статистики из серии книг «Песнь льда и пламени». Но я не стал углубляться в самую интересную часть, в граф социальных связей, ибо тема заслуживает отдельного внимания. В этой статье я продемонстрирую как теория графов может помочь при анализе подобных данных и приведу реализации алгоритмов, которыми я пользовался.

Всем кому интересно, добро пожаловать под кат.

Из опроса вышеупомянутой статьи, я сделал вывод, что больше трети аудитории Geektimes ознакомлено с книгой фентези романа, а больше половины с сюжетом из сериала. Я надеюсь, аудитории Geektimes и Habrahabr пересекаются и вам возможно будут интересны не только использованные алгоритмы, но и результаты.

Данные

Начнём, конечно же, с главного — данных. У нас есть граф социальной активности:

На нём изображены персонажи из мира престолов в вершинах графа, где размер вершины зависит от сказанных им слов, и диалогов персонажей на ребрах графа, где толщина ребра зависит от количества состоявшихся разговоров.

Общие сведения о графе:

Граф неориентированный.
Вершин (читай персонажей): 1105
Рёбер (читай диалогов): 3505

Это всё хорошо, но кто же составил список всех разговоров, да еще и определил их принадлежность спросите вы меня (в 5ти книгах ведь почти 2 миллиона слов). Метод условных случайных полей, отвечу я. Да, для сбора данных было привлечено машинное обучение и, как заявляет «тренер» модели, точность определения принадлежности разговора составляет около 75%. Я добавлю опросник в конце статьи, чтобы узнать стоит ли переводить эту статью о том как метод условных случайных полей был применен.

Итак, формат входных данных для всех алгоритмов будет одинаковый:

Первая строка содержит V и E, количество вершин и ребер в графе соответственно.

Далее идут V строк с ID персонажа и его именем. После этого E строк вида u v w — описание рёбер. Означает, что между u и v есть ребро с весом w, где u и v это ID персонажа. Напомню, что вес означает количество диалогов между соответствующими персонажами. Вес самих вершин учитываться нигде не будет, т.к. не нашёл достойного ему применения. Ах да, код алгоритмов будет представлен на языке C++.

Нам, конечно же, нужно считать данные. Для этого я создал файлы definitions.h и definitions.cpp. Далее я везде буду подключать definitions.h чтобы кода было меньше и код читался легче. Каждый последующий алгоритм реализован как отдельная функция и вызывается в функции main.

Степень вершины

Для начала, попробуем реализовать что нибудь очень простое, что даже стыдно назвать алгоритмом, но будет интересно читателю/зрителю. Найдём степень каждой вершины. Степень вершины — это количество рёбер, инцидентных (примыкающих к) вершине. Этот параметр в контексте графа, который мы имеем, покажет нам сколько же «друзей» у персонажа.

Это можно сделать за один проход и сложность этого алгоритма О(V+E). Если применить и сортировку результата, как это сделал я, то сложность будет O(E+V*log(V)).

Топ 10 многосвязных персонажей:

Тирион Ланнистер: 168
Джон Сноу: 128
Арья Старк: 104
Джейми Ланнистер: 102
Серсея Ланнистер: 86
Кейтилин Старк: 85
Теон Грейджой: 76
Дайнерис Таргариен: 73
Бриенна: 71
Санса Старк: 69

Интересно то, что в топе не оказалось того, кто знаком со многими и по занимаемой должности обязан поддерживать контакт с людьми, Вариса (он на 25ом месте). А вот, казалось бы, второстепенный персонаж Бриенна, от имени которой главы еще нет, на 9ом месте.

Обход графа

Итак, теперь перейдем к простым алгоритмам, а именно к поиску в глубину (Depth-first search) и поиску в ширину (Breadth-first search). Оба алгоритма очень похожи, различаются только способом обхода графа. Они применяются, когда требуется пройти по рёбрам от заданной вершины в графе до другой. В случае поиска в глубину, граф проходится начиная от вершины и поочередно в максимальную глубину по одному из исходящих рёбер. В случае же с поиском в ширину граф обходится сначала по всем своим соседним вершинам, далее по соседям соседних вершин и так пока не пройденных вершин не останется. Оба алгоритма имеют сложность O(V+E).

Связность графа

Найдём компоненты связности нашего графа. Компонента связности это подграф, у которого все вершины имеют путь до любой другой вершины компоненты. Для этого запустим алгоритм поиска в глубину по одному из вершин, а после завершения, в следующей, не помеченной алгоритмом, вершине. Таким образом каждый запуск поиска будет означать новую компоненту связности.

Было бы крайне странно, если бы граф был не связным и в нём было больше одной компоненты, не правда ли? Но к моему удивлению в графе оказалось аж 3 компоненты! Но посмотрев на них я увидел, что присутствовала одна большая компонента, и 2 другие, в которых было по одному персонажу (Это были улыбающийся старик (A smiley old man), который разговаривал с Арьей возле Божьего ока (God’s eye). И повар (A Cook), который играл с Тирионом на корабле). Ничего необычного, у них нет имён и удивительно, что участники разговора вообще определились правильно. Я, конечно же, добавил недостающие рёбра и в результате весь граф получился связным.

Теория рукопожатий

Следующее что мы найдем с помощью алгоритма поиска уже в ширину — максимальное число рукопожатий в графе, другими словами диаметр графа, т.е наидлиннейший из кратчайших путей между всеми вершинами графа. Как оказалось, максимальное количество рукопожатий это 8. Неплохой результат для произведения о «средневековых веках», если учитывать Теорию 6ти рукопожатий. Для примера, одна из таких цепочек связи:

Матушка Кротиха (Mother Mole) — Репейница (Thistle) — Варамир (Varamyr) — Джон Сноу (Jon Snow) — Эддард Старк (Ned Stark) — Барристан Селми (Barristan Selmy) — Квентин Мартелл (Quentyn Martell) — Принц-Оборванец (The Tattered Prince) — Льюис Ланстер (Lewis Lanster)

Такой алгоритм работает за O(V*V+V*E). Так как нужно запустить алгоритм BFS из каждой вершины графа. Будь этот граф деревом, то потребовалось бы только 2 раза запустить BFS. Сначала из любой вершины графа, а затем из самой отдалённой от неё вершины. И наибольшая глубина последнего запуска и была бы диаметром графа.

А раз я нашёл самые длинные пути для всех вершин графа, то можно вычислить и среднее значение, а так же составить распределение максимальных путей. Среднее значение для длины максимальных путей оказалось 6,16 (в среднем вполне вписывается в теорию о 6ти рукопожатиях), а общее среднее расстояние 3,6, для сравнения у фейсбука этот параметр 4.57.

Распределение длин максимальных путей:

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

Клики в графе

Алгоритм Брона-Кербоша позволяет найти максимальные клики в графе, иными словами подмножества вершин, любые две из которых связаны ребром. В контексте рассматриваемого графа это позволит найти сильно связанные компании, которые общались между собой в истории. Сложность алгоритма линейна относительно количества клик в графе, но в худшем случае она экспоненциальна O(3 V/3 ), алгоритм решает NP полную задачу всё таки. Сам по себе алгоритм представляет рекурсивную функцию, которая для каждой вершины находит максимальную клику, т.е. такую, в которую нельзя добавить ни одной другой вершины. Итак, результаты:

Распределение размеров клик:

Как видно, максимальная клика размером в 9 персонажей. К примеру одна из таких — компания Ланнистеров: Тирион, Джейми, Серсея, Варис, Тайвин, Кеван, Пицель, Петир и Мейс Тирелл. Что интересно, все клики размера 8 и 9 сформированы в Королевской Гавани или вблизи неё. А максимальная клика с Дайнерис размера 5.

Остовное дерево

А теперь немного упростим наш граф связей, оставив в нём только «костяк», так называемое остовное дерево, т.е. наиболее важные рёбра связи и при этом превратив граф в дерево со всеми исходными вершинами. Поможет нам в этом алгоритм Крускала. Алгоритм жадный, для его осуществления нужно всего лишь отсортировать все рёбра по их весу и поочередно добавлять каждое ребро, если оно связывает две компоненты. Если использовать правильную структуру данных (обычно используют систему непересекающихся множеств), то сложность алгоритма получится O(E(logE)+V+E) = O(E(logV)). Ниже приведен результат графа, который подвергся этим манипуляциям. Я так же для читаемости удалил рёбра с весом 1.

картинка кликабельна

Итак, из этого графа можно увидеть главных героев и их связь между собой. Как я и ожидал, Тирион Ланнистер находится в «центре» всех связей, от него исходят 4 большие ветки: Серсея Ланнистер, Джон Сноу, Санса Старк и Джорах Мормонт (ветка Дайнерис). Последние в свою очередь герои следующего уровня по связям. Вполне ожидаемый результат, не правда ли?

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

Мосты и шарниры

Мостами в графе называют рёбра, при удалении которых, количество компонент связности увеличивается. Аналогичное определение и у шарниров, только в отличии от мостов, шарниры это вершины, при удалении которых количество компонент связности возрастает. В данном графе, наличие мостов будет означать что в мире престолов существуют связи, которые являются единственным источником коммуникации между отдельными группами персонажей. Шарниры же, это герои, которые являются единственным посредником к группе других персонажей. Мосты и шарниры искать не очень тяжело. Для этого нам понадобится знакомый нам алгоритм поиска в глубину, но слегка модифицированный. Нужно использовать, так называемое, время входа в вершину и функцию времени выхода (fout) на вершине, которая будет принимать значения минимума времени входа и значений fout вершины в которую поиск в глубину пройден, таким образом, если при проходе ребра окажется, что значение функции fout на вершине больше чем время захода в неё, то это будет мостом, а так же и шарниром, а если равно, то только шарниром. Иными словами мы проверяем, возвращаемся ли мы после обхода в то же самое ребро/вершину и только в неё при обходе части графа, если да, то это и будет искомым мостом либо шарниром.

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

Минимальный разрез

Но всё же интересно узнать, сколько героев требуется «убить» чтобы полностью исключить контакт двух самых популярных (по вышеизложенной статистике) персонажей, скажем, Тириона Ланнистера и Арью Старк, либо Джона Сноу и Серсею Ланнистер. Для этого будем использовать алгоритм Диница. Для начала разберёмся как работает алгоритм.

По теореме Форда-Фалкерсона следует, что величина максимального потока в графе путей равна величине пропускной способности его минимального разреза. Иными словами, мы можем найти минимальный разрез между двумя вершинами (сток и исток) если найдём максимальный поток между этими вершинами. Алгоритм Диница как раз позволяет найти величину максимального потока и, собственно, сам поток. Я не буду разбирать подробно сам алгоритм и предоставлю вам возможность самим разобраться в нём. Для понимания полученного результата достаточно знать, что поток — это некая функция, которая для каждого ребра лежащего на пути от истока к стоку, определяет положительную величину, не превышающую пропускную способность этого ребра. Для упрощения можно представить систему труб с водой, где объем воды протекающей от истока к стоку в момент t и есть величина потока.

Поставленная мною задача слегка отличается от той, что решает алгоритм. Дело в том, что поток определяется на рёбрах, и если мы найдём минимальный разрез, то он «разрежет» граф по рёбрам, т.е. связям в графе, но нам ведь нужно разрезать граф не по рёбрам, а вершинам, т.е. персонажам. Чтобы решить эту задачу нужно подвергнуть граф небольшим изменениям. Раздвоим каждую вершину в графе, скажем вместо вершины v у нас получатся вершины v₁ и v₂, далее если между двумя вершинами v и u было ребро, то перенаправим v₁ в u₂, а u₁ в v₂, вместо ребра (u, v) получатся рёбра (v₁, u₂) и (u₁, v₂). И между каждыми раздвоенными вершинами v₁ и v₂ проведём ребро (v₂, v₁). В полученном, уже ориентированном, графе, все связи сохранятся, но там где раньше были вершины, появятся рёбра. Если вес этих ребер будет 1, а у всех остальных, скажем бесконечность (на практике можно использовать количество вершин в графе), то ребро между раздвоенными вершинами будет слабым звеном в графе и по принципу «предохранителя» не позволит пройти бОльшему потоку через себя, что даст возможность узнать количество вершин, которые нужно удалить, чтобы граф стал несвязным. А дальше запустим алгоритм Диница на полученном графе.

Сложность алгоритма O(n 2 m). Поэтому мы будем искать величину максимального потока не по всем парам вершин, а только по персонажам, которые имеют наибольшее количество связей, иначе для данного графа сложность получится O(n 5 ), где n=1000 и работать всё будет много часов. Ниже я приведу результаты по топ 100 персонажам по связям.

Я немного удивился результатам. Оказалось, что в топ 100, разрезать граф можно избавившись от минимум 6ти персонажей. Все такие связи при этом содержат либо Джона Коннингтона либо Эурона Грейджоя в качестве стока/истока. Но это не основные персонажи. Что интересно, в топ 10ти, в основном минимальный поток равен около 45ти. Например между Тирионом и Арьей поток равен 53, а между Джоном Сноу и Серсеей 42. Но есть и персонаж, которого можно отделить, удалив 16 других персонажей. Это Дайнерис Таргариен, не удивительно, ведь она наиболее удалённая героиня на карте престолов.

Ещё интересно было бы узнать, кто же наиболее «важный» герой в потоках. Т.е. через кого чаще всего протекает максимальный поток. Тут есть чему удивиться. Топ 10 важных персонажей в потоках (в скобках соответствующее количество вхождений в потоки):

Тирион Ланнистер (4109)
Джейми Ланнистер (3067)
Арья Старк (3021)
Джон Сноу (2883)
Эддард Старк (2847)
Серсея Ланнистер (2745)
Теон Грейджой (2658)
Бриенна (2621)
Сандор Клегане (2579)
Санса Старк (2573)

11. Джофрей Ланнистер
12. Робб Старк
13. Ренли Баратеон
14. Кейтилин Старк
15. Русе Болтон
16. Йорен
17. Сэм
18. Мелисандра
19. Бран Старк
20. Варис

где из верхних 6ти персонажей в книге уже убиты 5. Не позавидуешь этой десятке. Кто же следующий?

Так же, благодаря потокам, удалось вычислить «лишние» вершины, авторов реплик которых не удалось правильно распознать, поэтому они были связаны со многими персонажами, с которыми не должны были пересекаться. Ими оказались Человек (A Man) и Страж (A Guard). В следствии чего, я удалил эти вершины и пересчитал всю статистику заново.

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

Ссылки:

Проект на GitHub
Исходный социальный граф
Программа Gephi, с помощью которого можно открыть проект
Автор фото заголовка — Adam Foster

В конце, как и обещал, опросник: стоит ли переводить статью о том, как были определены авторы диалогов в книгах?

Алгоритм Штор-Вагнера нахождения минимального разреза

[math]G[/math] — неориентированный взвешенный граф с [math]n[/math] вершинами и [math]m[/math] рёбрами.

[math]A, B \subset V[/math] ;
[math]A, B \neq \emptyset[/math] ;
[math]A \cap B = \emptyset[/math] ;
[math]A \cup B = V[/math] .

[math]w(A, B) =[/math] [math]\sum\limits_ w(u, v)[/math]

Эту задачу называют «глобальным минимальным разрезом». Глобальный минимальный разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью любого алгоритма нахождения максимального потока (запуская его [math]O(n^2)[/math] раз для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый алгоритм, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г.

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

Идея алгоритма довольно проста. Будем [math]n-1[/math] раз повторять следующий процесс: находить минимальный разрез между какой-нибудь парой вершин [math]s[/math] и [math]t[/math] , а затем объединять эти две вершины в одну (создавать новую вершину, список смежности которой равен объединению списков смежности [math]s[/math] и [math]t[/math] ). В конце концов, после [math]n-1[/math] итерации, останется одна вершина. После этого ответом будет являться минимальный среди всех [math]n-1[/math] найденных разрезов. Действительно, на каждой [math]i[/math] -ой стадии найденный минимальный разрез [math]\langle A,B \rangle[/math] между вершинами [math]s_i[/math] и [math]t_i[/math] либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины [math]s_i[/math] и [math]t_i[/math] невыгодно относить к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну.

Следовательно нам необходимо для данного графа найти минимальный разрез между какой-нибудь парой вершин [math]s[/math] и [math]t[/math] . Для этого вводим некоторое множество вершин [math]A[/math] , которое изначально содержит единственную произвольную вершину [math]s[/math] . На каждом шаге находится вершина, наиболее сильно связанная с множеством [math]A[/math] , т.е. вершина [math]v \not\in A[/math] , для которой следующая величина [math]w(v,A) = \sum\limits_ <(v,u) \in E, \atop u \in A>w(v,u)[/math] максимальна (максимальна сумма весов рёбер, один конец которых [math]v[/math] , а другой принадлежит [math]A[/math] ). Этот процесс завершится, когда все вершины перейдут в множество [math]A[/math] .

Рассмотрим произвольный [math]s[/math] — [math]t[/math] разрез [math]C[/math] и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины [math]t[/math] :

Пусть [math]v[/math] — вершина, которую мы хотим добавить в [math]A[/math] , тогда [math]A_v[/math] — состояние множества [math]A[/math] в этот момент. Пусть [math]C_v[/math] — разрез множества [math]A_v \cup v[/math] , индуцированный разрезом [math]C[/math] . Вершина [math]v[/math] — активная, если она и предыдущая добавленная вершина в [math]A[/math] принадлежат разным частям разреза [math]C[/math] , тогда для любой такой вершины:

[math]w (v, A_v) \le w (C_v)[/math] .

[math]t[/math] — активная вершина, для неё выполняется:

[math]w (t,A_t) \le w (C_t)[/math] [math]w (t,A_t) = w (\), w (C_t) = w (C)[/math]

Получили утверждение теоремы. Для доказательства воспользуемся методом математической индукции. Для первой активной вершины [math]v[/math] это неравенство верно, так как все вершины [math]A_v[/math] принадлежат одной части разреза, а [math]v[/math] — другой. Пусть неравенство выполнено для всех активных вершин до [math]v[/math] , включая [math]v[/math] , докажем его для следующей активной вершины [math]u[/math] .

[math] w (u,A_u) \equiv w (u,A_v) + w (u,A_u \setminus A_v)[/math] (*)

[math]w (u,A_v) \le w (v,A_v)[/math] (**)

вершина [math]v[/math] имела большее значение [math]w[/math] , чем [math]u[/math] , так как была добавлена в [math]A[/math] раньше. По предположению индукции:

[math]w (v,A_v) \le w (C_v)[/math]

[math]w(u,A_v) \le w(C_v)[/math]

[math]w (u,A_u) \le w (C_v) + w (u,A_u \setminus A_v)[/math]

Вершина [math]u[/math] и [math]A_u \setminus A_v[/math] находятся в разных частях разреза [math]C[/math] , значит [math]w (u,A_u \setminus A_v)[/math] равна сумме весов рёбер, которые не входят в [math]C_v[/math] , но входят в [math]C_u[/math] .

Нахождение вершины с наибольшей [math]w[/math] за [math]O (n)[/math] , [math]n-1[/math] фаза по [math]n-1[/math] итерации в каждой. В итоге имеем [math]O (n^3)[/math]
Если использовать фибоначчиевы кучи для нахождения вершины с наибольшей [math]w[/math] , то асимптотика составит [math]O (nm + n^2 \log n)[/math]
Если использовать двоичные кучи, то асимптотика составит [math]O (nm \log n + n^2)[/math]

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

Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает «разницу» между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости Normalized Cut (J. Shi, J. Malik (1997))