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

76 чел.

Лекция 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


 

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

85354. Компенсація, корекція і реабілітація як категорії спеціальної психології 37.42 KB
  Перша фаза виявлення того чи іншого порушення в роботі організму. Сигнал про порушення може бути пов’язаний і з самим розладом і з його наслідками з різними відхиленнями в поведінці і діяльності. Друга фаза оцінка параметрів порушення його локалізації та глибини виразності. Не випадково одне і те ж порушення у тварин і людини може призвести до різних наслідків.
85355. Особливості розвитку людини з порушенням зору 40.34 KB
  Вроджені: захворювання й аномалії розвитку органів зору: патологія судинної оболонки захворювання рогової оболонки ока вроджені катаракти глаукоми окремі форми патології сітківки і таке інше. Аномалії зору також можуть виникнути в результаті зовнішніх і внутрішніх негативних впливів що мали місце в період вагітності: перенесені матір’ю вірусні захворювання токсоплазмоз краснуха й таке інше.
85356. Проблема «норми» і «патології» в сучасних науках про людину 40.46 KB
  Розрізнення психічної норми не норми і патології вимагає відповісти як мінімум на два принципових питання. Перший підхід привнесений в психологію з медицини і полягає у визначенні норми через заперечення: якщо людина психічно не хворий відсутні симптоми психічного захворювання значить він психічно здоровий. Другий підхід внесений в психологію з біологічних наук і полягає в розумінні психічної норми як здатності підтримувати гомеостаз або рівновагу від грец.
85358. Розвиток мови при ДЦП 42.08 KB
  Про поширеність порушень мовлення при ДЦП існують різні думки. Семенова відзначає що частота розладів мовлення залежить від форми паралічу. Враховуючи різноманітність порушень мовлення при ДЦП та складну структуру даної патології можна уявити що розвиток мовлення у цих дітей багато в чому залежить від проявів даного розладу. Так на розвиток мови впливають: ті ж обставини які викликають патологію мовлення у дітей без ДЦП; моторні порушення в периферичному мовному апараті.
85359. Механізми формування системних відхилень в дизонтогенезі 37.35 KB
  Дуже часто поява вторинних або системних порушень розглядається як майже автоматичний процес Насправді вторинні відхилення чи не з’являються і не зникають самі по собі. Їх поява і формування пов’язане з роботою численних складних механізмів.
85360. Форми шкільної дезадаптації в молодшому шкільному і підлітковому віці (неврози, страхи, депресія, неврастенія) 47.92 KB
  Разом з тим коли підліток пригнічений сумує або плаче прояви депресії або сильні потягу прийняти алкоголь викурити сигарету здійснити певний вчинок і т. Криза має виключно важливе значення як орієнтир бо потенційно саме в момент його розвитку можна фіксувати патологію коли підліток відчуває що не в силах протистояти стражданню навіть за умови що його можна швидко усунути якщо під час лікування він може пройти через процес рефлексії і опрацювання своїх переживань. Перш за все підліток дійсно знаходиться в пригніченому стані...
85361. Загальна характеристика дітей із порушеннями рухового апарату 39.9 KB
  При всій різноманітності вроджених і рано набутих захворювань і пошкоджень опорнорухового апарату у більшості таких дітей спостерігаються подібні проблеми. Але всі діти з порушеннями опорнорухового апарату потребують особливих умов життя навчання і подальшої трудової діяльності. Більшу частину дітей з порушеннями опорнорухового апарату складають діти з церебральними паралічами.
85362. Причини шкільної дезадаптації (стрес, фрустрація, внутрішній конфлікт) 42.11 KB
  Фрустрація виникає у результаті конфліктів особистості з іншими особливо в колективі в якому людина не дістає підтримки співчутливого ставлення. ВНУТРІШНІЙ КОНФЛІКТ Внутрішньоособистісний конфлікт один із найскладніших конфліктів який відбувається безпосередньо у внутрішньому світі людини. Життя нормальної людини – це внутрішній конфлікт від якого нікуди не дітися.