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

14.4. Двусвязность и сильная связность

В этом разделе мы рассматриваем алгоритмы Хопкрофта и Тарьяна [14.20] и Тарьяна [14.19] определения двусвязных и сильно связных компонент графа. Эти алгоритмы основываются на поиске в глубину. Мы начинаем обсуждение с алгоритма цвусвязности.

14.4.1. Двусвязность

Напомним (гл. 8), что двусвязный граф — это связный граф без точек сочленения. Максимальный двусвязный подграф графа называется двусвязной компонентой графа

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

Пусть — связный неориентированный граф. Пусть Т — дерево ПВГ этого графа с вершиной в качестве корня. Тогда мы имеем следующее:

Лемма 14.4. Вершина является точкой сочленения графа G тогда и только тогда, когда для некоторого сына s вершины v нет обратных ребер, соединяющих какие-либо потомки s в Т (включая ее саму) с собственным предком

Доказательство. Пусть G — граф, который получается после удаления вершины v из графа G. По определению v — точка сочленения графа тогда и только тогда, когда граф несвязен.

Пусть — сыновья v в Т. Для каждого i, пусть множество потомков вершины s, - (включая ее саму) и пусть G; — подграф G, порожденный множеством вершин Более того, пусть , где и пусть подграф, порожденный множеством вершин Отметим, что все собственные предки v принадлежат множеству

Объединение множеств вершин графов являющихся подграфами графа G, равно множеству вершин графа G. Мы можем показать, что все эти подграфы связны. Далее, в соответствии с теоремой 14.6, не существует ребер, соединяющих вершины, принадлежащие различным графам Отсюда следует, что G будет связен тогда и только тогда, когда для любого существует ребро между вершинами Такое ребро обязательно будет обратным ребром, а вершина b — собственным предком вершины v. Поэтому мы можем сделать вывод о том, что граф G будет связен тогда и только тогда, когда для каждого сына вершины v существует обратное ребро между некоторым потомком вершины (включая ее саму) и собственным предком вершины

Лемма 14.5. Корневая вершина — точка сочленения графа G тогда и только тогда, когда она имеет более одного сына.

Доказательство в этом случае аналогично доказательству леммы 14.4.

В дальнейшем мы будем ссылаться на вершины, указывая ее глубину. Чтобы вложить в процедуру ПВГ критерий, определенный леммами 14.4 и 14.5, мы определяем для каждой вершины v графа существует такое обратное ребро что — потомок — собственный предок v в

Используя значения LOW, определенные выше, мы можем переформулировать критерий, предложенный в лемме 14.4, как следующую теорему:

Теорема 14.8. Вершина — точка сочленения графа G тогда и только тогда, когда v имеет сына s, для которого

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

1. Когда v проходится в ПВГ в первый раз, полагаем равным глубине .

2. Когда рассматривается обратное ребро инцидентное v, полагаем равным наименьшему из текущего значения и глубины да.

3. Когда ПВГ возвращается к у после полного сканирования сына s этой вершины, полагаем равным наименьшему из текущего значения и

Отметим, что для любой вершины v вычисление заканчивается при завершении ее сканирования.

Рассмотрим вопрос о выделении ребер, принадлежащих двусвязным компонентам. Для этого мы используем массив STACK. Вначале массив STACK пуст. По мере просмотра ребер они добавляются в STACK сверху.

Предположим, что ПВГ возвращается в вершину v после полного сканирования сына этой вершины s. В этот момент вычисление завершается. Предположим, обнаружено, что Тогда, согласно теореме 14.8, v — точка сочленения. Далее, если s — первая вершина с этим свойством, то можно легко определить, что ребро вместе с ребрами, инцидентными s и его потомкам, образуют двусвязную компоненту. Эти ребра являются в точности теми ребрами,

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

Например, дерево ПВГ связного графа может иметь вид, изображенный на рис. —двусвязные компоненты в том порядке, в котором они выделяются.

Рис. 14.15. -двусвязные компоненты графа.

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

Алгоритм 14.6. Двусвязность.

