Пути и циклы в графах

Пути и маршруты

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

Например, для графа на последовательности дуг

M₁: a₆, a₅, a₉, a₈, a₄ ,

M₂: a₁, a₆, a₅, a₉, a₇ ,

M₃: a₁, a₆, a₅, a₉, a₁₀, a₆, a₄

являются путями. Пути могут быть различными.

Орцепью (или простым путем) называется такой путь, в котором каждая дуга используется не более одного раза.

Так пути M1 и M2 являются орцепями, а M3 нет, поскольку дуга a6 используется дважды.

Простой орцепью (или элементарным путем) называется путь, в котором каждая вершина используется не более одного раза.

Простой орцепью является путь M2 .

Для неориентированного графа понятия маршрута, цепи и простой цепи аналогичны понятиям пути, орцепи и простой орцепи в орграфе. (В определениях следует заменить слово "дуга" на слово "ребро").

Путь или маршрут можно изображать также последовательностью вершин. Так путь M1 можно представить последователь-ностью вершин х2, х5, х4, х3, х5, х6 , и такое представление часто оказывается более полезным.

Вес и длина пути

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

Граф G, описываемый тройкой вида

G = (X, A, С),

где Х = { хi }, i =1, 2, 3, ..., n – множество вершин,

А = { ai }, i = 1, 2, 3, ..., m – множество дуг,

С = {Ci}, i = 1, 2, 3, ..., m – множество характеристик дуг, называется графом со взвешенными дугами.

Пример такого графа приведен на ,а. При рассмотрении пути M, представленного последовательностью дуг (a1, a2, ..., aq), за его вес (или длину, или стоимость) принимается число L(M), равное сумме весов всех дуг, входящих в путь, т. е. $$L(M)=\sum (c_{i})$$ для всех $$a_{i} \in M$$.

Длиной (или мощностью ) пути называется число дуг, входящих в него. Чаще всего термин "длина" употребляется, когда все дуги, входящие в путь, имеют веса, равные 1, т. е. когда вес пути совпадает с его длиной (мощностью).

Граф со взвешенными вершинами – это граф, описываемый тройкой

G = ( X, А, V ),

где Х = { хi }, i = 1, 2, ..., n – множество вершин графа;

А = { ai }, i = 1, 2, ..., m – множество дуг графа;

V ={ vi }, i = 1, 2, ..., n – множество характеристик вершин.

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

И наконец, взвешенный граф определяется четверкой вида G = (Х, А, V, С), т. е. и дуги, и вершины этого графа имеют некоторые характеристики.

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

Орциклы и циклы

Особую группу составляют замкнутые пути. Путь a1, a2, ...,aq называется замкнутым, если в нем начальная вершина a₁ и конечная вершина aq совпадают. Так, например, для графа на можно составить несколько замкнутых путей:

М1: a3, a6, a11,

М2: a11, a3, a4, a7, a1, a12, a9,

М3: a3, a4, a7, a10, a9, a11.

Пути М1 и М3 являются замкнутыми простыми орцепями, называемыми контурами или простыми орциклами, поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной). Путь М2 не является контуром, так как вершина х1 используется в нем дважды.

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

Для неориентированного графа замкнутым маршрутом является неориентированный двойник замкнутого пути, т. е. замкнутым маршрутом является маршрут, в котором совпадают начальные и конечные вершины.

Для неориентированного графа понятия цикла и гамильтонова цикла аналогичны понятиям орцикла и гамильтонова контура в орграфе.

Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Граф, содержащий эйлеров цикл, называется эйлеровым графом.

Эйлеровым путем в графе называется путь, содержащий все ребра графа по одному разу. Граф, содержащий эйлеров путь, называется полуэйлеровым графом.

ТЕОРЕМА. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно нулю 0.

ТЕОРЕМА. Связный неориентированный граф G содержит эйлеров путь тогда и только тогда, когда число вершин нечетной степени равно нулю 0 или 2.

Эйлер первым в своей знаменитой задаче о Кенигсбергских мостах поставил вопрос о существование такого цикла.

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

Если каждый берег реки и острова считать вершинами графа, а каждый мост – ребром, то карту ,а можно представить в виде графа на рис. ,б и ответ на поставленный вопрос зависит теперь от существования эйлерова цикла в этом графе. Эйлер установил, что указанный граф не содержит эйлерова цикла, и этот результат ознаменовал рождение теории графов.