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

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

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

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

G = (X, A, С),

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

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

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

Пример такого графа приведен на рис. 8.2,а. При рассмотрении пути M, представленного последовательностью дуг(a₁, a₂,..., a_q), за его вес (или длину, или стоимость) принимается число L(M), равное сумме весов всех дуг, входящих в путь, т. е. L(M)= (c_i) для всех a_i M.

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

Рис. 8.2. Взвешенные графы: а – граф со взвешенными дугами; б – граф со взвешенными вершинами; в – взвешенный граф

Граф со взвешенными вершинами – это граф, описываемый тройкой G = (X, А, V), где Х = { х_i }, i = 1, 2,..., n – множество вершин графа;

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

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

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

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

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

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

М₁: a₃, a₆, a₁₁,

М₂: a₁₁, a₃, a₄, a₇, a₁, a₁2, a₉,

М₃: a₃, a₄, a₇, a₁₀, a₉, a₁₁.

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

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

Рис. 8.3. Орциклы в графе

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

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

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

Основная теорема о существовании эйлерова цикла формулируется так.

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

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

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

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

Рис. 8.4. а – схема Кенигсбергских мостов; б – эквивалентный граф