Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

14.1. Транзитивное замыкание

Напомним (разд. 5.2), что бинарное отношение на некотором множестве есть набор упорядоченных пар элементов этого множества. Транзитивное замыкание бинарного отношения R — это отношение R, определенное следующим образом:

тогда и только тогда, когда существует такая последовательность что . Ясно, что если то Следовательно, Можно легко показать, что R — транзитивно. В самом деле оно является наименьшим транзитивным отношением, включающим R. Таким образом, если R транзитивно, то

Как уже отмечалось в разд. 5.2, бинарное отношение можно представить ориентированным графом. Пусть G — ориентированный граф, представляющий отношение R. Ориентированный граф G, представляющий транзитивное замыкание R отношения R, называется транзитивным замыканием графа G. Из определения R следует, что ребро принадлежит G тогда и только тогда,

когда в графе G существует ориентированный путь из вершины в вершину у. Аналогично петля принадлежит графу G тогда и только тогда, когда в графе G присутствует ориентированный цикл, включающий вершину Например, граф, изображенный на рис. 14.1, б является транзитивным замыканием графа на рис. 14.1, а.

Рис. 14.1. а — граф G; б - G - транзитивное замыкание графа

Предположим, что мы определяем матрицу достижимости ориентированного графа G на вершинах как (-матрицу, в которой элемент ) равен 1 тогда и только тогда, когда существует ориентированный путь из вершины i в вершину j при или ориентированный цикл, содержащий вершину i при Другими словами, элемент матрицы достижимости равен 1 тогда и только тогда, когда вершина достижима из вершины i через последовательность ориентированных ребер. Очевидно, что матрица смежности графа G является в то же время матрицей достижимости графа G. Задача построения транзитивного замыкания ориентированного графа возникает в нескольких приложениях. Один из примеров описан Грисом [14.1]. В этом разделе мы обсуждаем элегантный и эффективный алгоритм вычисления транзитивного замыкания, предложенный Уоршоллом [14.2]. Мы обсудим также модификацию алгоритма Уоршолла, предложенную Уорреном [14.3].

Пусть G — ориентированный граф на вершинах, которые обозначены целыми числами Пусть Алгоритм Уоршолла строит последовательность таких графов, что — транзитивное замыкание графа G. Граф получается из графа после обработки вершины i в графе Обработка вершины i в графе включает добавление новых ребер в следующим образом.

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

Рис. 14.2. Иллюстрация к алгоритму Уоршолла.

Алгоритм Уоршолла представлен на рис. 14.2. Ясно, что при . Чтобы показать, что — транзитивное замыкание графа G, необходимо доказать следующее:

Теорема 14.1. 1. Пусть для произвольных вершин s и t графа G существует такой ориентированный путь вершины вершину t, что все вершины, отличные от s и принадлежат множеству Тогда граф содержит ребро

2. Пусть для произвольной вершины s в графе G существует ориентированный цикл С, содержащий вершину s, и все вершины, отличные от s, принадлежат множеству Тогда граф содержит петлю

Доказательство. 1. Докажем индукцией по i. Ясно, что утверждение верно для графа поскольку в соответствии с построением Уоршолла при обработке вершины 1 вводится ребро если граф (равный G) содержит ребра и . Пусть утверждение верно для всех

Предположим, что i не является внутренней вершиной пути Р. Тогда из предположения индукции следует, что содержит ребро . Следовательно, G также содержит ребро потому что Предположим, что -внутренняя вершина пути Р. Тогда вновь из предположения индукции следует, что граф содержит ребра Поэтому при обработке вершины I в ребро добавляется к графу

2. Доказательство аналогично доказательству п. 1.

Непосредственным следствием из этой теоремы является следующее.

Следствие —транзитивное замыкание графа G. Дадим формальное описание алгоритма Уоршолла. В этом описании граф G представляется матрицей смежности М, а символ V применяется для обозначения булева сложения. Алгоритм 14.1. Транзитивное замыкание (Уоршолл).

51. Инициализация.) М—матрица смежности графа

