Смежности

Если мы обнулим главную диагональ матрицы смежности орграфа, квадрат такой матрицы будет

представлять собой граф с ребрами, соответствующими каждому пути длиной 2 (вверху). Если

установить каждый элемент главной диагонали в 1, то квадрат такой матрицы будет представлять

собой граф с ребрами, соответствующий каждому пути длиной 1 или 2 (внизу).

Часть 5. Алгоритмы на графах

На рис. 19.15 представлены различные степени мат­рицы смежности для одного и того же, взятого в каче­стве примера орграфа, постепенно сходящиеся к тран­зитивному замыканию. Рассматриваемый метод предусматривает V умножений матриц самой на себя, для каждого из которых требуется время, пропорцио­нальное V³, что в конечном итоге составит V⁴. Факти­чески мы можем вычислить транзитивное замыкание для любого орграфа всего лишь за счет выполнения [дgV] операций булевого умножения матриц: мы вычис­ляем А², A⁴, A ⁸,..., до тех пор, пока не достигнем пока­зателя степени, большего или равного V⁴. Как следует из доказательства свойства 19.6, А = A ^у для любого t > V; таким образом, результатом этого вычисления, требую­щего на свое выполнение времени, пропорционально­го V³ lgV будет А^у, т.е. транзитивное замыкание.

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

for (i = 0; i < V; i++) for (s = 0; s < V; s++) for (t = 0; t < V; t++) if (A[s][i] & & A[i][t]) A[s][t] = 1;

Этот классический метод, предложенный С. Уор­шаллом (S. Warshall) в 1962 г., наиболее предпочтите­лен при вычислении транзитивных замыканий насы­щенных орграфов. Приведенный выше программный код подобен коду, который можно использовать для возведения в квадрат булевой матрицы: различие (что очень важно!) заключается в порядке выполнения циклов for.

Свойство 19.7. С помощью алгоритма Уоршалла мы можем вычислить транзитивное замыкание орграфа за время, пропорциональное V³.

Доказательство: Оценка времени выполнения рас­сматриваемого программного кода непосредствен­но следует из его структуры. Мы докажем, что он способен вычислить транзитивное замыкание ме­тодом индукции по i. После выполнения первой итерации цикла в матрице на пересечении строки

s и столбца t стоит 1 в том и только том случае, когда существуют пути s-t или s-0-t. Вторая итерация проверяет все пути между s и t, которые содержат верши­ну 1 и, возможно, 0, такие как, например, s-1-t, s-1-0-t и s-0-l-t. Мы

Глава 19. Орграфы и ориентированные ациклические графы

приходим к следующей индуктивному предположению: /-я итерация цикла устанавли­вает бит матрицы, находящийся на пересечении строки s и столбца t, в 1 тогда и только тогда, когда существует ориентированный путь из s в t, который не содержит ника­ких вершин с индексами, большими i (за исключением, возможно, конечных точек s и t). Как только что было доказано, это условие выполняется, когда i равно 0. Пред­положим, что это условие выполняется для i-й итерации цикла, тогда путь из s в t, ко­торый не содержит ни одной вершины с индексами, превосходящими i+1, существу­ет тогда и только тогда, когда: (i) существует путь из s в t, который не содержит никаких вершин с индексами, меньшими i, в этом случае значение A[s][t] установле­но на предыдущей итерации цикла (в соответствии с индуктивным предположением); либо (ii) когда существует путь из s в i+1 и путь из i+1 в t, причем ни один из них не содержит вершин с индексами, большими i (за исключением конечных точек), и в этом случае A[s][i+1] и A[i+l][t] были ранее установлены в 1 (по индуктивному предпо­ложению), следовательно, внутренний цикл устанавливает A[s][t] в 1. ■

Мы можем повысить производительность алгоритма Уоршалла путем простого преоб­разования программного кода: мы вынесем проверку элемента A[s][i] из внутреннего цикла, поскольку по мере изменения t его значение не меняется. Это действие позволит нам избежать выполнения t-ro цикла полностью, когда элемент A[s][i] равен нулю. Эко­номия, которую мы получим от данного усовершенствования, зависит от особенностей орграфа и в большинстве случаев весьма существенна (см. упражнения 19.53 и 19.54). Программа 19.3 реализует это усовершенствование и представляет собой метод Уоршал­ла в виде, позволяющем клиентам сначала выполнить предварительную обработку орграфа (вычислить транзитивное замыкание), затем дать за постоянное время ответ на любой зап­рос относительно достижимости.

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

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