S1. G — данный связный граф. Для каждой вершины v графа G положить Положить

S2. Выбрать произвольную вершину, например , с Положить

S3. Если все ребра, инцидентные v, уже помечены как просмотренные, то идти к шагу Иначе выбрать ребро , которое еще не помечено как «просмотренное». Пометить это ребро «просмотренным», добавить его в STACK сверху и идти к шагу

S4. Выполнить следующие действия и идти к шагу

1. Если то положить

2. Если то положить

S5. Если FATHER то идти к шагу иначе идти к шагу

Рис. 14.16. Иллюстрация к алгоритму 14.6.

Значения элементов массива LOW приведены в скобках; — двусвязные компоненты графа.

S6. Если то удалить все ребра из STACK сверху до ребра включительно. (Выделена компонента двусвязности.)

S7. Положить и идти к шагу

S8. (Все компоненты двусвязности выделены.) HALT.

На рис. 14.16 иллюстрируется применение этого алгоритма.

14.4.2. Сильная связность

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

Рассмотрим ориентированный граф . Пусть — сильно связные компоненты графа G. Пусть Т — лес ПВГ графа G, а порожденные подграфы Т с множествами вершин соответственно. Из теоремы 14.7 следует, что — связные графы.

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

Первым шагом в разработке алгоритма сильной связности является определение простого критерия, который можно использовать для выделения корня при выполнении ПВГ. Следующие замечания будут полезны при выводе такого критерия. Они являются прямыми следствиями того факта, что в графе, получаемом с помощью стягивания всех ребер в каждом из множества (разд. 5.1), нет ориентированных циклов.

1. Не существует обратных ребер вида , где до . Другими словами, все обратные ребра, исходящие из вершин множества заканчиваются также в вершинах множества

2. Не существует пересекающих ребер вида , где — предок Таким образом, для каждого пересекающего ребра выполняются следующие два условия:

а. Если для некоторых то находится слева от

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

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

обратного или пересекающего ребра. Отсюда следует, что все ребра такого ориентированного пути обязательно будут принадлежать графу . В качестве непосредственного следствия мы получаем утверждение

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

    (14.3)

Объединяя выражения (14.2) и (14.3), получим следующую теорему, которая характеризует корни сильно связных компонент ориентированного графа:

Теорема 14.9. Вершина v — корень сильно связной компоненты ориентированного графа тогда и только тогда, когда LOWLINK

Следующие действия могут быть полезны для вычисления LOWLINK при выполнении ПВГ.

1. При прохождении первый раз устанавливаем LOWLINK равным глубине V.

2. Если рассматривается обратное ребро (и, да), то полагаем LOWLINK равным минимуму из его текущего значения и глубины да.

3. Если исследуется пресекающее ребро (и, да), для которого v и w принадлежат одной и той же сильно связной компоненте, то полагаем LOWLINK равным минимуму из его текущего значения и глубины да.

4. Когда мы возвращаемся в v после полного сканирования сына s вершины v, то полагаем LOWLINK равным минимуму из его текущего значения и LOWLINK

Для выполнения шага 3 необходимо проверить, находится ли вершина w в той же сильно связной компоненте, что и v. Для этого мы используем массив STACK I, в который вершины графа G добавляются в порядке прохождения их при ПВГ. STACK1 используется также при определении вершин, принадлежащих какой-либо сильно связной компоненте.

Пусть v — первая вершина при поиске в глубину, для которой выполнено соотношение LOWLINK Тогда, согласно теореме 14.9, v — корень и фактически является В этот момент вершины сверху STACK1 до вершины v включительно являются вершинами, образующими граф Таким образом, граф G легко выделяется. Эти вершины удаляются из STACK1. После этого алгоритм применяется к графу G, который получается из графа G удалением вершин графа

Положим, как и при рассмотрении реализации шага 3 в вычислении LOWLINK, что и (и, да) — пересекающее ребро, встретившееся при рассмотрении ребер, инцидентных v. Предположим, что да не принадлежит той же самой сильно связной компоненте, которой принадлежит а. Тогда она должна принадлежать сильно связной компоненте корень которой находится левее - (см. выше замечание 2а). Вершины такой компоненты должны быть уже выделены и более не должны находиться в STACK1. Таким образом, да будет в той же сильно связной компоненте, что и v, тогда и только тогда, когда да присутствует в STACK1.