52. Выполнить для .

53. Выполнить для .

54. Если выполнить для .

56. HALT. (M—матрица смежности графа )

Отметим, что М (когда алгоритм приступает к выполнению шага для ) — матрица смежности графа . Обработка диагональных элементов не приводит к добавлению новых ненулевых элементов. Сделаем несколько замечаний:

1. Алгоритм Уоршолла преобразует матрицу смежности М графа G в матрицу смежности его транзитивного замыкания соответствующим переписыванием матрицы М. Поэтому говорят, что алгоритм работает «на месте».

2. Алгоритм обрабатывает все ребра, заходящие в вершину, перед тем, как начинает обрабатывать следующую вершину. Другими словами, он обрабатывает матрицу М по столбцам. Следовательно, мы описываем алгоритм Уоршолла как ориентированный по столбцам.

3. При обработке вершины никакие новые ребра (т. е. ребра, которые не присутствовали в графе, когда началась обработка этой вершины), заходящие в эту вершину, не добавляются. Это означает, что при обработке вершины мы можем выбирать ребра, заходящие в вершину в произвольном порядке.

4. Предположим, что ребро заходящее в вершину t, не присутствует в графе при обработке вершины но добавляется в последующем при обработке некоторой вершины . Ясно, что это ребро не рассматривается при обработке вершины i. Не будет оно обрабатываться и позднее, так как никакая вершина не обрабатывается более одного раза. Фактически такое ребро не приведет к добавлению каких-либо новых ребер.

5. Алгоритм Уоршолла называется работающим в один проход, так как каждая вершина обрабатывается точно один раз.

Предположим, что мы желаем модифицировать алгоритм Уоршолла так, чтобы он стал ориентированным по строкам. В таком алгоритме при обработке вершины обрабатываются все ребра, исходящие из этой вершины. Обработка ребра заключается во введении ребра для каждого ребра исходящего из вершины Поэтому новые ребра, исходящие из вершины, можно добавить при обработке вершины «построчно». Некоторые из этих вновь добавленных ребер не будут обрабатываться до завершения обработки рассматриваемой вершины. Если обработка этих ребер необходима для вычисления транзитивного замыкания, то такая обработка может выполняться только при втором проходе. Таким образом, в общем случае ориентированный по строкам алгоритм может потребовать более одного прохода для вычисления транзитивного замыкания.

Рис. 14.3. Пример работы строкоориентированного алгоритма транзитивного замыкания. а — граф G; б — граф G в — граф

Например, рассмотрим граф G на рис. 14.3, а. После обработки построчно вершин графа G мы получим граф G, представленный на рис. 14.3, б. Очевидно, что G не является транзитивным замыканием графа G, так как ребро (1, 2) еще не добавлено. Можно отметить, что ребро (1, 3) не обрабатывается при этом проходе, поскольку оно добавляется только после обработки ребра (1, 4). То же самое верно и для ребра (4.2).

Предположим, что мы обрабатываем вершины графа G. При этом втором проходе ребро (1, 2) добавляется при обработке вершины 1 и мы получаем транзитивное замыкание графа G, показанное на рис. 14.3, в. Таким образом, для графа, изображенного

на рис. 14.3, а, требуется два прохода ориентированного по строкам алгоритма.

Возникает вопрос: всегда ли достаточно двух проходов? Ответ на него положителен и Уоррен [14.3] продемонстрировал это, предложив изящный двухпроходной строкоориентированный алгоритм. В этом алгоритме при обработке вершины, например i, в первом проходе обрабатываются только ребра, связанные с вершинами, меньшими , а во втором проходе — только ребра, связанные с вершинами, большими i. Другими словами, алгоритм преобразует матрицу смежности М графа G в матрицу смежности графа G, обрабатывая в первом проходе только элементы матрицы, расположенные ниже ее главной диагонали, а во втором проходе — только элементы матрицы, расположенные выше ее главной диагонали. Таким образом, при каждом проходе обрабатывается не более ребер. Приведем описание модификации Уоррена, касающееся алгоритма Уоршолла.

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

