Как найти матрицу достижимости по графу

Достижимость и контрдостижимость

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

Достижимость в графе описывается матрицей достижимости R=[r_ij], i, j=1, 2, … n, где n – число вершин графа, а каждый элемент определяется следующим образом:

r_ij=1, если вершина х_j достижима из х_i,

r_ij=0, в противном случае.

Множество вершин R(x_i) графа G, достижимых из заданной вершины x_i, состоит из таких элементов x_j, для которых (i, j)-й элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице R равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0. Поскольку прямое отображение 1-го порядка Г⁺¹(x_i) является множеством таких вершин x_j, которые достижимы из x_i с использованием путей длины 1, то множество Г⁺(Г⁺¹(x_i)) = Г⁺²(x_i) состоит из вершин, достижимых из x_i с использованием путей длины 2. Аналогично Г^+p(x_i) является множеством вершин, которые достижимы из x_i с помощью путей длины p.

Так как любая вершина графа, которая достижима из x_i, должна быть достижима с использованием пути (или путей) длины 0 или 1, или 2, …, или p, то множество вершин, достижимых для вершины x_i, можно представить в виде

.

Как видим, множество достижимых вершин R(x_i) представляет собой прямое транзитивное замыкание вершины x_i, т. е. R (x_i) = T⁺(x_i). Следовательно, для построения матрицы достижимости находим достижимые множества R (x_i) для всех вершин . Полагая, r_ij=1, если и r_ij=0 в противном случае.

Для графа, приведенного на
рис.
4.1,а, множества достижимостей находятся следующим образом:

,

,

,

,

,

,

.

Матрица достижимости имеет вид, как показано на
рис.
4.1,в. Матрицу достижимости можно построить по матрице смежности (
рис.
4.1,б), формируя множества T⁺(x_i) для каждой вершины x_i
.

Матрица контрдостижимости Q = [ q_ij], i, j =1, 2, … n, где n – число вершин графа, определяется следующим образом:

q_ij=1, если из вершины x_j
можно достичь вершину x_i
,

q_ij=0, в противном случае.

Контрдостижимым множеством Q (x_i) является множество таких вершин, что из любой вершины этого множества можно достичь вершину x_i
. Аналогично построению достижимого мно-жества R (x_i) можно записать выражение для Q (x_i):

.

Таким образом, видно, что Q (x_i) – это есть не что иное как обратное транзитивное замыкание вершины x_i
, т. е. Q (x_i) = Т^—x_i). Из определений очевидно, что столбец x_i
матрицы Q (в котором q_ij=1, если , и q_ij=0 в противном случае) совпадает со строкой x_i
матрицы R, т. е. Q = R^T,где R^T
– матрица, транспонированная к матрице достижимости R.

Матрица контрдостижимости показана на
рис.
4.1,г.

Следует отметить, что поскольку все элементы матриц R и Q равны 1 или 0, то каждую строку можно хранить в двоичной форме, экономя затраты памяти ЭВМ. Матрицы R и Q удобны для обработки на ЭВМ, так как с вычислительной точки зрения основными операциями являются быстродействующие логические операции.

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

Достижимость и
контрдостижимость

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

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

Достижимость в графе описывается
матрицей достижимости R=[r_ij],
i, j=1, 2, … n, гдеn–
число вершин графа, а каждый элемент
определяется следующим образом:

r_ij=1,
если вершинах_jдостижима изх_i,

r_ij=0,
в противном случае.

Множество вершин R(x_i)графаG, достижимых из
заданной вершиныx_i, состоит из таких элементовx_i, для которых(i, j)-й
элемент в матрице достижимостей равен
1. Очевидно, что все диагональные элементы
в матрицеRравны 1,
поскольку каждая вершина достижима из
себя самой путeм длины 0. Поскольку прямое
отображение 1-го порядкаГ⁺¹(x_i)является множеством таких вершинx_j, которые достижимы изx_iс использованием путей длины 1, то
множествоГ⁺(Г⁺¹(x_i))
= Г⁺²(x_i)состоит из вершин, достижимых изx_iс использованием путей длины 2. АналогичноГ^+p(x_i)является множеством вершин, которые
достижимы из x_i с помощью путей
длиныp.