Представим описание алгоритма сильной связности. Он совпадает с алгоритмом 14,5 с точностью до включения соответствующих шагов для вычисления

величин LOWLINK и выделения вершин различных сильно связных компонент. Мы используем в этом алгоритме массив POINT. Вначале для всех вершин V. Это указывает на то, что ни одна из вершин еще не включена в массив устанавливается в 1, когда у добавляется в STACK1, и в 0, когда удаляется из STACK 1.

Алгоритм 14.7. (Сильная связность.)

51. G — данный ориентированный граф. Для каждой вершины v в G положить Положить и STACK1

52. Выбрать произвольную вершину, например , с MARK Положить Добавить в STACK 1, положить

53. Если все ребра, инцидентные у, уже помечены как «просмотренные», то идти к шагу Иначе выбрать ребро которое еще не помечено как «просмотренное». Пометить его «просмотренным» и идти к шагу

54. Выполнить следующие действия и идти к шагу

1) Если MARK то положить Добавить w в STACK 1 и положить POINT

2) Если то положить LOWLINK

55. Если LOWLINK то удалить все вершины сверху STACK1 до вершины у включительно. (Эти вершины образуют сильно связную компоненту). Затем положить POINT для всех вершин удаляемых из STACK 1.

56. Если FATHER идти к шагу иначе положить

57. Если для каждой вершины то идти к шагу иначе идти к шагу

58. (Все сильно связные компоненты выделены.) HALT.

Рис. 14.17 иллюстрирует работу этого алгоритма.

Рис. 14.17. Иллюстрация алгоритма 14.7.

Значения элементов массива LOWLINK приведены в скобках, — сильно связные компоненты графа.

14.5. Сводимость графа программы

Графом программы называется ориентированный граф G с выделенной вершиной s, из которой существует ориентированный путь в любую другую вершину графа G. Другими словами, любая

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

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

Многие методы оптимизации кода применимы только тогда, когда граф программы обладает специальным свойством, называемым сводимостью [14.21-14.29].

Сводимость графа программы G определяется исходя из следующих двух преобразований графа

Удалить петлю из графа

Если — единственное ребро, входящее вши то удалить вершину . Для каждого ребра () графа G добавить ребро если еще не принадлежит графу G. (Это преобразование называется коллапсированием вершины w в вершину )

Рис. 14.18. а — сводимый граф программы G; значения элементов массива приведены в скобках; о — граф, получающийся после коллапсировання в графе G вершины 5 в вершину 4.

Например, коллапсирование вершины в вершину 4 в графе программы, изображенном на рис. 14.18, а, приводит к графу на рис. 14.18, б.

Граф программы сводим, если его можно преобразовать в граф, состоящий только из вершины s, многократным применением преобразований .

Например, граф на рис. 14.18, а является сводимым. Это можно установить последовательным применением коллапсирования вершин в следующем порядке: 5, 8, 3, 10, 9, 7, 6, 2.

Кок [14.22] и Аллен [14.27] первыми сформулировали понятие «сводимость», и их определение сделано на основе метода, называемого интервальным анализом. Определение, приведенное выше, предложено Хектом и Ульманом [14.30] и эквивалентно определению Кока и Аллена.

Если граф сводим, то можно показать [14.30], что любой граф G, получаемый из графа G с помощью одного или нескольких применений преобразований и также сводим. Таким образом, порядок применения преобразований при проверке сводимости несуществен. Некоторые интересные классы программ, например программы «go-to-less», приводят к графам, которые обязательно сводимы [14.30], и большинство программ можно промоделировать сводимым графом посредством процесса «расщепления вершин» [14.31].

