Многие вычислительные приложения естественным образом используют не только набор элементов (items), но также и набор соединений (connections) между парами таких элементов. Отношения, которые вытекают из этих соединений, немедленно вызывают множество естественных вопросов. Существует ли путь от одного такого элемента к другому, вдоль этих соединений? В какие другие элементы можно перейти из заданного элемента? Какой путь от одного элемента к другому считается наилучшим?

Чтобы смоделировать подобную ситуацию и ответить на вопросы, аналогичные сформулированным выше, мы пользуемся объектами, которые называются графами {graphs). Теория графов, будучи крупной ветвью комбинаторной математики, интенсивно изучалась в течение не одной сотни лет. Было выявлено много важных и полезных свойств графов, однако многие задачи еще ждут своего решения.

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

В первом разделе обсуждаются алгоритмы, основанные на обходе графа в ширину и в глубину.

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

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

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

При описании времени работы алгоритма над данным графом G = (V, Е) мы обычно определяем размер входного графа в терминах количества его вершин |V| и количества ребер |Е| графа, т.е. размер входных данных описывается двумя, а не одним параметром. Для удобства и краткости в вычислениях сложности алгоритма символ V будет означать |V|, а символ Е — |Е|. Такое соглашение позволяет сделать формулы для времени работы более удобочитаемыми без риска неоднозначности.

[вверх]