41197

Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall)

Лекция

Физика

Именно {Инициализация: } {1} for i := 1 to n do {2} for j := 1 to n do {3} if i = j then else ; {4} for k := 1 to n do {5} for i := 1 to n do {6} for j := 1 to n do {7} ; {есть матрица смежности транзитивного замыкания т. {Инициализация: } {1} for i := 1 to n do {2} for j := 1 to n do {3} if i = j then else ; {4} for k := 1 to n do {5} for i := 1 to n do {6} if then ; {есть матрица смежности транзитивного замыкания т. Следовательно матрицу можно вычислить с помощью алгоритма:...

Русский

2013-10-23

280.5 KB

68 чел.

Лекция 11 часть 2 (весна 2009 года)

Кратчайшие пути между всеми парами вершин

Часть 1. Вспомогательная тема:

Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall)

 Задан ориентированный граф G = (V, E). Как и ранее n = |V|, m = |E|.

 Транзитивным замыканием графа G называется граф G*, состоящий из тех же вершин, т.е. G* = (V, E*), множество рёбер которого есть

E* = {(u, v): ( V) & ( V) & (существует путь из u в v в графе G) }.

Иными словами, в графе транзитивного замыкания G* дуга из вершины u в вершину v имеется только тогда, когда в исходном графе G есть путь из u в v.

Например, для графа G, изображенного на рис. 1.а, его транзитивное замыкание дано на рис. 1.б.

Матрица смежности A графа G, изображенного на рис. 1.а, есть

A = ,

а матрица смежности А* транзитивного замыкания G* этого графа есть

А* = .

Можно ввести понятие матрицы путей (или матрицы достижимости) P графа G, так, что pij = 1, если существует путь из вершины  в вершину  в графе G, и pij = 0 в противном случае. Очевидно, что матрица путей P графа G совпадает с матрицей смежности А* его транзитивного замыкания G*.

Далее важную роль в нашем рассмотрении будут играть степени матрицы смежности.

 Утверждение. Пусть A есть матрица смежности графа G. Элемент  матрицы  равен числу путей длины k из вершины  в вершину  (V, V).

 Доказательство проведем по индукции:

А) при k = 1 утверждение очевидно (по определению матрицы смежности);

Б) пусть утверждение верно для k = l,  покажем, что оно верно и для k = l + 1; действительно  и

.

Рассмотрим отдельное слагаемое этой суммы, соответствующее вершине . Если , то это слагаемое не дает вклада в сумму. Если же  и , то {число путей длины l + 1 из вершины  в вершину }, причём из l шагов состоит каждый из путей из вершины  в вершину  и один шаг ведет из вершины в вершину. Рисунок

наглядно изображает это рассуждение (пунктиром показаны пути, а дуга – сплошной линией). Таким образом, вся сумма даст число путей длины l + 1 из вершины  в вершину .

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

Очевидно, что элементы матрицы

дают число путей длины не более чем 4 между каждыми двумя вершинами. Очевидно также, что если в этой матрице заменить все ненулевые элементы на 1, то мы получим матрицу путей P графа G или, что то же, матрицу смежности A* его транзитивного замыкания G*.

 В общем случае пусть  и определим матрицу P как

Очевидно, что это и есть матрица путей P графа G или, что то же, матрица смежности A* его транзитивного замыкания G*. Т.к. перемножение двух матриц осуществляется за время O(n3), то вычислить матрицу P можно за O(nn3) = O(n4) операций. Заметим, что если нас интересуют циклы по всем вершинам графа, то следует рассмотреть .


Таблица  

 = 

    Пути длины 1

  =  = 

      Пути длины 2

  = 

               Пути длины 3

  = 

               Пути длины 4


Ясно, что при таком подходе мы, вероятно, вычисляем лишнее, т.к. нас с самого начала интересует не количество путей, а лишь факт их наличия. В связи с этим оказывается полезным переопределить операцию умножения матриц. Напомним, что обычная операция умножения матриц C = AB определяется как (мы рассматриваем квадратные матрицы размера nn)

Определим операции сложения и умножения «булевских» матриц:

C = AB  ,

C = A+B  .

Легко видеть, что эти операции получаются из «обычных» формул для вычисления элементов матриц заменой операций сложения (знак +) на дизъюнкцию или булевское сложение (знак ) и умножения – на конъюнкцию или булевское умножение (знак &).

Нетрудно проверить, что с переопределенными операциями имеем

.

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

Теперь, поскольку нам нужна лишь окончательная степень , то можно воспользоваться бинарным способом вычисления степени, и это приводит к алгоритму сложности O(n3log n), а не O(n4), как ранее.

