Задача о путях во взвешенных ориентированных графах

Среди задач анализа ориентированных графов весьма важ- важны следующие задачи.

1. Вычисление для заданного ориентированного графа его матрицы достижимости. Эту задачу будем называть задачей построения транзитивного замыкания ванного графа. Такое название связано с тем, что матрицу достижимости можно рассматривать как матрицу транзитивного и рефлексивного замыкания бинарного отношения непосредственной достижимости в ориентированном графе.
2. Вычисление наименьших расстояний между всеми парами вершин в ориентированном графе. Эту задачу будем называть задачей о кратчайших расстояниях. Задачу о кратчайших расстояниях можно сформулировать так. Пусть задан взвешенный ориентированный граф и пусть из вершины v достижима вершина w. Фиксируем какой-либо путь S, ведущий из v в w. Расстоянием от вершины v до вершины w по пути S называют сумму меток дуг, входящих в этот путь, а наименьшим — минимальное из расстояний между вершинами v и w по всем возможным путям.
   Отметим, что задача о кратчайших расстояниях не всегда имеет решение. Например, если в ориентированном графе есть петля, метка которой — отрицательное число, то по этой петле можно проходить сколько угодно раз и тем самым уменьшать сумму меток дуг пути, включающего эту петлю, до любого наперед заданного значения.
3. Перечисление всех путей между двумя произвольными вершинами. Эту задачу будем называть задачей о перечислении путей. При ее решении требуется для любой заданной пары вершин u и v ориентированного графа получить все пути, для которых u является началом, а v — концом.

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

Ранее мы ввели понятие взвешенного неориентированного (ориентированного) графа и метки ребер (дуг) определили как числа, поставленные в соответствие ребру (дуге). Обобщим это понятие для ориентированного графа.

Определение 5.13. Взвешенным (или размеченным) ориентированным графом называют пару W = (G, φ), где G = (V, Е) — обычный ориентированный граф, а φ: Е → R — весовая функция (или функция разметки) со значениями в некотором идемпотентном полукольце R = (R, +, ⋅, 0, 1), причем (∀e ∈ Е)(φ(е) ≠ 0).

Мы будем в этом случае также говорить, что ориентированный граф размечен над идемпотентным полукольцом R. Часто полукольцо R является замкнутым, хотя это требование необязательно. Будем, однако, везде в этом пункте предполагать, что R — полукольцо с итерацией.

Пусть вершины ориентированного графа каким-либо образом пронумерованы. Тогда взвешенный ориентированный граф может быть задан матрицей А, элемент которой a_ij равен значению φ((i,j)) весовой функции на дуге (i, j), если из вершины i ведет дуга в вершину j, или нулю полукольца в противном случае. Эту матрицу будем называть матрицей меток дуг.

Оказывается, что вычисление итерации А* матрицы А дает решение всех сформулированных выше задач, если для каждой задачи выбирать соответствующее полукольцо. А именно в случае полукольца В (см. пример 3.2) получаем решение задачи о транзитивном замыкании, в случае полукольца R⁺ (см. пример 3.1) — решение задачи о кратчайших расстояниях*.

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

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

*О методе решения третьей из сформулированных выше задач см. задачу 7.36.

Рассмотрим теперь решение общей задачи о путях для произвольного замкнутого полукольца R.

Метка пути, ведущего из вершины v_i в вершину v_j, есть произведение в полукольце R меток входящих в путь дуг в порядке их следования (для пути ненулевой длины) и есть 1 (единица полукольца R) для пути нулевой длины.

Стоимость прохождения из вершины v_i в вершину v_j (или между i-й и j-й вершинами) — это сумма в полукольце R меток всех путей, ведущих из вершины v_i в вершину v_j.

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

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

Матрица меток дуг является элементом полукольца матриц над полукольцом R. В этом полукольце определены операции сложения и умножения матриц, а также возведение матрицы в неотрицательную степень. Докажем следующее утверждение.

Лемма 5.1. Элемент ^(l)ij матрицы А^l, l ≥ 0, равен стоимости прохождения из вершины v_i в вершину v_j по всем путям длины l.