Так как любая вершина графа, которая
достижима из x_i, должна быть достижима с использованием
пути (или путей) длины 0 или 1, или 2, …,
илиp, то множество
вершин, достижимых для вершиныx_i, можно представить в виде

R (x_i)
= { x_i }
Г⁺¹(x_i)

Г⁺²(x_i)
…Г^+p(x_i).

Как видим, множество достижимых вершин
R(x_i)представляет собой прямое транзитивное
замыкание вершиныx_i, т. е.R(x_i)
= T⁺(x_i).
Следовательно, для построения матрицы
достижимости находим достижимые
множестваR(x_i)для всех вершинx_iX.
Полагая,r_ij=1,
еслиx_j
R(x_i)иr_ij=0в противном случае.

Рис. 4.1. Достижимость в графе: а –граф;
б – матрица смежности; в – матрица
достижимости; г- матрица контрдостижимости.

Для графа, приведенного на рис. 4.1,а,
множества достижимостейнаходятся
следующим образом:

R (х₁) = { х₁}{ х₂, х₅}{ х₂, х₄, х₅ }{ х₂, х₄, х₅} = { х₁,
х₂, х₄, х₅},

R (х₂) = { х₂}{ х₂, х₄}{ х₂, х₄, х₅}{
х₂, х₄, х₅} = { х₂,
х₄, х₅},

R (х₃) = { х₃}{ х₄}{ х₅}{ х₅ } = { х₃, х₄, х₅},

R (х₄) = { х₄}{ х₅}{ х₅} = { х₄, х₅},

R (х₅) = { х₅}{ х₅} = { х₅},

R (х₆) = { х₆}{ х₃, х₇}{ х₄, х₆}{ х₃, х₅, х₇}{ х₄, х₅, х₆} = { х₃,
х₄, х₅, х₆, х₇},

R (х₇) = { х₇}{ х₄, х₆}{ х₃, х₅, х₇}{ х₄, х₅, х₆} = { х₃,
х₄, х₅, х₆, х₇}.

Матрица достижимостиимеет вид,
как показано на рис. 4.1,в.Матрицу
достижимости можно построить поматрице смежности(рис. 4.1,б), формируя
множестваT⁺(x_i)для каждой вершиныx_i.

Матрица контрдостижимостиQ
= [ q_ij],i, j =1, 2, … n, гдеn– число вершин графа, определяется
следующим образом:

q_ij=1,
если из вершиныx_jможно достичь вершинуx_i,

q_ij=0,
в противном случае.

КонтрдостижимыммножествомQ
(x_i)является множество таких вершин, что
из любой вершины этого множества можно
достичь вершинуx_i. Аналогично построению достижимого
множестваR (x_i)можно записать выражение дляQ
(x_i):

Q (x_i)
= { x_i }
Г^-1(x_i)
Г^—2(x_i)
…Г^-p(x_i).

Таким образом, видно, что Q
(x_i)– это есть не что иное как обратное
транзитивное замыкание вершиныx_i, т. е.Q (x_i)
= Т^—(x_i).
Из определений очевидно, что столбец
x_iматрицыQ(в
которомq_ij=1,
еслиx_j
Q (x_i),
иq_ij=0в противном случае) совпадает со строкойx_i
матрицыR, т. е.Q
= R^T,гдеR^T– матрица, транспонированная кматрице
достижимостиR.

Матрица контрдостижимостипоказана
на рис. 4.1,г.

Следует отметить, что поскольку все
элементы матриц RиQравны 1 или 0, то каждую строку можно
хранить в двоичной форме, экономя затраты
памяти ЭВМ. МатрицыRиQудобны для обработки
на ЭВМ, так как с вычислительной точки
зрения основными операциями являются
быстродействующие логические операции.

Нахождение
множества вершин, входящих в путь