Предположим, что мы желаем проверить сводимость графа G. Это можно осуществить первоначальным удалением петель с помощью преобразования и последующим подсчетом числа ребер, заходящих в каждую вершину. Затем мы можем найти вершину w с единственным заходящим в него ребром и применить преобразование коллапсируя w в v. Мы можем повторять этот процесс до тех пор, пока граф не будет сжат полностью либо пока не обнаружится, что он несводим. Ясно, что каждое применение преобразования требует шагов, где n — число вершин графа G. Таким образом, сложность этого алгоритма . Хопкрофт и Ульман [14.32] улучшили этот алгоритм до сложности , где — число ребер графа G. Тарьян [14.33, 14.34] позже представил алгоритм, который был лучше алгоритма Хопкрофта и Ульмана.

Хект и Ульман [14.30, 14.35] дали несколько полезных структурных характеризаций графов программ. Одна из них определяется следующей теоремой:

Теорема 14.10. Пусть G — граф программы с начальной вершиной Он сводим тогда и только тогда, когда не существует вершин ориентированных путей из s в v и из s в да, а также такого ориентированного цикла С, содержащего v и w, что он не имеет общих ребер, а только по одной общей вершине с каждым из путей (рис. 14.19).

Доказательство этой теоремы приведено в работах [14.30, 14.36].

Перейдем к обсуждению алгоритма Тарьяна для проверки сводимости графа программы. Этот алгоритм базируется на характеризации сводимых графов, которую мы докажем, применяя теорему 14.10, и использует ПВГ. Наше обсуждение основывается на данных работы [14.33].

Пусть G — граф программы с начальной вершиной s. Пусть Т — дерево ПВГ графа G с s в качестве корня. Далее мы будем ссылаться на вершины по их глубине.

Рис. 14.19. Основной несводимый граф.

Теорема 14.11. Граф G сводим тогда и только тогда, когда он не содержит ориентированного пути Р из s в некоторую такую вершину v, что v является собственным предком в Т некоторой другой вершины из Р.

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

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

Пусть для любой вершины v HIGHPT — такой наивысший собственный предок v, что существует ориентированный путь из о в HIGHPT и Р не включает в себя собственных предков v, исключая HIGHPT 1 (и). Мы полагаем HIGHPT если не существует ориентированного пути из v в какой-либо - собственный предок v. На рис. 14.18, а указаны в скобках значения HIGHPT 1 для соответствующих вершин.

Отметим, что при вычислении HIGHPT мы можем игнорировать прямые ребра, так как если Р — ориентированный путь из и в и Р не содержит предков v, кроме , то мы можем сопоставить каждому прямому ребру из Р путь из ребер дерева или части его и имеем, кроме того, ориентированный путь из у в , который не содержит предков v, кроме .

Алгоритм Тарьяна основан на следующей характеризации графов программ:

Теорема граф тогда и только тогда, когда нет таких вершины v и ребра (), заходящего в v, что (и), где w — наивысший общий предок и и V.

Доказательство. Предположим, что G — несводимый граф. Тогда, согласно-теореме 14.11, существует ориентированный путь Р из s в и, где v — собственный предок некоторой другой вершины из Р. Выберем наиболее короткий путь Р. Пусть да — первая вершина Р, которая является потомком v. Тогда все вершины, кроме v, которые следуют за да в Р, являются потомками . Другими словами, часть Р из да в и не включает собственных предков вершины да, кроме v. Поэтому HIGHPT Таким образом, , HIGHPT и ребро Р, входящее в удовлетворяют условию теоремы.

Предположим, что условия теоремы выполняются. Тогда ребро не является обратным ребром, потому что в таком случае наибольший общий предок w для и и и равен v и Таким образом, — либо прямое, либо пересекающее ребро. Пусть ориентированный путь из и в HIGHPT1 (у), который не проходит ни через один собственный предок v, кроме . Тогда ориентированный путь, состоящий из ребер дерева, из s в и с последующим ребром и путем удовлетворяет условию теоремы 14.11. Поэтому G — несводимый граф.

Отсюда должно быть ясно, что проверка сводимости графа G, использующая приведенную выше теорему, включает следующие основные шаги:

1. Выполнить ПВГ на в качестве корня.

