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

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

Графы являются основным объектом изучения теории графов.

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.

 

1. Создание ориентированного графа

Первое, что вам вероятно нужно изучить с точки зрения программирования с Boost graph, это использование списка смежности для создания соединений ребер графа. Вероятно, стоит привыкнуть к использованию typedef, учитывайте объявления Boost могут оказаться длинными.

Объявление списка смежности для ориентированного графа, пример:

Предположим, мы хотим построить следующий взвешенный ориентированный граф:

Мы можем сделать это, делая повторные вызовы add_edge для создания графа. В следующем коде показано, как это можно сделать (не забудьте про -lboost_thread -lboost_system при сборке проекта) :

Спискок смежности

Получаем следующий результат:

Количество ребер = 5
Лист ребер:
(0,1)
(0,2)
(0,3)
(1,3)
(2,3)

2. Создание неориентированного графа

Пример неориентированного графа

Который мы строим аналогичным образом, но на этот раз предусматривая использование свойства boost:: undirectedS:

Получаем следующий результат:

Количество ребер = 10
Список ребер:
(0,1)
(0,7)
(7,2)
(7,8)
(2,8)
(8,6)
(8,3)
(6,5)
(5,4)
(3,4)

3. Вывод веса ребер неориентированного графа

Рассмотрим следующее связующее дерево:

Получите отображение между ребрами и их соответствующими весами с помощью boost_property_map:

Полный код:

(0,1) 1
(0,2) 2
(1,2) 9
(0,3) 8
(1,3) 5
(2,3) 7
(3,4) 6
(3,5) 7

4. Нахождение минимального пути, алгоритм Дейкстры

Алгоритм Дейкстры  — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

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

Находим короткий путь между узлами A и F.

Путь A -> F
A E F

5. Поиск минимальных остовных деревьев с использованием алгоритма Крускала

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

Минимальное остовное дерево:
4 < —> 2 вес 1
5 < —> 0 вес 1
3 < —> 2 вес 2
0 < —> 1 вес 2
5 < —> 3 вес 3

6. Проблема максимального потока DIMACS

DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) — центр дискретной математики и теоретической информатики.

В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.

Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.

Пример задачи о максимальном потоке.

dimacs.txt

Строки, начинающиеся с «c», являются строками комментариев. Строка задачи начинается с буквы «p» и представляет обозначение задачи (max, min и т. д.), количество ребер (8) и количество вершин (6). Строки, начинающиеся с «n», являются дескрипторами узла-идентификатора — узел ID и является ли узел источником («s») или приемником («t»). Наконец, строки «a» являются дескрипторами, дающими взаимосвязи узлов и их весового значения. В следующем графическом представлении примера задачи сетевого потока показаны не только сетевые соединения и веса, но и потоки на каналах:

c Общий поток:
s 15

c значения потока:
f 0 1 5
f 0 2 10
f 1 3 5
f 1 4 0
f 2 3 5
f 2 4 5
f 3 5 10
f 4 5 5

Как и предполагалось, вектор решения выходных переменных составляет [5, 10, 5, 0, 5, 5, 10, 5].

Отправить ответ

avatar

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

  Subscribe  
Уведомлять о