Если необходимо узнать о вершинах графа,
входящих в эти пути, то следует вспомнить
определения прямого и обратного
транзитивных замыканий. Так как T⁺(x_i)– это множество вершин, в которые есть
пути из вершиныx_i,
аT^–(х_j)– множество вершин, из которых есть
пути вx_j, тоT⁺(x_i)
T^–(x_j)– множество вершин, каждая из которых
принадлежит, по крайней мере, одному
пути, идущему отx_iкx_j
. Эти вершины называются существенными
или неотъемлемыми относительно двух
концевых вершинx_iиx_j. Все остальные вершины графа называются
несущественными или избыточными,
поскольку их удаление не влияет на пути
отx_iкx_j.

Рис. 4.2. Орграф

Так для графа на рис. 4.2 нахождение
вершин, входящих в путь, например из
вершины х₂в вершинух₄, сводится к нахождениюТ⁺(
х₂)
={ х₂,
х₃,
х₄,
х₅,
х₆},

Т^—(
х₄)
={ х₁,
х₂,
х₃,
х₄,
х₅},
и их пересеченияT⁺(х₂)
T^–(х₄)
={ х₂,
х₃,
х₄,
х₅}.

Матричный метод нахождения путей в
графах

Матрица смежности полностью определяет
структуру графа. Возведем матрицу
смежности в квадрат по правилам
математики. Каждый элемент матрицы А²
определяется по формуле

a⁽²⁾_ik=ⁿ_j=1^a_ij^a_jk

Слагаемое в формуле равно 1 тогда и
только тогда, когда оба числа a_ijиa_jk
равны 1, в противном случае оно равно
0. Поскольку из равенстваa_ij
= a_jk
= 1следует существование пути длины
2 из вершиныx_iв вершинух_k, проходящего через вершинуx_j, то (i -й,k-й) элемент матрицыА²равен числу путей длины 2, идущих изx_iвх_k.

В таблице 4.1a представлена матрица
смежности графа, изображенного на рис.
4.2. Результат возведения матрицы смежности
в квадрат А²показан в таблице 4.1б.

Так «1», стоящая на пересечении
второй строки и четвертого столбца,
говорит о существовании одного пути
длиной 2 из вершины х₂к вершинех₄. Действительно, как видим вграфена рис. 4.2, существует такой путь:a₆,
a₅. «2» в
матрицеA²говорит о существовании двух путей
длиной 2 от вершиных₃к вершинех₆:a₈,
a₄иa₁₀,
a₃.

Аналогично для матрицы смежности,
возведенной в третью степень A³
(таблица 4.1в),a ⁽³⁾
_ikравно числу
путей длиной 3, идущих отx_iкх_k. Из четвертой строки матрицыA³видно, что пути длиной 3 существуют: один
изх₄вх₄(a₉,
a₈,
a₅),
один изх₄в

х₅(a₉,
a₁₀,
a₆)и два пути изх₄вх₆(a₉,
a₁₀,
a₃
и a₉,
a₈,
a₄).
МатрицаA⁴показывает существование путей длиной
4 (таблица 4.1г).

Таким образом, если a ^р
_ikявляется
элементом матрицыA^р,тоa ^р
_ikравно числу
путей (не обязательно орцепей или простых
орцепей) длиныр, идущих
отx_iкх_k.

Соседние файлы в папке МОТС

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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.

Тема: Уравнения в идемпотентных полукольцах. Гомоморфизм графов. Алгоритмы обхода вершин графа.. Читаем, комментируем, решаем ДЗ.

Идемпотентные полукольца

• :
• : для любого

Нахождение матрицы достижимости

1-й столбец

2-й столбец

3-6 столбцы

Нахождение кратчайших путей

1-й столбец

2-й столбец

3-6 столбцы

Гомоморфизм и автоморфизм графов

Алгоритмы обхода графов. Поиск в глубину, поиск в ширину

bool visited[N] = {false, ... }; // массив флагов посещённых вершин
edge edges[M];                   // массив рёбер

