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

101 чел.

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


 

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

80525. Автоматизація процесів оцінювання машин та обладнання 70.7 KB
  Автоматизація обліку матеріальних цінностей Матеріальні цінності це сировина і матеріали покупні напівфабрикати і комплектуючи вироби тара і тарні матеріали; паливо будівельні матеріали і обладнання для установки; малоцінні і швидкозношувані предмети спецодяг і спецвзуття. Основними задачами що вирішуються на цій ділянці є своєчасне повне і достовірне відображення в обліку а потім видання необхідних оброблених на ПЕОМ це настільна або портативна високопродуктивна обчислювальна система...
80526. КУЛЬТУРА УКРАЇНИ XIV – I ПОЛ. XVII СТОЛІТТЯ 1.97 MB
  Існує думка, що період XIV – перш. пол. XVII ст. мало відображений у джерелах, так як був бідний подіями, які могли залишити помітний слід в історії. Ближче до істини інша точка зору: життя було значно багатшим, ніж це зафіксовано в документах і пам\'ятках культури, що до нас дійшли
80527. Українська культура в другій половині ХХ століття 39.07 KB
  Розвиток української культури в другій половині ХХ ст. У Донецькій та Кримській областях не залишалося жодної української школи. ЦК КПРС прийняв нову постанову що підсилило русифікацію української системи освіти. Серед них можна назвати Історію української літератури Історію української мови Радянську енциклопедію історії України Історію українського мистецтва.
80528. Витоки української культури. Матеріальна та духовна культура словянського світу 1тис. нашої ери 562 KB
  Термін «культура» вперше зустрічається в античному світі. Його початкове значення – обробка rрунту, внесення людиною змін у природу. Надалі термін «культура» отримав більш універсальне значення.Культура - це все, що створено людиною.
80529. Українська культура у другій половині ХХ століття 77 KB
  Розвиток української культури у другій половині ХХ ст. У Донецькій і Кримській областях не залишалося жодної української школи. ЦК КПРС прийняв нову постанову що підсилило русифікацію української системи освіти. Серед них можна назвати Історію української літератури Історію української мови Радянську енциклопедію історії України Історію українського мистецтва .
80530. Культура Україна на межі 20-21 століття 805.79 KB
  Відпали відкриті або приховані перешкоди на шляху розвитку національної культури. Товариство звільнилося від ідеологічних штампів попередньої епохи вперше отримало можливість відкритого доступу до досягнень світової духовності і культури. Активізувалася культурне життя в регіонах країни зросла увага до традиційної культури Україна.
80531. Національно-культурне відродження 1920-1930-х рр. Українська культура періоду тоталітаризму (1933 – 1953 рр.) 28.11 KB
  Коренізація була викликана прагненням більшовиків заручитися підтримкою місцевого (корінного) населення з тим, щоб зміцнити свою соціальну базу. У середині 20-х рр. 80% населення республіки складали українці, а 20% – представники інших національностей.
80532. Українська культура початку ХХ ст. (1900 – 1921 рр.) 547 KB
  Української наукової громадськості було надано сім професорських місць у Львівському університеті і три професорських місця в Чернівецькому університеті. Спроби української громадськості з інших регіонів надати закарпатцям допомогу також припинялися угорською владою. Зростання числа грамотних українців стимулював розвиток української літератури. Коцюбинського Цвіт яблуні Intermezzo Тіні забутих предків стали класикою золотим фондом української літератури.