◀ Доказательство проведем индукцией по l. При l = 0 утверждение очевидно, так как А⁰ = Е, где Е — единичная матрица, которая будет матрицей стоимости прохождения по всем путям длины 0.

При l = 1 утверждение также очевидно. Далее,

Согласно предположению индукции, элемент а^(l-1)ik равен стоимости прохождения из вершины v_i в вершину v_k по всем путям длины l-1. Множество всех путей длины l из вершины v_i в вершину v_j, проходящих через фиксированную k-ю вершину так, что вершина v_k связана дугой с вершиной v_j (v_k → v_j,) образуется путем присоединения дуги (v_k, v_j) к каждому из путей, ведущих из v_i в v_k и имеющих длину l - 1.

Тогда видно, что написанное выше выражение для элемента (l)ij дает стоимость прохождения из вершины vi в вершину vj по всем путям длины l (рис. 5.26). ▶

Так как стоимость прохождения между парой вершин (v_i,v_j) равна сумме меток всех путей, ведущих из первой вершины во вторую, а указанную сумму можно можно получить, суммируя последовательно метки путей длины 0, длины 1, длины 2 и т.д., то матрица стоимостей взвешенного ориентированного графа с учетом доказанной леммы 5.1 может быть представлена в виде

До сих пор мы рассматривали матрицы над замкнутым полукольцом. Однако, если элементы матрицы А принадлежат некоторому полукольцу с итерацией, из теоремы 3.9 следует, что и все элементы матрицы стоимостей С = А* останутся в этом же полукольце. Таким образом, полученные результаты можно перенести на произвольное полукольцо с итерацией.

Теорема 5.4. Матрица стоимостей ориентированного графа G, размеченного над полукольцом с итерацией R (в частности, над замкнутым полукольцом), равна итерации матрицы А меток дуг ориентированного графа G. #

Для вычисления С = А* достаточно решить (т.е. найти наименьшее решение) в R при всех j = 1,n систему уравнений

ξ = A ξ + ε_j,

где ε_j ∈ Rⁿ — j-й единичный вектор, т.е. вектор, все элементы которого, кроме j-ro, равны 0, a j-й равен единице полукольца R. Наименьшее решение имеет вид ξ = A*ε_j (см. 3.3). Тогда столбец ξ = A*ε_j есть j-й столбец матрицы А*. Такой метод вычисления матрицы А* аналогичен известному из линейной алгебры методу элементарных преобразований при вычислении обратной матрицы.

Выясним теперь смысл матрицы стоимостей С = А* для полуколец В и R⁺.

В первом из этих полуколец метка отдельного пути всегда равна 1 (так как метка дуги в размеченном над полукольцом графе не может, согласно определению, быть нулем полукольца). Следовательно, стоимость с_ij = 1, если существует хотя бы один путь из i-й вершины в j-ю, и с_ij = 0, если иначе. Другими словами, для полукольца с_ij матрица стоимостей совпадает с матрицей достижимости ориентированного графа.

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

Пример 5.9. Рассмотрим граф, изображенный на рис. 5.27, и решим для него задачу вычисления матрицы достижимости. На числовые метки дуг внимания пока не обращаем, считая, что ориентированный граф размечен над полукольцом В и метка каждой дуги равна 1, т.е. ориентированный граф задан матрицей

Запишем систему уравнений в полукольце В для определения первого столбца матрицы А*

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

Воспользуемся методом последовательного исключения неизвестных (см. 3.3). Поскольку в правой части первого уравнения нет переменной х₁, можно исключить эту переменную из системы, подставив в остальные уравнения. С учетом идемпотентности сложения получим

Из второго уравнения имеем х₂ = 1*(x₃ + 0). В полукольце В итерация любого элемента равна единице полукольца. Поэтому х₂ = х₃ + 0. Исключив х₂ из системы, получим

Далее вычислим х₃ = 1*0 = 1 ⋅ 0 = 0. Подставив х₃ = 0 в последнее уравнение, найдем х₄ = 1*1 = 1.

