Задачи, которые можно решить с помощью графов

Типичные задачи Теории Графов

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

Поиск кратчайшего пути

Одной из таких задач является поиск кратчайшего пути.

Например алгоритм Дейкстры находит кратчайший путь из одной вершины до другой, если он существует. Стоит отметить, что этот алгоритм не работает с графами, где есть циклы с отрицательным весом дуг.
Алгоритм Беллмана — Форда может искать кратчайший путь в графах и с отрицательным весом дуг, но он медленнее, чем алгоритм Дейкстры.
Например, Алгоритм поиска A* часто используется в компьютерных играх. Так как в алгоритме А* используется эвристическое правило, он не всегда найдёт самый короткий пусть, но найдёт близкий к самому короткому. Алгоритм поиска A* работает быстрее алгоритма Дейкстры.

Таким образом, алгоритмов поиска кратчайшего пути много и каждый из них обладает своей особенностью. Сервис Graphonline использует алгоритмы Дейкстры и с его помощью можно найти кратчайший путь до вершины и минимальное расстояние до всех остальных вершин.

Поиск максимального потока

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

Сервис Graphonline использует алгоритм Проталкивания Предпотока. Например, если у вас есть граф, где вершины это - города, а вес дуг задаёт пропускную способность дорог между городами (например автомобилей в час), то можно легко посчитать сколько машин может доехать из города А в город N за час.

Поиск минимального остовного дерева

Алгоритм ищет дерево минимального веса в графе, которое бы соединяло все вершины. Этот алгоритм можно применять для дорожной или компьютерной сети, где вы хотите оптимизировать стоимость.

Предположим, имеются 7 компьютеров и разные способы проложить локальную сеть. Используя алгоритм поиска минимального остовного дерева, можно легко посчитать, где стоит проложить кабель, чтобы понадобилось минимальное количество кабеля.

Прикладные задачи, решаемые с помощью Теории Графов

Распределение рабочих

В распоряжении имеются N работников и M различных типов работ. Разные работники могут выполнять разные типы работ. Необходимо распределить работников, чтобы максимальное количество из их было занято.

Для решения строим граф, где соединяем работников с теми работами, которые они могут выполнять. Создаём псевдоисток, который соединяется со всеми работниками и сток, с которым соединены все типы работ. После этого ищем максимальный поток от истока к стоку.

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

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

Самый быстрый способ

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