Практическое применение теории графов
Поиск в ширину
Поиск в ширину
Поиск в глубину
Поиск в глубину
Кратчайший путь
Кратчайший путь
Обнаружение циклов
Обнаружение циклов
Минимальное остовное дерево
Минимальное остовное дерево
Сильно связные компоненты
Сильно связные компоненты
Топологическая сортировка
Топологическая сортировка
Раскраска графов
Раскраска графов
Максимальный поток
Максимальный поток
Паросочетания
Паросочетания
3.14M
Категория: ПрограммированиеПрограммирование

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

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 Паросочетания двудольного графа
English     Русский Правила