Итак, первый столбец А* есть

Второй столбец определяется из системы

Исключая х₁, получаем

Из второго уравнения имеем х₂ = 1*(х₃ + 1) = х₃ + 1. Далее находим

Отсюда х₃ = 1*1 = 1 и х₄ = х₄ +1. В итоге х₄ = 1*1 = 1, х₂ = 1 + 1 = 1, х₁ = 1 + 1 + 1 + 0 = 1. Таким образом, второй столбец А* есть

Аналогично вычисляем третий и четвертый столбцы и в результате получаем матрицу А*:

Анализ этой матрицы показывает (см. 5.2), что данный граф связен и имеет две бикомпоненты: {v₁, v₄} и {v₂, v₃}.

Заметим, что в полукольце В можно упростить решение систем уравнений, воспользовавшись свойствами полукольца. Легко видеть, что наименьшее решение уравнения

есть x_k = 1 и не зависит от значений переменных в правой части уравнения. С учетом этого решение системы (5.3) упростится. Так, из первого уравнения сразу получаем х₁ = 1. Тогда четвертое уравнение принимает вид х₄ = x₃ +1, откуда х₄ = 1. Поскольку х₁ и х₄ не входят в оставшиеся два уравнения, их решение нужно искать, используя метод исключения.

Пример 5.10. Для графа, изображенного на рис. 5.27, вычислим матрицу кратчайших расстояний, перейдя к полукольцу R⁺. Договоримся, что для упрощения записи ∞ здесь будем понимать как +∞.

Наш взвешенный ориентированный граф задается теперь следующей матрицей:

Система для вычисления первого столбца матрицы А* имеет вид

Обратим внимание на нюансы, связанные с работой в полукольце R⁺: элементы 1 и 0 не являются единицей и нулем полукольца, т.е. х ≠ x + 0 и х ≠ 1 ⋅ x в общем случае. Напомним, что сложение в полукольце R⁺ — взятие наименьшего из двух чисел, а умножение — обычное арифметическое сложение. Заметим, что наличие слагаемого 0 в любой сумме (в полукольце) означает, что вся сумма равна 0; слагаемое +∞ можно не записывать (как нуль полукольца).

Из первого уравнения системы сразу следует, что х₁ = 0, так как одно из слагаемых в правой части есть элемент 0. Напомним, что итерация любого элемента в рассматриваемом полукольце равна единице полукольца. Учитавая этот факт, из второго уравнения получаем

x₂ = 2*(3x₃ + ∞) = 3x₃.

Исключая x₂ из остальных уравнений системы и учитывая, что x₁ = 0, получаем

Далее, из второго уравнения имеем

x₃ = (1 ⋅ 3)x₃ + ∞ = 4₃ + ∞,

откуда x₃ = 4* ⋅ ∞ = ∞, и поэтому

x₃ = 3 ⋅ 0 + 4 ⋅ ∞ + ∞ = 3 + ∞ = 3

Подставляя найденное значение x₃ в выражение для x₂ получаем x₂ = ∞. Первый столбец искомой матрицы вычислен:

Этот столбец содержит кратчайшие расстояния от всех вершин графа до вершины v₁. Наличие в нем нулей полукольца во второй и третьей строках говорит о том, что вершина v₁ не достижима из вершин v₂ и v₃.

Аналогично вычисляются остальные столбцы матрицы А*. Результат будет следующим:

Для данного простого ориентированного графа легко сопоставить полученный алгебраический результат с результатом „визуального" анализа ориентированного графа. Рассмотрим, например, пару вершин (v₁, v₃). В ориентированном графе есть различные пути из вершины v₁ в вершину v₃. Легко видеть, что заведомо „не выгодны" пути, содержащие контуры и петли, поэтому их рассматривать не будем и вычислим метки по простым путям. По пути v₁ → v₄ → v₃ сумма меток равна 5, по пути v₁ → v₃ — 10, а по пути v₁ → v₂ → v₃ — 8. Кратчайшее расстояние — 5, что совпадает с ответом, полученным алгебраически: элемент а^*13 также равен 5. #

