Обход графов

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

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

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

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

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

Постановка задачи определения минимального пути обхода графа

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

1. Определение самого короткого маршрута обхода к выбранному пункту назначения. Необходимо сформировать самый короткий путь обхода к пункту назначения, вершине t. Начальной точкой пути может служить любая из вершин графа, за исключением вершины t. А когда изменяется направление всех ребер графа, то задача может быть сведена к задаче о единой начальной точке и в ней необходимо определить самый короткий путь обхода из исходной точки во все другие.
2. Определение самого короткого пути обхода между заданной парой точек. То есть, следует найти минимальный маршрут из точки U в точку V.
3. Определение самых коротких путей обхода между всеми парами вершин. То есть, нужно найти самый короткий путь обхода из каждой точки U в каждую точку V. Подобную задачу можно решить с помощью алгоритма, предназначенного для решения задачи с одной начальной точкой, но имеется возможность разрешить ее более оперативно.

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

1. Необходимо определить наиболее короткий путь обхода графа, проходящий через требуемые вершины. В данном случае можно выделить следующие возможные ограничивающие факторы: путь обхода, имеющий минимальную длину, обязан проходить через выделенные вершины, и минимальный путь обхода должен содержать наименьшее количество невыделенных вершин.
2. Необходимо определить наиболее короткий путь обхода, но при минимальном покрытии вершин ориентированного графа путями.
3. Требуется найти наименьшее по мощности количество путей.
4. Требуется определить наименьшее по числу путей обхода подмножество всех маршрутов, но при этом любая из дуг обязана принадлежать хотя бы одному из них.

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

1. Алгоритм Дейкстры позволяет определить наикратчайший путь обхода из одной вершины графа ко всем другим его вершинам. Данный алгоритм является справедливым только для графов, не имеющих ребер с отрицательным весом.
2. Алгоритм Беллмана - Форда позволяет определить минимальный путь обхода от одной вершины графа ко всем остальным вершинам во взвешенном графе. В этом случае ребра могут обладать и отрицательным весом.