// рекурсивная процедура поиска
void deep_search(vertex_t v) {

    visited[v] = true; // отметить вершину как посещённую     
    ...                // сделать с вершиной то, ради чего обход затевался

    for(size_t i = 0; i < M; i++) {
        edge e = edges[i];
        if(e.from == v && !visited[e.to]) {
             deep_search(e.to);
        }  
    }
}

bool visited[N] = {false, ... }; // массив флагов посещённых вершин
edge edges[M];                   // массив рёбер
stack<vertex_t> s;               // стэк

// нерекурсивная процедура поиска
void deep_search(vertex_t v0) {

    s.push(v0);

    while(!s.empty()) {
        vertex_t v = s.pop();

        if(visited[v]) continue; // пропустить посещённую вершину

        visited[v] = true; // отметить вершину как посещённую
        ...                // сделать с вершиной что-то
   
        for(size_t i = 0; i < M; i++) {
            edge e = edges[i];
            if(e.from == v && !visited[e.to]) {
                s.push(e.to);
            }  
        }
    }
}

остовные дуги

получаются непосредственно при поиске в глубину, образуют дерево (или
в общем случае лес), на рисунке обозначены пунктиром;

прямые дуги

соединяют предка и потомка в остовном пути, на рисунке обозначены
буквой F;

обратные дуги

соединяют потомка и предка в остовном пути, на рисунке обозначены
буквой B, интересно то, что каждая из таких дуг задаёт элементарный контур в графе;

перекрёстные дуги

все остальные дуги, на рисунке обозначены буквой C.

bool visited[N] = {false, ... };   // массив флагов посещённых вершин
edge edges[M];                     // массив рёбер
queue<vertex_t> q;                 // очередь

// процедура поиска
void wide_search(vertex_t v0) {

    q.push(v0);

    while(!q.empty()) {
        vertex_t v = q.pop();

        if(visited[v]) continue; // пропустить посещённую вершину
        visited[v] = true;       // отметить вершину как посещённую      
        ...                      // сделать с вершиной что-то
   
        for(size_t i = 0; i < M; i++) {
            edge e = edges[i];
            if(e.from == v && !visited[e.to])
               q.push(e.to);
        }
    }
}

Матрица достижимости простого ориентированного графа  — бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Способы построения матрицы достижимости

Перемножение матриц

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

.

По определению, матрица композиции отношений есть , где  — конъюнкция, а  — дизъюнкция.

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

Случай нескольких путей

Если булевы операции дизъюнкции и конъюнкции заменить обычными алгебраическими операциями сложения и умножения соответственно, нахождение матрицы достижимости сведётся к обычному пошаговому перемножению матриц с последующим сложением результатов каждого шага. Тогда получившаяся матрица будет состоять не только из 0 и 1 и будет характеризовать не только наличие путей между вершинами, но уже и количество таких путей. В таком случае можно разрешить наличие кратных рёбер в графе.

Пример

Рассмотрим простой связный ориентированный граф .
Он имеет матрицу смежности вида:

Найдём булевы степени этой матрицы , , :

,
,
.

Получим матрицу достижимости

Таким образом, из вершины можно добраться в любую другую.

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

Она показывает количество путей длины от 1 до 4 между вершинами орграфа.

Алгоритм Уоршелла

Существует другой алгоритм, позволяющий найти матрицу достижимости в точности за шагов — алгоритм Уоршелла.

Связанные понятия

Матрица сильной связности

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

Построение матрицы сильной связности

Матрица сильной связности может быть построена из матрицы достижимости. Пусть  — матрица достижимости орграфа . Тогда матрица сильной связности состоит из элементов .

Пример

Рассмотрим тот же граф, что и ранее.

Его матрица достижимости:

Из неё получаем матрицу сильной связности:

Вершины 3 и 4 сильно связаны друг с другом и сами с собой.

Матрица связности графа

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

Матрица контрдостижимости

Матрица контрдостижимости Q графа G может быть найдена из матрицы достижимости путем ее транспонирования.

Примечания