Помимо изложенного есть еще один способ вычисления замыкания матрицы с элементами в замкнутом полукольце. Он основан на понятии пути ранга k из вершины v_i в вершину v_j.

Пусть в ориентированном графе выбрана и зафиксирована нумерация вершин. Будем полагать, что все вершины пронумерованы подряд натуральными числами, начиная с 1.

Путь v_i0 → v_i1 → ... → v_im длины m называют путем ранга k при m > 1, если k — наибольшее среди чисел i₁, ..., i_m-1 и путем ранга 0 при m = 1. Путь нулевой длины также считают путем ранга 0. Таким образом, ранг пути — это максимальный номер вершины, в которую разрешено заходить по пути из v_i в v_j (исключая вершины v_i и v_j). Путь ранга 0 не содержит промежуточных вершин. Максимальный ранг пути в ориентированном графе при указанном выше способе нумерации равен числу его вершин.

Пример 5.11. В ориентированном графе, изображенном на рис. 5.27, путь v₁ → v₄ → v₁ имеет ранг 4, путь v₄ → v₁ → v₂ — ранг 1, путь v₄ → v₁ → v₃ → v₂ — ранг 3. Пути v₄ → v₃ → v₂, v₄ → v₁ → v₃ → v₂ и v₄ → v₂ → v₂ → v₃ → v₂ также имеют ранг 3. #

Обозначим через С^k матрицу стоимостей прохождения между различными парами вершин по всем путям ранга, не превосходящего k. Ее элемент c^(k)ij содержит стоимость прохождения из вершины v_i в вершину v_j по всем путям рангов 0, ..., k-1, k.

Выведем формулу для вычисления элемента c^(k)ij матрицы С^k. Для этого заметим следующее. По пути ранга, не большего k, из вершины v_i в вершину v_j можно пройти следующими способами:

идя из вершины vi в вершину vj по некоторому пути ранга, не превосходящего k — 1, т.е. минуя вершину vk; сначала идя из vi в vk по пути ранга, не большего k — 1, затем „покрутившись" любое число раз (а может быть, и ни разу) по какому-либо контуру или любому замкнутому пути из vk в vk ранга, не большего k — 1, и, наконец, идя из вершины vk в вершину vj по пути ранга, не большего k - 1 (рис. 5.28).

При первом способе следования стоимость прохождения из вершины v_i в v_j по всем путям ранга, не большего л — 1, составит c^(k-1)ij.

При втором способе следования стоимость прохождения из v_i в v_k по всем путям ранга, не большего л — 1, будет равна c^(k-1)ik. Стоимость прохождения из v_k в v_k по всем замкнутым путям ранга, не большего k — 1, составит (c^(k-1)kk)*.

Поясним это в частном случае, когда вершина v_k содержится в каком-то одном контуре. Пусть Г — такой контур, а μ_Г — метка этого контура. Тогда очевидно, что метка пути, образованного нуль-кратным прохождением по контуру Г, равна единице полукольца (как метка всякого пути длины 0), метка же пути, образованного m-кратным прохождением по Г при m ≥ 1, равна μ^mГ. Следовательно, стоимость прохождения по всем путям, которые получаются при произвольном числе прохождений по контуру Г, составит

Стоимость прохождения из вершины v_k в вершину v_j по пути ранга, не большего k — 1, равна c^(k-1)kj (см. рис. 5.28). Таким образом, стоимость прохождения по пути ранга, не большего k, при указанном способе следования составит

c^(k-1)ik (c^(k-1)kk)* c^(k-1)kj.

Таким образом, словесное описание "путешествия" из v_i в v_j по путям ранга, не большего k, приводит к следующей формуле для вычисления элемента матрицы С^k:

c^(k)ij = c^(k-1)ij + c^(k-1)ik (c^(k-1)kk)* c^(k-1)kj.     (5.5)