Оказывается, существует более эффективный алгоритм, известный как алгоритм Уоршалла, к рассмотрению которого мы и переходим.

Наше предыдущее рассмотрение фактически основывалось на таком анализе  структуры путей, при котором выделялась последняя дуга и предшествующие ей части пути (см. рисунок на с. 2). Применим другой подход. Пусть вершины графа пронумерованы числами от 1 до n. Нас будут интересовать пути, проходящие через промежуточные вершины из некоторого определенного множества. Определим булевские величины  так, что равно 1 или 0 в зависимости от того, существует или нет путь из вершины  в вершину , проходящий через промежуточные вершины только из множества вершин с номерами от 1 до k. Постараемся определить, как связаны элементы  матрицы  с элементами матрицы . Рассмотрим следующий схематичный рисунок.

Рассмотрим соотношение

.

Справедливость этого соотношения обосновывается рассуждениями, соответствующими интуитивно понятному приведенному рисунку. При этом следует учесть, что .

Алгоритм Уоршалла состоит в вычислении последовательности матриц . Именно,

{Инициализация: }

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   for := 1 to n do

{7}    ;

{есть матрица смежности транзитивного замыкания, т.е. }

Удобно преобразовать этот алгоритм к несколько иному виду. «Свернём» цикл по j в строке 6, переписав строку 7 в виде

{6*}  .

Здесь  обозначают i-ую строку матрицы , i-ую строку матрицы  и k-ую строку матрицы  соответственно, а операции присваивания и дизъюнкции применяются к строкам матриц. При этом цикл в явной форме исчез. Он «спрятан» в операциях со строками матриц. В такой форме удобнее анализировать изменения матриц  при работе алгоритма.

Далее заметим, что теперь строки 6 и 7 в алгоритме можно заменить на следующее

{6*}   if   then  else .

В такой форме отчётливо видно, что при заданном k каждая i-ая строка либо не изменяется (при ), либо при  заменяется на результат побитной дизъюнкции i-ой и k-й строк. Для наглядности изобразим это графически на следующем рисунке (при i < k).

Поскольку при модификации i-ой строки используются только i-ая и k-ая строки, то новое значение  можно было бы записать на место старого  (при i < k или при i > k). При i = k имеем  и, следовательно, k-ая строка при этом не изменяется. Т.о. все преобразования можно производить в матрице B (двумерном булевском массиве) что называется «на месте».

 С учётом этих соображений алгоритм Уоршалла можно записать в следующем окончательном виде.

{Инициализация: }

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   if   then ;

{есть матрица смежности транзитивного замыкания, т.е. }

Очевидно, что сложность этого алгоритма (с учётом неявного цикла внутри строк) есть O(n3), а в случае, когда строка матрицы может быть представлена одной (или несколькими) битовой строкой и операция дизъюнкции строк выполняется за фиксированное время, тогда сложность алгоритма уменьшается до O(n2).

Часть 2. Основная тема:

Алгоритм построения кратчайших путей между всеми парами вершин

Пусть для ориентированного графа G = (V, E) задана матрица стоимостей W(nn).

 Рассмотрим величину  – стоимость кратчайшего пути из вершины  в вершину  среди всех путей, содержащих не более k дуг. Набор этих величин (матрица)  уже использовался нами ранее при анализе (доказательстве корректности) алгоритма Форда-Беллмана (было использовано другое обозначение d[k| j], при этом первая вершина  была фиксирована). Тогда же было использовано рекуррентное соотношение

.

Докажите это соотношение, используя вспомогательный рисунок:

Оказывается, что матрицу из элементов  можно рассматривать как степень матрицы W, если специальным образом определить операцию «умножения» матриц. Действительно, определим операцию умножения матриц как

C = AB  ,

заменив в обычной операции перемножения матриц сложение (знак +) на взятие минимума min, а умножение  (знак ) – на сложение (знак +). Кроме того, определим диагональные элементы весовой матрицы W как . Определим также матрицу как

Тогда получим

для .

Матрица  является результатом решения задачи о кратчайших путях. Вычислить её можно за O(n4) или же, как и в случае транзитивного замыкания, за O(n3log n) операций.

Далее совершенно аналогично случаю транзитивного замыкания рассмотрим более эффективный алгоритм, известный как алгоритм Флойда-Уоршалла.

Пусть, как и ранее в алгоритме Уоршалла, вершины графа пронумерованы числами от 1 до n. Нас будут интересовать пути, проходящие через промежуточные вершины из некоторого определенного множества. Рассмотрим величину  – стоимость кратчайшего пути из вершины  в вершину  среди всех путей, проходящих через промежуточные вершины только из множества вершин с номерами от 1 до k.

