Практическое применение теории графов

1. Практическое применение теории графов

ПРАКТИЧЕСКОЕ
ПРИМЕНЕНИЕ
ТЕОРИИ ГРАФОВ
ЛЕКЦИЯ 8
ГРАФОВЫЕ АЛГОРИТМЫ

2.

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

3. Поиск в ширину

ПОИСК В ШИРИНУ
Обход или поиск — это одна из фундаментальных операций, выполняемых на
графах.
Поиск в ширину начинается с определённой вершины, затем исследуются все её соседи на
данной глубине и происходит переход к вершинам следующего уровня. В графах, в отличие от
деревьев, могут быть циклы — пути, в которых первая и последняя вершины совпадают.
Поэтому необходимо отслеживать посещённые алгоритмом вершины. При реализации
алгоритма поиска в ширину используется структура данных «очередь».
На рисунке 1 показан пример того, как выглядит поиск в ширину на графе.
Жёлтым цветом помечаются обнаруженные вершины, красным — посещённые.
Применяется для:
• определения кратчайших путей и минимальных остовных деревьев;
• индексации веб-страниц поисковыми ботами;
• поиска в соцсетях;
• нахождения доступных соседних узлов в одноуровневых сетях,
таких как BitTorrent.

4. Поиск в ширину

ПОИСК В ШИРИНУ
Рис. 1 Визуальное отображение обхода на графах (поиск в ширину)

5. Поиск в глубину

ПОИСК В ГЛУБИНУ
Поиск в глубину начинается с определённой вершины, затем уходит как можно
дальше вдоль каждой ветви и возвращается обратно.
Здесь тоже необходимо отслеживать посещённые алгоритмом вершины. Для того,
чтобы стало возможным возвращение обратно, при реализации алгоритма поиска в
глубину используется структура данных «стек».
На рисунке 2 показан пример того, как выглядит поиск в глубину на том же графе,
который использован на рисунке 1. Граф обходится на всю глубину каждой ветви с
возвращением обратно.
Применяется:
• для нахождения пути между двумя вершинами;
• для обнаружения циклов на графе;
• в топологической сортировке;
• в головоломках с единственным решением (например, лабиринтах).

6. Поиск в глубину

ПОИСК В ГЛУБИНУ
Рис. 2 Визуальное отображение обхода на графах (поиск в глубину)

7. Кратчайший путь

КРАТЧАЙШИЙ ПУТЬ
Кратчайший путь от одной вершины графа к другой — это путь, при котором сумма весов рёбер,
его составляющих, должна быть минимальна.
На рисунке 3 показан кратчайший путь на графе от вершины 1 до вершины 6.
Алгоритмы нахождения кратчайшего пути:
• Алгоритм Дейкстры.
• Алгоритм Беллмана-Форда.
• Алгоритм поиска A*
• Алгоритм Флойда — Уоршелла
• Алгоритм Джонсона
• Алгоритм Ли (волновой алгоритм)
• Поиск кратчайшего пути на основе алгоритма Килдала.
Применяются в:
• картографических сервисах типа Google maps или Apple maps для прокладки маршрутов и
определения местоположения;
• сетях для решения проблемы минимальной задержки пути;
• абстрактных автоматах для определения через переход между различными состояниями
возможных вариантов достижения некоторого целевого состояния, например минимально
возможного количества ходов, необходимого для победы в игре.

8. Кратчайший путь

КРАТЧАЙШИЙ ПУТЬ
Рис. 3 Визуальное отображение кратчайшего пути от вершины 1 к вершине 6

9. Обнаружение циклов

ОБНАРУЖЕНИЕ ЦИКЛОВ
Цикл — это путь, в котором первая и последняя вершины графа совпадают.
То есть путь, начинающийся и завершающийся в одной и той же вершине, называется
циклом.
Обнаружение циклов — это процесс выявления таких циклов.
На рисунке 4 показано, как происходит обнаружение цикла.
Алгоритмы обнаружения цикла:
• Алгоритм Флойда.
• Алгоритм Брента.
Применяются:
• в распределённых алгоритмах, использующих сообщения;
• для обработки крупных графов с использованием распределённой системы
обработки в кластере;
• для обнаружения взаимоблокировок в системах с параллельным выполнением;
• в криптографических приложениях для выявления ключей сообщения, которые
могут соответствовать одному и тому же зашифрованному значению.

10. Обнаружение циклов

ОБНАРУЖЕНИЕ ЦИКЛОВ
Рис. 4 Цикл

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

МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО
Минимальное остовное дерево — это подмножество рёбер графа, которое
соединяет все вершины, имеющие минимальную сумму весов рёбер, и без циклов.
На рисунке 5 показан процесс получения минимального остовного дерева.
Алгоритмы поиска минимального остовного дерева: (мы их не берем, почему?)
• Алгоритм Прима.
• Алгоритм Крускала.
Применяются:
• для создания деревьев для распределения данных в компьютерных сетях;
• в кластерном анализе с использованием графов;
• при сегментации изображений;
• при социально-географическом районировании, когда смежные регионы
объединяются.

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

МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО
Рис. 5 Визуальное отображение минимального остовного дерева

13. Сильно связные компоненты

СИЛЬНО СВЯЗНЫЕ КОМПОНЕНТЫ
Граф считается сильно связным, если все вершины в графе достижимы из всех
остальных вершин.
На рисунке 6 показан пример того, как выглядит граф с тремя сильно связными
компонентами, вершины которых окрашены в красный, зелёный и жёлтый цвета.
Алгоритмы поиска сильных компонент связности:
• Алгоритм Косараджу.
• Алгоритм Тарьяна.
Применяются:
• для вычисления декомпозиции Далмейджа-Мендельсона, которая представляет
собой разделение вершин двудольного графа на подмножества;
• в соцсетях для поиска групп сильно связанных между собой людей и выдачи
рекомендаций на основе общих интересов.

14. Сильно связные компоненты

СИЛЬНО СВЯЗНЫЕ КОМПОНЕНТЫ
Рис. 6 Сильно связные компоненты

15. Топологическая сортировка

ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА
Топологическая сортировка графа — это такое линейное упорядочение его вершин, в
котором для каждого направленного ребра, например (u, v), вершина u предшествует
вершине v.
На рисунке 7 показан пример топологического упорядочения вершин, согласно которому
вершина 5 должна следовать за вершинами 2 и 3, а вершина 6 — за вершинами 4 и 5.
Алгоритмы поиска топологической сортировки:
• Алгоритм Кана.
• Алгоритм на основе поиска в глубину.
Применяются:
• при планировании выполнения команд;
• при сериализации данных;
• определения порядка выполняемых при компиляции задач в Makefiles;
• для разрешения зависимостей символов в компоновщиках.

16. Топологическая сортировка

ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА
Рис. 7 Топологическая сортировка

17. Раскраска графов

РАСКРАСКА ГРАФОВ
При раскраске графов элементам графа присваиваются цвета с учётом определённых условий.
Раскраска вершин — наиболее часто используемый метод окраски графов.
При этом вершины графа окрашиваются с использованием k цветов,
а любым двум соседним вершинам должны соответствовать
разные цвета.
Другие методы окраски — раскраска рёбер и раскраска граней.
Хроматическое число графа — это наименьшее количество
цветов, необходимых для окрашивания графа.
На рисунке 8 показан пример того, как выглядит
раскраска вершин графа с использованием 4-х цветов.
Алгоритмы с раскраской графов:
• Алгоритмы, использующие поиск в ширину или поиск в глубину.
• Жадная раскраска.
Применяются для:
составления расписаний;
назначения радиочастот мобильных сетей;
моделирования и решения головоломок типа судоку;
проверки того, является ли граф двудольным;
раскрашивания географических карт стран или штатов, на которых соседние страны или штаты имеют разные цвета.

18. Раскраска графов

РАСКРАСКА ГРАФОВ
Рис. 8 Раскраска вершин

19. Максимальный поток

МАКСИМАЛЬНЫЙ ПОТОК
Можно смоделировать граф в виде сети потоков с весами рёбер в качестве пропускной
способности этих потоков.
В задаче максимального потока требуется найти такой путь потока, который может
обеспечить максимально интенсивность потока.
На рисунке 9 показан пример того, как выглядит нахождение максимального потока сети
и определение конечного значения потока.
Алгоритмы нахождения максимального потока:
• Алгоритм Форда-Фулкерсона.
• Алгоритм Эдмондса-Карпа.
• Алгоритм Диница.
Применяются:
•в авиакомпаниях для составления полётного расписания экипажей;
•при сегментации изображений для определения фона и переднего плана изображения.

20. Максимальный поток

МАКСИМАЛЬНЫЙ ПОТОК
Рис. 9 Определение максимального потока

21. Паросочетания

ПАРОСОЧЕТАНИЯ
Паросочетание на графе — это набор рёбер, которые не имеют общих вершин (т.е. хотя бы
двух рёбер, не имеющих общей вершины).
Паросочетание называется максимальным, если оно содержит максимально возможное
число рёбер, сочетающихся с как можно большим количеством вершин.
На рисунке 10 показано получение полного паросочетания в двудольном графе с двумя
наборами вершин, обозначенных оранжевым и синим цветами.
Алгоритмы нахождения паросочетаний:
• Алгоритм Хопкрофта-Карпа.
• Венгерский алгоритм.
• Алгоритм сжатия цветков.
Применяются:
• в подборе пары для жениха или невесты (задача о стабильных браках);
• для определения вершинного покрытия;
• в теории транспорта для решения задачи распределения ресурсов и оптимизации
перевозок.

22. Паросочетания

ПАРОСОЧЕТАНИЯ
Рис. 10 Паросочетания двудольного графа