Пусть a_ij — элементы матрицы меток дуг ориентированного графа. Поскольку каждый путь ранга 0 между дающими вершинами состоит из одной дуги, а каждая вершина достижима сама из себя по пути нулевой длины с меткой 1 или по петле с меткой а_ii, то элементы матрицы С⁰ имеют вид

Тогда матрицу стоимостей С = А* можно найти, вычисляя последовательно матрицы С^(k) k = 0,n, по формулам (5.5) и (5.6).

Вычисления по формулам 5.5 и 5.6 образуют алгоритм Флойда — Уоршелла — Клини определения стоимости прохождения между любыми парами вершин.

Для полуколец В и R⁺ в силу того, что в них итерация любого элемента х равна единице полукольца, получим упрощенный вариант формулы (5.5):

c^(k)ij = c^(k-1)ij + c^(k-1)ik c^(k-1)kj.     (5.7)

Вычисления по формуле (5.7) начинают с матрицы определяемой соотношением (5.6). Все дальнейшие вычисления удобно также проводить в матричном виде. Для нахождения матрицы С^(k) удобно определить сначала матрицу D^(k) элементы которой вычисляются по формуле

d^(k)ij = c^(k-1)ik c^(k-1)kj.

Чтобы найти j-й столбец матрицы D^(k) достаточно k-й столбец матрицы С^(k-1) умножить (в смысле соответствующего полукольца) на j-й элемент k-й строки этой же матрицы.

Решим описанным способом задачу о кратчайших расстояниях в графе, изображенном на рис. 5.27. Для него С⁰ = А, где матрица А имеет вид (5.4). Используя формулу (5.7), следовательно находим

Например, матрица С⁽²⁾ по матрице С⁽¹⁾ вычисляется так. Сначала выделим в С⁽¹⁾ вторую строку и второй столбец:

Затем, чтобы вычислить первый столбец матрицы С⁽²⁾, берем второй (выделенный) столбец матрицы С⁽¹⁾ и умножаем (в полукольце 7?+) его элементы по очереди на первый элемент второй (выделенной) строки той же матрицы С⁽¹⁾. Каждое такое произведение складываем в полукольце с одноименным элементом первого столбца матрицы С⁽¹⁾. Поскольку умножение в полукольце R⁺ — это арифметическое сложение, а сложение — взятие наименьшего из двух чисел, мы получим следующие элементы первого столбца матрицы С⁽²⁾:

c⁽²⁾¹¹ = min{c⁽¹⁾¹¹, c⁽¹⁾¹² + c⁽¹⁾²¹} = min{0, ∞} = 0,

c⁽²⁾²¹ = min{c⁽¹⁾²¹, c⁽¹⁾²² + c⁽¹⁾²¹} = min{∞, ∞} = ∞,

c⁽²⁾³¹ = min{c⁽¹⁾³¹, c⁽¹⁾³² + c⁽¹⁾²¹} = min{∞, ∞} = ∞,

c⁽²⁾⁴¹ = min{c⁽¹⁾⁴¹, c⁽¹⁾⁴² + c⁽¹⁾²¹} = min{3, ∞} = 3.

Как видим, первый столбец матрицы С⁽²⁾ не изменился по сравнению с первым столбцом матрицы С⁽¹⁾ Это означает, что нельзя уменьшить стоимость прохождения в первую вершину из других вершин графа, идя через вторую вершину (см. рис. 5.27).

Точно так же для вычисления второго столбца матрицы С⁽²⁾ умножаем второй столбец С⁽¹⁾ на второй элемент второй строки той же матрицы, для вычисления третьего столбца — на третий элемент второй строки и т.д. Не выписывая подробно всех вычислений, отметим характерный момент — изменение элемента c⁽²⁾¹³ = 8 по сравнению с c⁽¹⁾¹³ = 10, связанное с тем, что стоимость прохождения из v₁ в v₃ по пути ранга 2 оказалась меньше, чем стоимость прохождения по пути ранга 1. Минимальная же стоимость прохождения c⁽⁴⁾¹³ = 5 получена по пути ранга 4.