2. Вычислить для каждой вершины у графа

3. Для пересекающих ребер проверить при вычислении выполнение условий теоремы 14.12.

4. Для прямых ребер проверить после вычисления HIGHPT выполнение условий теоремы 14.12.

Отметим, что, как мы видели раньше, прямые ребра могут игнорироваться при вычислении HIGHPT. Из доказательства теоремы 14.12 следует, что обратные ребра не нужны при проверке условий упомянутой теоремы.

Для вычисления значений HIGHPT мы упорядочиваем обратные ребра по глубине у. Затем мы обрабатываем обратные ребра в порядке от большей к меньшей вершине у. Первоначально все вершины не помечены. Чтобы обработать обратное ребро , мы должны подниматься вдоль пути в дереве из и в у, помечая каждую текущую непомеченную вершину глубиной вершины у. (Мы не помечаем саму вершину и.) Если вершина w уже помечена, то мы проверяем все пересекающие ребра, заходящие в w. Если — такое пересекающее ребро (рис. 14.20), то мы поднимаемся вдоль пути в дереве из 2 в у, помечая каждую непомеченную вершину глубиной вершины у. Если z не является потомком у, то граф G несводим по теореме 14.12 и вычисление прекращается. Мы продолжаем помечать вершины, пока не будут рассмотрены все пересекающие ребра, входящие в уже помеченные вершины, после чего мы рассматриваем следующее обратное ребро. При рассмотрении всех обратных ребер метки будут представлять собой значения HIGHPT для соответствующих вершин. Каждая непомеченная вершина имеет значение HIGHPT, равное 0.

Рис. 14.20.

Опишем алгоритм Тарьяна проверки сводимости. В этом алгоритме мы используем очередей, называемых ячейками, по одной для каждой вершины. Ячейка BUCKET (w), соответствующая

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

Алгоритм 14.8. (Сводимость графа программы (Тарьян).)

S1. Выполнить ПВГ на данном графе программы G на вершинах. Обозначить вершины их глубинами. Упорядочить обратные ребра графа G по глубинам v.

S2. Для положить HIGHPT «пустой список».

S3. Добавить все обратные ребра в BUCKET .

S4. Положить

Если BUCKET пуст, то идти к шагу иначе идти к шагу

Положить Если то идти к шагу иначе идти к шагу S5.

S7. (Начало обработки нового обратного ребра.) Удалить обратное ребро из BUCKET и положить СНЕСК

S8. Если CHECK пуст (обработка обратного ребра завершена), то идти к шагу иначе идти к шагу

Удалить и из CHECK.

10. Если и — потомок да, то идти к шагу иначе идти к шагу S17.

S11. Если то идти к шагу иначе идти к шагу

Если HIGHPT то идти к шагу иначе идти к шагу S15.

S13. Положить HIGHPT .

S14. Для каждого пересекающего ребра добавить v в CHECK

S15. Положить . Идти к шагу S11.

S16. Если для каждого прямого ребра (граф сводим), то HALT, иначе идти к шагу S17.

S17. HALT, Граф несводим.

Отметим, что шаг в алгоритме 14.8 требует, чтобы мы имели возможность определить, является ли вершина w потомком другой вершины и. Пусть — число потомков вершины и в Т. Тогда мы можем показать, что w — потомок и тогда и только тогда, когда (упражнение 14.3). Мы можем вычислить непосредственно при выполнении ПВГ.

Эффективность алгоритма 14.8 существенно зависит от эффективности вычисления HIGHPT1. Чтобы сделать вычисление эффективным, необходимо избежать проверки вершин, которые уже были помечены. Тарьян предложил процедуру для обеспечения этого. Следующее рассуждение образует основу этой процедуры.

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