S1. М—матрица смежности графа

S2. Выполнить для .

S3. Выполнить для

S4. Если то выполнить для

S5.

S6. Выполнить для

S7. Выполнить для

S8. Если то выполнить для

S9.

S10. HALT. (M — матрица смежности графа G.) Отметим, что в этом алгоритме шаги соответствуют первому проходу, а шаги — второму проходу.

Рис. 14.4. Иллюстрация к алгоритму Уоррена.

Рассмотрим вновь граф, изображенный на рис. 14.3, а. В конце первого прохода алгоритма Уоррена мы получим граф, изображенный на рис. 14.4, а, а в конце второго — транзитивное замыкание графа G, представленное на рис. 14.4, б. Доказательство корректности алгоритма Уоррена основывается на следующей лемме:

Лемма 14.1. Предположим, что для двух произвольных вершин в графе G существует ориентированный путь Р из s в t. Тогда граф, полученный после обработки

вершины s в первом проходе алгоритма Уоррена, содержит ребро , где — следующая за s вершина пути Р причем или

Доказательство. Докажем индукцией по

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

Если то вновь по предположению индукции граф, получаемый после обработки вершины 12 в первом проходе, содержит ребро , где следующая за L вершина пути Р, причем или

Если и то мы повторяем эти рассуждения для вершины до тех пор, пока мы не получим такую вершину что либо либо Таким образом, граф, который мы получаем перед обработкой вершины s, содержит такие ребра при этом выполняются следующие соотношения:

1) вершина следует за вершиной в пути Р, 2;

2)

3)

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

Теорема 14.2. Алгоритм Уоррена вычисляет транзитивное замыкание графа

Доказательство. Необходимо рассмотреть два случая:

Случай 1. Для любых двух вершин s и t в графе G существует ориентированный путь Р из вершины s в вершину t. Пусть — такое первое ребро пути Р (в направлении от s к t), что Тогда из предыдущей леммы следует, что граф, который мы имеем перед началом второго прохода алгоритма Уоррена, содержит ребро где k следует за t в Р, причем или Таким образом, после завершения первого прохода существует такой путь что и каждая вершина следует за в пути Р.

При обработке вершины s во втором проходе ребро встречается первым. Обработка этого ребра вызывает появление ребра так как в графе присутствует ребро Поскольку то ребро в последующем подвергается обработке. Это в свою очередь приводит к введению ребра и т. д. Таким образом, когда обработка вершины завершается, в полученном графе будет присутствовать ребро

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

Ясно, что оба алгоритма Уоршолла и Уоррена имеют в худшем случае сложность Однако алгоритм Уоррена будет выполняться быстрее алгоритма Уоршолла в случае больших разряженных матриц, особенно в страничной среде. Уоррен [14.3] ссылается на другие строкоориентированные алгоритмы.

В работе [14.4] представлен -алгоритм. Он основан на алгоритме «четырех русских» для перемножения булевых матриц.

Автор работы [14.5] предложил -алгоритм для перемножения двух и -матриц. Используя этот алгоритм, авторы работ [14.6, 14.7] представили -алгоритмы для задачи транзитивного замыкания. Другие алгоритмы, основанные на перемножении матриц, предложены в работах [14,8, 14.9]

В работе [14.10] рассматривается алгоритм, основанный на алгоритме Тарьяна для нахождения сильно связных компонент ориентированного графа

(разд. 14.4). Сильно связные компоненты данного графа определяет в качестве первого шага алгоритм Мунро.

Алгоритм Пардома [14.11] во многих случаях требует шагов, хотя худшем случае имеет сложность Однако этот алгоритм гораздо сложнее других алгоритмов транзитивного замыкания.

Недавно Шнорр [14.12] представил алгоритм с предполагаемым временем работы , где — ожидаемое число ребер в транзитивном замыкании.

В работе [14.13] рассматриваются вычислительные эксперименты с несколькими алгоритмами транзитивного замыкания.

<< Предыдущий параграф Следующий параграф >>
Оглавление