Используя тот же схематичный рисунок,

легко доказать справедливость соотношения

.

Следовательно, матрицу  можно вычислить с помощью алгоритма:

{Инициализация: }

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   for := 1 to n do

{7}    ;

Самостоятельно докажите, что как и в алгоритме Уоршалла, верхние индексы у матриц  можно убрать, т.е. необходимо иметь в алгоритме только один экземпляр матрицы D и все вычисления с ней проводить «на месте». Т.о. алгоритм Флойда-Уоршалла принимает следующий вид:

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   for := 1 to n do

{7}    ;

Очевидно, что сложность этого алгоритма есть O(n3). Сравнение с алгоритмом Форда-Беллмана обнаруживает любопытный факт: найти кратчайшие пути между всеми парами вершин асимптотически не более трудно, чем кратчайшие пути только от одной вершины до всех остальных!

PAGE 1


 

А также другие работы, которые могут Вас заинтересовать

27593. Захват заложника 32.5 KB
  Захват заложника ст. Объективная сторона заключается в захвате или удержании лица в качестве заложника. Захват заложника – это открытое либо тайное с применением насилия или угрозы его применения либо без такового ограничение свободы его передвижения которое сопровождается в последующем открытым сообщением об этом и выдвигаемых условиях его освобождения.
27594. Изнасилование (ст. 131 УК). Отличие этого преступления от насильственных действий сексуального характера (ст. 132 УК) и от понуждения к действиям сексуального характера (ст. 133 УК). Половое сношение и иные действия сексуального характера с лицом, не дост 39.5 KB
  изнасилование половое сношение с применением насилия или с угрозой его применения к потерпевшей или другим лицам либо с использованием беспомощного состояния потерпевшей. Объектом этого преступления является половая свобода женщины а если потерпевшей является несовершеннолетняя или малолетняя то половая неприкосновенность ее. Потерпевшей может быть только женщина. Необходимо отметить что угроза может касаться не только потерпевшей но и других лиц судьба которых важна для потерпевшей например угроза убить мужа или детей женщины...
27596. Исправительные и обязательные работы как виды уголовного наказания. Их характеристика, порядок и условия применения 31 KB
  Исправительные и обязательные работы как виды уголовного наказания. Исправительные работы заключаются в принудительном привлечении осужденного к труду не имеющему основного места работы с удержанием в доход государства определенной доли из его заработка в размере установленном приговором суда. Исправительные работы включают следующие основные элементы: принудительное привлечение к труду; привлечение к труду лиц не имеющих основного места работы; отбывание наказания в местах определяемых органами местного самоуправления по...
27598. Конфискация имущества как мера уголовно-правового характера 30 KB
  Конфискация имущества как мера уголовноправового характера Уже прошло несколько лет с того момента когда в уголовном законе были произведены наиболее ожидаемые изменения Федеральным законом от 27 июля 2006 г. № 153 восстановлен институт конфискации имущества. № 162ФЗ не вызвало столь острых дискуссий на страницах юридической литературы как отмена конфискации имущества. В обновленной редакции конфискация имущества определяется как мера уголовноправового характера заключающаяся в принудительном безвозмездном обращении по решению суда в...
27599. Крайняя необходимость. Понятие и условия ее правомерности. Отличие крайней необходимости от необходимой обороны 30 KB
  Отличие крайней необходимости от необходимой обороны. 39 УК не является преступлением причинение вреда охраняемым уголовным законом интересам в состоянии крайней необходимости т. для устранения опасности непосредственно угрожающей личности и правам данного лица или иных лиц охраняемым законом интересам общества или государства если эта опасность не могла быть устранена иными средствами и при этом не было допущено превышение пределов крайней необходимости. Акт крайней необходимости является правом граждан но не обязанностью.
27601. Лишение права занимать определенные должности и заниматься определенной деятельностью. Лишение специального, воинского или почетного звания, классного чина и государственных наград. Понятие данных видов наказания, порядок и условия их применения 31.5 KB
  Лишение права занимать определенные должности и заниматься определенной деятельностью. Лишение права занимать определенные должности или заниматься определенной деятельностью состоит в запрещении занимать должности на государственной службе в органах местного самоуправления либо заниматься определенной профессиональной или иной деятельностью. Лишение права занимать определенные должности или заниматься определенной деятельностью может назначаться в качестве основного или дополнительного наказания. Лишение права занимать определенные должности...