множества, пронумерованные в пределах Вершина будет находиться в множестве v, т. е. в SET (у), если v является наибольшим непомеченным собственным предком w. Так как вершина 1 никогда не помечается, то каждая вершина всегда находится в каком-либо множестве. Первоначально вершина помещается в множество, номер которого является номером ее отца в Т. Таким образом, первоначально помещается в SET (FATHER ) для п. Чтобы пройти шаг мы находим номер и множества, содержащего и, и считаем его новым и. Когда и становится помеченной, мы соединяем множества, пронумерованные и и и и формируем новое множество с номером и. Таким образом, и становится наибольшим непомеченным собственным предком всех вершин из старого множества SET (и).

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

S12. Положить номер множества, содержащего и.

S13. Если HIGHPT то идти к шагу S 14, иначе идти к шагу SI6.

S14. Положить 1) HIGHPT (и).

S15. Для каждого пересекающего ребра добавить v в CHECK

S16. Положить Идти к шагу

Можно показать, что такой модифицированный способ вычисления требует объединений множеств, выполнений шага теоретико-множественных операций. Если мы используем алгоритм Фишера [14.37], а также Хопкрофта и Ульмана [14.38] для выполнения объединений непересекающихся множеств и шага то из анализа, проведенного Тарьяном [14. 39], следует, что алгоритм сводимости имеет сложность , где а — очень медленно растущая функция, которая связана с обращением функции Аккермана и определяется следующим образом: Функция Аккермана имеет вид

Отметим, что функция Аккермана является очень быстрорастущей функцией. Поэтому очень большое число, и можно показать, что а если . Алгоритм выполнения теоретико-множественных операций, упомянутый ранее, описан в работах [14.40, 14.41]. Алгоритм 14.8 неконструктивен в том смысле, что он не дает нам порядка, в котором необходимо

коллапсировать вершины при сведении сводимого графа. Однако, как мы увидим позже, эту информацию можно легко получить при работе алгоритма.

Будем приписывать вершинам при выполнении ПВГ номера, называемые SNUMBER, со значениями в пределах в порядке завершения сканирования вершин. Фактически это тот же порядок, что и порядок, в котором устанавливаются в 1 соответствующие элементы массива SCAN в алгоритме 14.5. Можно легко проверить что

1) если — ребро дерева, то SNUMBER

2) если — пересекающее ребро, то SNUMBER ;

3) если — обратное ребро, то SNUMBER

4) если — прямое ребро, то SNUMBER На рис. 14.21 в скобках указаны величины SNUMBER для соответствующих вершин графа, представленного на рис. 14.18, а.

Предположим, что используется алгоритм сводимости и каждый раз, когда мы помечаем вершину v, мы приписываем ей пару . Когда алгоритм заканчивается, мы упорядочиваем вершины так, что вершина, помеченная парой появляется раньше вершины, помеченной парой тогда и только тогда, когда или Этот порядок вершин называется порядком редукции. Отметим, что непомеченной вершине v приписывается пара

Рис. 14.21. Граф рис. 14.18, а со значениями элементов массива SNUMBER, указанными в скобках.

Предположим, что порядок редукции для сводимого графа программы G. Пусть Т — дерево 1 ПВГ для графа G с вершиной s в качестве корня. Используя теорему 14.12 и свойства чисел SNUMBER, указанные ранее, легко показать, что ребро дерева является единственным ребром, заходящим в Предположим, что мы коллапсируем вершину в вершину и, и пусть G — получаемый сводимый граф. Пусть также Т — дерево, получаемое из Т сжатием ребра (). Тогда ясно, что Т—дерево ПВГ для графа

1. Пересекающее ребро G соответствует пересекающему ребру либо прямому ребру графа G либо не имеет соответствия.

2. Прямое ребро графа G соответствует прямому ребру графа G либо не имеет соответствия.

3. Обратное ребро графа G соответствует обратному ребру графа G либо не имеет соответствия.

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

Теорема 14.13. Если граф программы G сводим, то мы можем коллапсировать вершины графа G в порядке редукции, используя преобразование (с промежуточным применением преобразования ). Например, из величин HIGHPT 1, приведенных на рис. 14.18, а, и величин SNUMBER, приведенных на рис. 14.21, порядком редукции для графа с рис. 14.18, а является следующая последовательность: 4, 5, 3, 8, 10, 9, 7, 6, 2.

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