Орграфы и DAG-графы

Разбить на страницы

Показывать лекцию целиком

Если учитывать порядок, в котором задаются две вершины каждого ребра графа, получится совершенно другой комбинаторный объект — ориентированный граф (directed graph), или орграф (digraph). Пример орграфа приведен на рис 19.1. В орграфах обозначение s-t описывает ребро, ведущее из вершины s в вершину t, но оно не дает никакой информации о том, существует ли ребро, ведущее из t в s. Любые две вершины орграфа могут быть связаны одним из четырех видов отношений: ребер между ними нет; имеется ребро s-t, ведущее из s в t; имеется ребро t-s, ведущее из t в s; и имеются два ребра s-t и t-s, которые означают связь в обоих направлениях. Требование однонаправленности естественно для многих приложений, оно легко реализуется и на вид вполне безобидно. Однако оно означает неявное наличие дополнительной комбинаторной структуры, которая существенно влияет на наши алгоритмы и делает работу с орграфами весьма непохожей на работу с неориентированными графами. Обработка орграфов похожа на езду по городу, в котором все улицы имеют одностороннее движение, а направление движения не задается каким-то общим принципом. Можно себе представить, с какими трудностями можно столкнуться в таком городе, если понадобится проехать из одной его точки в другую.

(рис 19.1)

Ориентированный граф (орграф)

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

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

Более современный пример для этой классической модели — интернет, где вершины представляют веб-страницы, а ребра — ссылки между страницами. В разделе 19.4 мы рассмотрим другие примеры для более абстрактных ситуаций.

Довольно часто направление ребер выражает отношение предшествования. Например, орграф может моделировать производственную линию: вершины обозначают этапы выполняемой работы, а ребро из вершины s в вершину t означает, что этап, соответствующий вершине s, должен быть выполнен до выполнения этапа, соответствующего вершине t. Другой способ моделирования той же ситуации заключается в использовании диаграммы PERT (Project Evaluation and Review Technique — сетевое планирование и управление): здесь уже ребра представляют этапы работы, а вершины неявно задают отношение предшествования (все работы, сходящиеся в конкретной вершине, должны быть завершены до начала работ, исходящих из этой вершины). Как узнать, когда нужно приступать к выполнению каждого из этих этапов, чтобы не нарушить ни одно из отношений предшествования? Это так называемая задача составления расписания (scheduling problem). Она не имеет смысла, если в орграфе имеется цикл, и в таких ситуациях мы работаем с DAG-графами (directed acyclic graph — ориентированный ациклический граф). В разделах 19.5—19.7 мы рассмотрим основные свойства DAG-графов и алгоритмы решения простой задачи составления расписания — топологической сортировки (topological sorting). На практике в задачах составления расписаний обычно учитываются веса вершин или ребер, которые моделируют время или стоимость выполнения каждого этапа. Такие задачи будут изучаться в и .

Число возможных орграфов поистине огромно. Каждое из возможных V² ориентированных ребер (считая и петли) может присутствовать или отсутствовать — таким образом, общее количество разных орграфов равно $$$2^{V^{2}}$$$. С увеличением количества вершин это число стремительно возрастает (см. рис 19.2) уже при небольших значениях V, даже по сравнению с количеством различных неориентированных графов. Как и в случае неориентированных графов, количество изоморфных друг другу графов (вершины одного из изоморфных графов можно переименовать таким образом, чтобы получить другой) намного меньше, однако воспользоваться этим сокращением невозможно, т.к. нам неизвестен эффективный алгоритм выявления изоморфизма графов.

(рис 19.2) Подсчет количества графов

Количество различных неориентированных графов с Vвершинами огромно, даже при малых значениях V, но количество различных орграфов с Vвершинами гораздо больше. Количество неориентированных определяется формулой 2<sup>V(V+1)/2</sup>, а количество орграфов — формулой $$$2^{V^{2}}$$$ 2v2.

Разумеется, любая программа обрабатывает лишь мизерную часть возможных орграфов; эти числа так велики, что практически наверняка ни один конкретный орграф не окажется в числе обработанных любой заданной программой. В общем случае трудно как-то охарактеризовать орграфы, с которыми приходится сталкиваться на практике, поэтому приходится разрабатывать алгоритмы так, чтобы они могли справиться с любым заданным орграфом. С одной стороны, мы уже сталкивались с подобными ситуациями (например, ни одна программа сортировки не обрабатывала все 1000! перестановок 1000 элементов). С другой стороны, совсем не воодушевляет тот факт, что, например, даже если все электроны вселенной были бы суперкомпьютерами, способными обрабатывать 10¹⁰ графов за секунду в течение всей жизни Вселенной, то эти суперкомпьютеры не просмотрят и 10^-100 процента орграфов, состоящих из 10 вершин (см. упражнение 19.9).

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

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

Упражнения

19.1. Найдите в интернете пример крупного орграфа — возможно, графа транзакций в какой-то онлайновой системе или орграфа, определяемого ссылками веб-страниц.

19.2. Найдите в интернете пример крупного DAG-графа — возможно, графа определения функций в крупной программной системе или ссылок в каталоге крупной файловой системы.

19.3. Постройте таблицу, аналогичную представленной на рис 19.2, но без учета графов и орграфов с петлями.

19.4. Каково количество орграфов, содержащих V вершин и E ребер?

19.5. Сколько орграфов соответствует каждому неориентированному графу, содержащему V вершин и E ребер?

19.6. Сколько цифр содержит десятичное число, равное количеству орграфов с V вершинами и E ребрами?

19.7. Начертите неизоморфные орграфы, содержащие три вершины.

19.8. Каково количество различных орграфов, содержащих V вершин и E ребер, если считать орграфы различными только если они не изоморфны.

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

Глоссарий и правила игры

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

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

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

Определение 19.2. Ориентированный путь (directedpath) в орграфе — это список вершин, в котором имеется (ориентированное) ребро орграфа, соединяющее каждую вершину списка со следующим элементом этого списка. Мы говорим, что вершина t достижима (reachable) из вершины s, если существует ориентированный путь из s в t.

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

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

Конечно, подобные примеры подчеркивают различия, однако важно помнить, что задача, трудная для человека, может быть, а может и не быть трудной для программы — к примеру, написание класса DFS, предназначенного для поиска циклов в орграфе, не труднее задачи поиска циклов в неориентированном графе. И все же орграфы и неориентированные графы во многом существенно различаются. Например, то, что в каком-то орграфе вершина t достижима из вершины s, ничего не говорит о том, достижима ли s из t. Это различие очевидно, но, как мы увидим, весьма существенно.

Как было сказано в , представления, используемые для орграфов, по существу те же, что и представления, используемые для неориентированных графов. Вообще-то они даже более наглядны, поскольку каждое ребро в них представлено только один раз — см. рис 19.4. В представлении списками смежности ребро s-t представляется узлом, содержащим t в связном списке, который соответствует вершине s.

(рис 19.3) Решетчатый орграф

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

В представлении матрицей смежности приходится использовать полную матрицу размером V х V, и ребро представляется в ней единицей на пересечении строки s и столбца t. Единицы на пересечении строки t и столбца s нет, если в графе нет ребра t-s. В общем случае матрица смежности для орграфа не симметрична относительно главной диагонали.

В этих представлениях нет различий между неориентированными графами и ориентированными графами с петлей в каждой вершине и двумя ориентированными ребрами для каждого ребра, соединяющего разные вершины неориентированного графа (по одному в каждом направлении). Поэтому алгоритмы, которые мы разработаем в этой главе для орграфов, можно использовать и для обработки неориентированных графов — естественно, при соответствующей интерпретации результатов. Кроме того, в качестве основы для программ обработки орграфов мы будем использовать некоторые программы из : программы 17.7—17.10, реализующие классы DenseGRAPH и SparseMultiGRAPH, строят орграфы, если конструктору передается во втором аргументе значение true.

(рис 19.4) Представления орграфа

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

Степень захода (indegree) вершины орграфа есть количество ориентированных ребер, которые ведут в эту вершину. Степень выхода (outdegree) вершины орграфа есть количество ориентированных ребер, которые ведут из этой вершины. Никакая вершина орграфа не достижима из вершины со степенью выхода 0 — такая вершина называется сток (sink); вершина со степенью захода 0 называется исток (source), она не достижима ни из какой вершины орграфа. Орграф, в котором разрешены петли, и степень выхода каждой вершины равна 1, называется отображением (map) (функция из множества целых чисел от 0 доV— 1 на это же множество). Используя векторы, индексированные именами вершин, можно подсчитать степени захода и выхода для каждой вершины и найти истоки и стоки, потратив на это линейное время и объем памяти, пропорциональный V (см. упражнение 19.19).

Обращение (reverse) орграфа — это орграф, который получается при изменении направлений всех ребер орграфа на обратные. На рис 19.5 показано обращение орграфа с рис 19.1 и его представления. Обращения орграфов используются в алгоритмах тогда, когда нужно знать, откуда исходят ребра, поскольку стандартные представления показывают нам только куда они идут. При обращении орграфа степени выхода и захода меняются местами.

В случае представления матрицей смежности обращение можно вычислить, создав копию матрицы и транспонировав ее (поменяв местами строки и столбцы).

(рис 19.5) Обращение орграфа

Изменение направлений ребер орграфа на обратные соответствует транспонированию матрицы смежности, но требует перестроения списков смежности (см. рис 19.1 и рис 19.4).

Если известно, что граф в дальнейшем не будет изменяться, то можно использовать его обращение без каких-либо дополнительных вычислений — просто переставляя вершины в обращениях к ребрам при работе с обращенным графом. Например, ребро s-t орграфа G задано значением 1 в элементе adj[s][t]. Значит, если бы мы вычислили обращение R орграфа G, оно содержало бы 1 в элементе adj[t][s]. Но ведь это можно и не делать: если в реализации клиента выполняется проверка ребра edge(s,t), то для работы с обращением достаточно заменить каждую такую ссылку на edge(t,s). Несмотря на очевидность, этой возможностью часто пренебрегают. Однако в случае представления списками смежности обращение представляет собой совершенно другую структуру данных, и, как видно из программы 19.1, для ее построения нужно время, пропорциональное количеству ребер орграфа.

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

Программа 19.1. Обращение орграфа

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

  template <class inGraph, class outGraph>
  void reverse(const inGraph G, outGraph R)
    { for (int v = 0; v < G.V(); v++)
        { typename inGraph::adjIterator A(G, v);
          for (int w = A. beg() ; !A.end() ;
            w = A.nxt())
          R.insert(Edge(w, v));
        }
    }

В орграфах, по аналогии с неориентированными графами, мы говорим об ориентированных циклах (ориентированные пути, ведущие от вершины к ней самой) и о простых ориентированных путях и циклах (в которых все вершины и ребра различны). Обратите внимание, что в орграфе возможен цикл s-t-s длиной 2, но циклы в неориентированных графах должны содержать минимум три различных вершины. Во многих приложениях орграфы не должны содержать циклы, и мы имеем дело с другим видом комбинаторного объекта.

Определение 19.3. Ориентированный ациклический граф (directed acyclic graph, DAG) — это орграф, не содержащий направленных циклов.

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

(рис 19.6) Ориентированный ациклический граф (DAG-граф)

В этом графе нет циклов, хотя это не очевидно ни из списка ребер, ни даже из чертежа графа.

Направленные циклы крайне важны для понимания связности орграфов, не являющихся DAG-графами. Неориентированный граф связен, если существует путь из каждой его вершины в любую другую вершину; но для орграфов используется несколько другое определение:

(рис 19.7) Терминология орграфов

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

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

Определение сильно означает, что каждая пара вершин связана более сильным отношением, чем достижимость. Мы говорим, что вершины s и t любого графа является сильно связанными (strongly connected), или взаимно достижимыми (mutually reachable), если существует ориентированный путь из s в t и ориентированный путь из t в s. (Из нашего соглашения, что каждая вершина достижима из самой себя, следует, что каждая вершина сильно связана сама с собой.) Орграф сильно связен тогда и только тогда, когда сильно связаны все его пары вершин. То есть сильно связные орграфы определяет свойство, само собой разумеющееся в случае связных неориентированных графов: если существует путь из s в t, то существует и путь из t в s.

В случае неориентированных графов это свойство выполняется автоматически: один и тот же путь, пройденный в обратном направлении, отвечает всем требованиям определения, но в случае орграфа это уже будет другой путь.

О сильной связности пары вершин можно сказать и по-другому: они принадлежат некоторому ориентированному циклическому пути. Напомним, что мы используем термин циклический путь (cyclic path), а не просто цикл (cycle), чтобы показать, что путь не обязательно должен быть простым. Например, на рис 19.1 вершины 5 и 6 сильно связаны, поскольку вершина 6 достижима из вершины 5 по ориентированному пути 5-4-2-0-6, а 5 достижима из 6 по ориентированному пути 6-4-3-5. Из существования этих путей следует, что вершины 5 и 6 принадлежат ориентированному циклическому пути 5-4-2-0-6-4-3-5, но не принадлежат никакому (простому) ориентированному циклу. Понятно, что ни один DAG-граф, содержащий более одной вершины, не может быть сильно связным.

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

Лемма 19.1. Орграф, не являющийся сильно связным, состоит из множества сильно связных компонентов (strongly connected component) (или, для краткости, сильных компонентов — strong component), которые представляют собой максимальные сильно связные подграфы, и множества ориентированных ребер, ведущих из одного компонента в другой.

Доказательство. Подобно компонентам неориентированных графов, сильные компоненты в орграфах являются подграфами, которые индуцированы подмножествами вершин: каждая вершина — это в точности один сильный компонент. Чтобы доказать этот факт, сначала заметим, что каждая вершина принадлежит как минимум одному сильному компоненту, который содержит (хотя бы) саму вершину. Далее отметим, что каждая вершина принадлежит максимум одному сильному компоненту: если бы какая-либо вершина принадлежала сразу двум различным компонентам, то существовал бы путь, проходящий через эту вершину и соединяющий вершины этих компонентов друг с другом в обоих направлениях, что противоречит предположению о максимальности обоих компонентов. $$$\blacksquare$$$

Например, орграф, который состоит из единого направленного цикла, содержит в точности один сильный компонент. Но ведь и каждая вершина в DAG-графе — это сильный компонент, поэтому каждое ребро в DAG-графе ведет из одного компонента в другой. В общем случае не все ребра орграфа принадлежат сильным компонентам. Это отличается от ситуации для связных компонентов в неориентированных графах — в них каждая вершина, а также каждое ребро принадлежит некоторому связному компоненту — но аналогично ситуации для реберно-связных компонентов в неориентированных графах. Сильные компоненты в орграфах соединены между собой ребрами, которые ведут из вершины одного компонента в вершину другого без обратных ребер.

Лемма 19.2. Если для заданного орграфа D определить другой орграф K(D), в котором каждая вершина соответствует одному из сильных компонентов орграфа D, а каждое ребро соответствует одному из ребер орграфа D, которое соединяет вершины различных сильных компонентов (соединяет вершины в K, соответствующие сильным компонентам, которые он соединяет в D), то K(D) будет DAG-графом (который мы будем называть коренным DAG-графом (kernel DAG), или ядерныым DAG, графа D).

Доказательство. Если бы K(D) содержал направленный цикл, то вершины двух различных сильных компонентов орграфа D принадлежали бы одному направленному циклу, а это противоречит условию. $$$\blacksquare$$$

На рис.19.8 показаны сильные компоненты и коренной DAG-граф для некоторого орграфа. Мы рассмотрим алгоритмы поиска сильных компонентов и построения коренных DAG-графов в разделе 19.6.

(рис 19.8) Сильные компоненты и коренной DAG

Рассматриваемый орграф (вверху) состоит из четырех сильных компонентов, которые определяются массивом id (в центре), индексированным именами вершин (в качестве индексов взяты произвольные целые числа). Компонент 0 содержит вершины 9, 10, 11 и 12; компонент 1 состоит из единственной вершины 1; компонент 2 содержит вершины 0 , 2 , 3, 4, 5 и 6, а компонент 3 состоит из вершин 7 и 8. Если начертить граф, определяемый ребрами между различными компонентами, то получится DAG-граф (внизу).

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

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

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

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

Нам потребуется поддержка операций АТД орграфа, которые принимают в качестве аргументов две вершины s и t и позволяют проверить

достижима ли t из s;

являются ли s и t сильно связными (взаимно достижимыми).

Какие ресурсы мы готовы выделить для выполнения этих операций? Как было показано в разделе 17.5 , простое решение задачи связности в неориентированных графах обеспечивалось поиском в глубину. При этом требовалось время, пропорциональное V, но при готовности выполнить предварительную обработку за время, пропорциональное V + E, и выделить объем памяти, пропорциональный V, можно отвечать на запросы о связности графа за постоянное время. Ниже в этой главе мы изучим алгоритмы выявления сильной связности, которые имеют такие же характеристики производительности.

Однако главная трудность в том, что ответы на запросы о достижимости в орграфах получить намного сложнее, чем на запросы о связности или сильной связности. В этой главе мы изучим классические алгоритмы, для выполнения которых требуется время, пропорциональное VE, и объем памяти, пропорциональный V², разработаем реализации с постоянным временем и линейным расходом памяти и времени на предварительную обработку при запросах о достижимости на орграфах определенного типа, и рассмотрим трудности достижения этой оптимальной производительности для всех орграфов.

Упражнения

19.10. Приведите структуру списков смежности, построенных программой 17.9 для орграфа

3-71-47-80-55-23-82-90-64-92-66-4.

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

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

19.13. Напишите программу, которая генерирует орграфы, соединяя вершины, расположенные на решетке $$$\sqrt{V}\times \sqrt{V}$$$, с соседними вершинами случайно направленными ребрами (см. рис 19.3).

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

19.15. Измените программу из упражнения 19.14, чтобы каждое дополнительное ребро из вершины s в вершину t появлялось с вероятностью, обратно пропорциональной евклидову расстоянию между s и t.

19.16. Напишите программу, которая генерирует в единичном интервале V случайных интервалов длиной d каждый, после чего строит орграф с ребром из интервала s в интервал t тогда и только тогда, когда хотя бы одна из граничных точек s попадает в t (см. упражнение 17.75). Определите, как выбрать d, чтобы ожидаемое количество ребер было равно E. Протестируйте свою программу, как описано в упражнении 19.11 (для разреженных орграфов) или в упражнении 19.12 (для насыщенных орграфов).

19.17. Напишите программу, которая выбирает V вершин и E ребер из реального орграфа, найденного в упражнении 19.1. Протестируйте свою программу, как описано в упражнении 19.11 (для разреженных орграфов) или 19.12 (для насыщенных орграфов).

19.18. Напишите программу, которая с одинаковой вероятностью строит любой из возможных орграфов с V вершинами и с E ребрами (см. упражнение 17.70). Протестируйте свою программу, как описано в упражнении 19.11 (для разреженных орграфов) или 19.12 (для насыщенных орграфов).

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

19.20. Воспользуйтесь программой из упражнения 19.19, чтобы найти среднее количество истоков и стоков в различных видах орграфов (см. упражнения 19.11—19.18).

19.21. Покажите структуру списков смежности, которая получится при построении обращения орграфа

3-71-47-80-55-23-82-90-64-92-66-4

с помощью программы 19.1.

19.22. Опишите обращение отображения.

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

19.24. Напишите альтернативную реализацию класса из упражнения 19.23, которая поддерживает обе ориентации ребер в списках смежности.

19.25. Опишите семейство сильно связных орграфов с V вершинами без (простых) направленных циклов длиной больше 2.

19.26. Приведите сильные компоненты и коренной DAG для орграфа

3-71-47-80-55-23-82-90-64-92-66-4.

19.27. Приведите коренной DAG решетчатого орграфа с рис 19.3.

19.28. Сколько графов имеют V вершин, каждая из которых имеет степень выхода, равную k?

19.29. Каково ожидаемое количество различных представлений случайного орграфа списками смежности? Указание. Разделите общее количество возможных представлений на общее количество орграфов.

Анатомия DFS в орграфах

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

В неориентированных графах имеются два представления каждого ребра, но второе представление, которое встречается при поиске в глубину, всегда приводит в помеченную вершину и поэтому игнорируется (см. ). В орграфе имеется только одно представление каждого ребра, поэтому можно было бы надеяться на упрощение алгоритмов DFS в орграфах. Однако орграфы сами являются более сложными комбинаторными объектами, так что эти надежды не оправдываются. Например, деревья поиска, которые мы используем для понимания функционирования алгоритма, имеют в случае орграфов более сложную структуру, чем для неориентированных графов. И это усложняет разработку алгоритмов для работы с орграфами. Как мы вскоре убедимся, сделать какие-то выводы об ориентированных путях в орграфах гораздо труднее, чем о путях в неориентированных графах.

Как и в , мы воспользуемся двумя терминами. Термин стандартный поиск в глубину по спискам смежности (standard adjacency-lists DFS) будет обозначать процесс вставки последовательности ребер в АТД орграфа, представленного списками смежности (второй аргумент конструктора из программы 17.9 имеет значение true), с последующим выполнением поиска в глубину — например, с помощью программы 18.3. Параллельный термин стандартный поиск в глубину по матрице смежности (standard adjacency-matrix DFS) будет обозначать процесс вставки последовательности ребер в АТД орграфа, представленного матрицей смежности (второй аргумент конструктора из программы 17.7 имеет значение true), с последующим выполнением поиска в глубину — например, с помощью той же программы 18.3.

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

(рис 19.9) Лес DFS для орграфов

Данный лес описывает стандартный поиск в глубину по спискам смежности орграфа с рис 19.1. Внешние узлы представляют уже посещенные внутренние узлы с теми же метками; во всем остальном этот лес является представлением орграфа, где все ребра направлены вниз. Существуют четыре типа ребер: (1) древесные ребра, ведущие во внутренние узлы; (2) обратные ребра, ведущие во внешние узлы, которые представляют предшественников (серые кружки); (3) нисходящие ребра, ведущие во внешние узлы, которые представляют потомков (серые квадратики); и (4) поперечные ребра, ведущие во внешние узлы, не являющиеся ни предшественниками, ни потомками (светлые квадратики). Тип ребер, ведущих в посещенные узлы, можно определить, сравнивая прямые и обратные номера их начальных и конечных узлов (внизу):

Прямой	Обратный	Пример	Тип ребра
<	>	`4-2`	Нисходящее
>	<	`2-0`	Обратное
>	>	`7-6`	Поперечное

Например, ребро 7-6 является поперечным, поскольку и прямой, и обратный номера узла 7 больше, чем аналогичные номера узла 6 .

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

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

Ребра, представляющие рекурсивный вызов (древесные (tree) ребра).

Ребра, ведущие из вершины к предку в ее дереве DFS (обратные (back) ребра).

Ребра, ведущие из вершины к потомку в ее дереве DFS (нисходящие (down) ребра).

Ребра, ведущие из одной вершины в другую, не являющуюся ни предшественником, ни потомком в ее дереве DFS (поперечные (cross) ребра).

Древесные ребра ведут в непосещенные вершины и соответствуют рекурсивному вызову при поиске в глубину. Обратные, поперечные и нисходящие ребра ведут в посещенные вершины. Чтобы определить тип заданного ребра, мы используем прямую и обратную нумерацию (очередность посещения узлов, соответственно, при прямом и обратном обходе леса).

Лемма 19.3. В лесе DFS, соответствующем орграфу, ребро, которое ведет в посещенную вершину, является обратным ребром, если оно ведет в узел с большим обратным номером; либо поперечным ребром, если оно ведет в узел с меньшим прямым номером; либо нисходящим ребром, если оно ведет в узел с большим прямым номером.

Доказательство. Все эти утверждения следуют непосредственно из определений. Узлы-предки в дереве DFS имеют меньшие прямые номера и большие обратные; узлы-потомки имеют большие прямые номера и меньшие обратные. Верно также и то, что оба эти номера меньше в ранее посещенных узлах других деревьев DFS, и оба эти номера больше в тех узлах, которые предстоит посетить в других деревьях. $$$\blacksquare$$$

Программа 19.2 представляет собой класс DFS, который определяет вид каждого ребра орграфа, а на рис 19.10 приведен пример ее работы для орграфа с рис 19.1. Во время поиска проверка, ведет ли какое-либо ребро в узел с большим обратным номером, эквивалентна проверке, присвоен ли уже обратный номер. Любой узел, которому уже присвоен прямой номер, но еще не присвоен обратный номер, является предком в дереве DFS и поэтому его обратный номер больше обратного номера текущего узла.

(рис 19.10) Трассировка орграфа поиска в глубину

Здесь приведены выходные результаты программы 19.2 для орграфа с рис 19.1. Они в точности соответствуют прямому обходу дерева DFS, показанному на рис 19.9.

Как было сказано в для неориентированных графов, виды ребер зависят скорее от динамики поиска, чем от самого графа. Различные леса DFS для одного и того же графа могут существенно различаться по характеру (см. рис 19.11). Даже количество деревьев леса DFS может зависеть от начальной вершины.

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

(рис 19.11) Лес DFS на орграфе

Эти леса описывают поиск в глубину на том же графе, что и на рис 19.9, где функция поиска на графе проверяет вершины (и вызывает рекурсивную функцию для непосещен-ных вершин) в порядке s, s + 1, ..., V-1, 0, 1, ... , s-1 для каждого s. Структура леса определяется как динамикой поиска, так и структурой самого графа. У каждого узла одни и те же дочерние узлы (узлы в его списке смежности в порядке их следования) в любом лесу. Крайнее левое дерево в каждом лесу содержит все узлы, достижимые из его корня, однако выводы о достижимости из других вершин усложняются из-за наличия обратных, поперечных и нисходящих ребер. Даже количество деревьев в лесе зависит от выбора начальной вершины, поэтому нет прямого соответствия между деревьями в лесе и сильными компонентами, как в неориентированных графах. Например, в данном случае все вершины достижимы из вершины 8 , только если начать поиск из вершины 8.

Программа 19.2. DFS на орграфе

Данный класс DFS использует прямую и обратную нумерацию, чтобы показать роль каждого ребра графа в поиске в глубину (см. рис 19.10).

  template <class Graph>
  class DFS
    { const Graph G;
      int depth, cnt, cntP;
      vector<int> pre, post;
      void show(char *s, Edge e)
        { for (int i = 0; i < depth; i++) 
        cout << " ";
          cout << e.v << "-" << e.w << s << endl;
        }
      void dfsR(Edge e)
        { int w = e.w; show(" древесное", e);
          pre[w] = cnt++; depth++;
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            { Edge x( w, t) ;
              if (pre[t] == -1) dfsR(x);
              else if (post[t] == -1) show(" обратное", x);
              else if (pre[t] > pre[w]) show(" нисходящее", x);
              else show(" поперечное", x);
            }
          post[w] = cntP++; depth--;
        }
    public:
      DFS(const Graph G) : G(G), cnt(0), cntP(0),
        pre(G.V(), -1), post(G.V(), -1)
        { for (int v = 0; v < G.V(); v++)
            if (pre[v] == -1) dfsR(Edge(v, v));
        }
    };

Например, рассмотрим следующую фундаментальную задачу.

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

Лемма 19.4. Орграф является DAG-графом тогда и только тогда, когда проверка всех ребер с помощью поиска в глубину не обнаруживает обратные ребра.

Доказательство. Любое обратное ребро принадлежит некоторому направленному циклу, который состоит из этого ребра и еще пути в дереве, соединяющего концы ребра — поэтому поиск в глубину на DAG не встретит обратных ребер. Чтобы доказать обратное утверждение, мы покажем, что если в орграфе имеется цикл, то поиск в глубину встретит обратное ребро. Допустим, v — первая из вершин цикла, которую посещает DFS. Эта вершина имеет наименьший прямой номер из всех вершин цикла. Поэтому указывающее на нее ребро будет обратным ребром: оно встретится при рекурсивном вызове для вершины v (доказательство этого см. в лемме 19.5), и оно указывает из одного из узлов цикла на v, т.е. на узел с меньшим прямым номером (см. лемму 19.3). $$$\blacksquare$$$

Любой орграф можно преобразовать в DAG, выполнив поиск в глубину и удалив все ребра графа, которые соответствуют обратным ребрам в DFS. Например, из рис. 19.9 рис 19.9 видно, что удаление ребер 2-0, 3-5, 2-3, 9-11, 10-12, 4-2 и 7-8 преобразовывает орграф с рис 19.1 в DAG-граф. Конкретный вид полученного DAG-графа зависит от представления исходного графа и от динамических свойств поиска в глубину (см. упражнение 19.37). Этот метод представляет собой удобный способ генерации больших случайных DAG-графов (см. упражнение 19.76) для тестирования алгоритмов обработки DAG-графов.

Сравнение только что описанного решения с решением, приведенным в для неориентированных графов, дает основание трактовать эти два вида графов как различные комбинаторные объекты, даже если их представления подобны, а некоторые программы работают для обоих видов. Судя по нашим определениям, мы вроде бы используем для решения этой задачи тот же метод, что и для обнаружения циклов в неориентированных графах (поиск обратных ребер), однако наша реализация для неориентированных графов на орграфе работать не будет. Например, в мы внимательно подходили к различиям между родительскими ссылками и обратными ссылками, поскольку существование родительской ссылки не означает наличия цикла (циклы в неориентированных графах должны содержать не меньше трех вершин). Однако нельзя игнорировать обратные ссылки на родительские узлы в орграфах, ведь пары вершин со взаимными ссылками в орграфах считаются циклами. В принципе, можно было бы определить обратные ребра в неориентированных графах так же, как и здесь, однако тогда потребовалось бы явное исключение для случая с двумя вершинами. Хотя более важно то, что в неориентированных графах мы можем обнаруживать циклы за время, пропорциональное V (см. ), однако для обнаружения цикла в орграфе может понадобиться время, пропорциональное E (см. упражнение 19.32).

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

Достижимость из одного истока. До каких вершин заданного орграфа можно добраться из заданной начальной вершины s? Сколько имеется таких вершин?

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

Доказательство. Это доказательство, по сути, повторяет доказательство леммы 18.1, однако мы еще раз подчеркиваем различие между достижимостью в орграфах и связностью в неориентированных графах. Очевидно, что данная лемма справедлива для орграфа, который состоит из одной вершины и не содержит ребер. Для любого орграфа, содержащего более одной вершины, предположим, что эта лемма справедлива для всех орграфов, состоящего из меньшего количества вершин. Первое ребро, которое мы выберем из вершины s, разбивает рассматриваемый орграф на два подграфа, индуцированных двумя подмножествами вершин (см. рис 19.12): (1) вершины, достижимые по ориентированным путям, которые начинаются с этого ребра и далее не содержат s; и (2) вершины, которых невозможно достичь по какому-либо ориентированному пути, начинающемся с этого ребра, без возврата в s. Применим к этим подграфам индуктивное предположение, учитывая, что не существуют ориентированные ребра из каких-либо вершин первого подграфа в вершины второго подграфа, кроме s (наличие такого ребра противоречило бы построению, т.к. его конечная вершина должна находиться в первом подграфе); что направленные ребра, ведущие в s, будут проигнорированы, поскольку прямой номер этой вершины меньше, чем у любой вершины второго подграфа; и что прямые номера всех вершин первого подграфа меньше, чем у вершин второго подграфа. Поэтому все направленные ребра из вершин второго подграфа в первый подграф будут проигнорированы. $$$\blacksquare$$$

(рис 19.12) Декомпозиция орграфа

Доказательство методом индукции того, что поиск в глубину приводит нас во все места орграфа, достижимые из заданного узла, по существу ничем не отличается от доказательства для метода Тремо. Здесь приведен пример в виде лабиринта (вверху), аналогичный рис 18.4. Мы разбиваем граф на две меньшие части (внизу), индуцированные двумя множествами вершин: вершинами, которые могут быть достигнуты, если пройти по первому ребру из начальной вершины без ее дальнейшего посещения (нижняя часть), и вершинами, которые остаются недостижимыми, если пройти по первому ребру и не возвращаться в исходную вершину (верхняя часть). Любое ребро, исходящее из вершины первого множества в исходную вершину, пропускается во время поиска, т.к. исходная вершина уже помечена. Любое ребро, исходящее из вершины второго множества в какую-либо вершину первого множества, пропускается потому, что все вершины первого множества помечены еще до начала поиска во втором подграфе.

В отличие от неориентированных графов, DFS на орграфе не дает полной информации о достижимости из любой вершины, кроме исходной, поскольку ребра дерева являются ориентированными, а поисковые структуры содержат поперечные ребра. Когда мы уходим из какой-либо вершины вниз по дереву, мы не можем быть уверены в том, что существует обратный путь в эту вершину по ребрам орграфа; и в общем случае такого пути действительно нет. Например, после выбора древесного ребра дерева 4-11 уже невозможно вернуться в вершину 4. А при игнорировании поперечных и обратных ребер (поскольку они ведут в уже посещенные вершины) игнорируется и вся связанная с ними информация (множество вершин, достижимых из конечной вершины). Например, проход по ребру 6-9 на рис 19.9 — единственный способ обнаружить, что вершины 10, 11 и 12 достижимы из вершины 6.

Чтобы определить вершины, достижимые из другой вершины, видимо, нужно выполнить новый поиск в глубину из этой вершины (см. рис 19.11). Можно ли воспользоваться информацией из предыдущих поисков, чтобы повысить эффективность этого процесса? Мы рассмотрим подобные вопросы в разделе 19.7.

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

В этой и в предыдущей главах мы видели, что различные способы выбора непосе-щенных вершин приводят к различным динамикам DFS. В случае орграфов структурная сложность деревьев DFS приводит к различиям в динамике поиска, которые еще ярче выражены, чем в неориентированных графах. Например, на рис 19.11 продемонстрированы существенные различия для орграфов даже просто при изменении порядка просмотра вершин высокоуровневыми функциями. На этом рисунке приведена лишь мизерная часть таких возможностей — ведь в принципе каждый из V! различных порядков просмотра вершин может приводить к различным результатам. В разделе 19.7 мы рассмотрим один важный алгоритм, в котором учитывается эта гибкость, и непосе-щенные вершины обрабатываются на верхнем уровне (корни деревьев DFS) в особом порядке, который сразу же выявляет сильные компоненты.

Упражнения

19.30. Начертите лес DFS, который получается при выполнении поиска в глубину на орграфе

3-71-47-80-55-23-82-90-64-92-66-4,представленно мспискамисмежно сти.

19.31. Начертите лес DFS, который получается при выполнении поиска в глубину на орграфе

3-71-47-80-55-23-82-90-64-92-66-4,представленно мматрицейсмежно сти.

19.32. Опишите семейство орграфов с Vвершинами и E ребрами, для которых стандартный поиск в глубину по спискам смежности находит циклы за время, пропорциональное E.

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

19.34. Покажите все возможные леса DFS для орграфа

0-10-20-31-32-3,

и сведите в таблицу количество древесных, обратных, поперечных и нисходящих ребер для каждого леса.

19.35. Если обозначить количества древесных, обратных, поперечных и нисходящих ребер, соответственно, через t, b, с и d, то для любого поиска в глубину на любом орграфе с V вершинами и E ребрами будут верны соотношения t + b + с + t = E и t < V. Какие другие соотношения между этими переменными можно обнаружить? Какие из этих значений зависят только от свойств графов, а какие — от динамических свойств DFS?

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

19.37. Постройте связный DAG-граф, удалив в графе, который изображен на рис 19.1, пять ребер (см. р рис 19.11).

19.38. Реализуйте класс орграфа, который предоставляет клиенту возможность проверять, что заданный орграф на самом деле является DAG-графом, и напишите реализацию на основе DFS.

19.39. Воспользуйтесь решением из упражнения 19.38 для (эмпирической) оценки вероятности того, что случайный орграф с Vвершинами и E ребрами представляет собой DAG, для различных видов орграфов (см. упражнения 19.11—19.18).

19.40. Эмпирически определите относительное процентное содержание древесных, обратных, поперечных и нисходящих ребер при выполнении поиска в глубину на различных видах орграфов (см. упражнения 19.11—19.18).

19.41. Опишите, как построить последовательность ориентированных ребер между V вершинами, для которых при стандартном поиске в глубину на представлении списками смежности не будет ни поперечных, ни нисходящих ребер, а количество обратных ребер пропорционально V².

19.42. Опишите, как построить последовательность ориентированных ребер V вершин, для которых при стандартном поиске в глубину на представлении списками смежности не будет ни обратных, ни нисходящих ребер, а количество поперечных ребер пропорционально V².

19.43. Опишите, как построить последовательность ориентированных ребер V вершин, для которых при стандартном поиске в глубину на представлении списками смежности не будет ни обратных, ни поперечных ребер, а количество нисходящих ребер пропорционально V².

19.44. Приведите правила, соответствующие обходу методом Тремо лабиринта, в котором все коридоры являются односторонними.

19.45. Добавьте в решения, полученные в упражнениях 17.56—17.60, возможность вывода стрелок на ребрах (в качестве примеров используйте рисунки из данной главы).

Достижимость и транзитивное замыкание

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

Определение 19.5. Транзитивное замыкание (transitive closure) орграфа — это орграф с теми же вершинами, но в котором ребро из s в t существует тогда и только тогда, когда существует ориентированный путь из s в t в заданном орграфе.

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

(рис 19.13) Транзитивное замыкание

Исходный орграф (вверху) содержит лишь восемь ориентированных ребер, но его транзитивное замыкание (внизу) показывает, что существуют ориентированные пути, соединяющие 19 из 30 пар вершин. Транзитивное замыкание отражает структурные свойства орграфа. Например, строки 0, 1 и 2 матрицы смежности в транзитивном замыкания идентичны (как и столбцы 0, 1 и 2), поскольку эти вершины содержатся в ориентированном цикле исходного орграфа.

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

Перемножение булевых матриц. Булевой матрицей (Boolean matrix) называется матрица, элементы которой принимают двоичные значения, т.е. 0 или 1. Для заданных булевых матриц A и B можно вычислить произведение C, используя вместо арифметических операций сложения и умножения, соответственно, логические операции И и ИЛИ.

Классический алгоритм вычисления произведения двух матриц размером V х V вычисляет для каждого s и t скалярное произведение строки s первой матрицы и строки t второй матрицы:

  for (s = 0; s < V; s++)
    for (t = 0; t < V; t++)
      for (i = 0, C[s][t] = 0; i < V; i++)
        C[s][t] = A[s][i] * B[i][t];

В матричной системе обозначений такая операция записывается просто как C = A * B. Эта операция определена для матриц, состоящих из любых типов элементов, для которых определены операции 0, + и *. В частности, если a + b интерпретируется как логическая операция ИЛИ, а операция a * b — как логическая операция И, то получается умножение булевых матриц. В языке C++ можно воспользоваться таким вариантом:

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

Чтобы вычислить элемент C[s][t] произведения, вначале мы обнуляем его, а затем присваиваем ему значение 1, если находится значение i, для которого как A[s][i], так и B[i][t] равны 1. Это эквивалентно занесению в C[s][t] значения 1 тогда и только тогда, когда результат побитовой операции И над строкой s матрицы A и столбцом t матрицы B не равен нулю.

Теперь пусть A — матрица смежности орграфа A, и мы используем приведенный выше код для вычисления $$$C = A * A \equiv A^{2}$$$ (только нужно заменить идентификатор B на A). В этом случае для каждой пары вершин s и t матрица C содержит ребро из s в t тогда и только тогда, когда имеется такая вершина i, для которой в A существует как путь из s и i, так и путь из i и t. То есть ориентированные ребра в A² в точности соответствуют ориентированным путям в A длиной 2. Если учитывать петли в каждой вершине A, то A² будет содержать ребра из матрицы A, иначе их там не будет. Эта зависимость между умножением булевых матриц и путями в орграфе продемонстрирована на рис 19.14. Она немедленно приводит к элегантному методу вычисления транзитивного замыкания любого орграфа.

Лемма 19.6. Транзитивное замыкание орграфа можно вычислить, построив матрицу смежности A этого графа, добавив петли для каждой вершины и вычислив A^V. Доказательство. Продолжим рассуждения из предыдущего абзаца: A³ содержит ребра для каждого пути орграфа длиной меньше или равной 3, в матрице A⁴ содержится каждый путь орграфа, длина которого меньше или равна 4, и т.д. Нет необходимости рассматривать пути, длина которых больше V: любой такой путь

хотя бы один раз должен повторно пройти через одну из вершин (поскольку в графе всего V вершин), поэтому он не добавляет какую-то новую информацию в транзитивное замыкание. Ведь оба конца такого пути уже соединены ориентированным путем длиной меньше V (который можно получить, удалив цикл в повторно посещенную вершину). $$$\blacksquare$$$

На рис 19.15 показаны различные степени матрицы смежности для одного и того же орграфа в процессе вычисления транзитивного замыкания. Данный метод выполняет V матричных умножений, каждое из которых выполняется за время, пропорциональное V³, что в конечном итоге составляет V⁴. Но на самом деле транзитивное замыкание для любого орграфа можно вычислить с помощью лишь $$$\lceil lgV\rceil$$$ операций умножения булевых матриц A², A⁴, A⁸, ..., пока показатель степени не станет больше или равен V. Как показано в доказательстве леммы 19.6, A^t = A^V для любого t > V; так что в результате этого вычисления, требующего на свое выполнение времени, пропорционального V³lgV, получится транзитивное замыкание A^V.

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

  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.14) Вычисление квадрата матрицы смежности

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

(рис 19.15) Степени матрицы смежности и ориентированные пути

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

) можно вычислить транзитивное замыкание орграфа за время, пропорциональное V³.

Доказательство. Оценка времени выполнения непосредственно следует из структуры кода. Докажем, что он вычисляет транзитивное замыкание, методом индукции по i. После первого выполнения тела цикла матрица содержит 1 на пересечении строки s и столбца t тогда и только тогда, когда существуют пути s-t или s-0-t. Вторая итерация проверяет все пути между s и t, которые содержат вершину 1 и, возможно, 0 — такие как s-1-t, s-1-0-t и s-0-1-t. Мы приходим к следующему индуктивному предположению: i-я итерация цикла заносит 1 в ячейку матрицы на пересечении строки s и столбца t тогда и только тогда, когда в орграфе существует ориентированный путь из s в t, который не содержит вершин с индексами, большими i (за исключением, возможно, конечных точек s и t). Как только что было доказано, это условие выполняется, когда i равно 0. Если это условие верно для i-ой итерации цикла, то путь из s в t, который не содержит вершин с индексами больше i + 1, существует тогда и только тогда, когда: (1) существует путь из s в t, который не содержит вершин с индексами, большими i — в этом случае в A[s][t] занесено 1 на предыдущей итерации цикла (в соответствии с индуктивным предположением); либо (2) существует путь из s в i+1 и путь из i+1 в t, и ни один из них не содержит вершин с индексами, большими i (за исключением конечных точек) — в этом случае в A[s][i + 1] и A[i+1][t] были ранее записаны 1 (по индуктивному предположению). Следовательно, внутренний цикл заносит 1 в A[s][t].$$$\blacksquare$$$

(рис 19.16) Алгоритм Уоршелла

Здесь показан процесс формирования транзитивного замыкания (внизу) для простого орграфа (вверху) с помощью алгоритма Уоршелла. Первая итерация цикла (левый столбец, вверху) добавляет ребра 1-2 и 1-5, поскольку существуют пути 1-0-2 и 1-0-5, которые содержат вершину 0 (но не содержат вершины с большими номерами). Вторая итерация (левый столбец, вторая сверху) добавляет ребра 2-0 и 2-5, поскольку существуют пути 2-1-0 и 2-1-0-5, которые содержат вершину 1 (но не содержат вершины с большими номерами). Третья итерация (левый столбец, внизу) добавляет ребра 0-1, 3-0, 3-1 и 3-5, поскольку существуют пути 0-2-1, 3-2-1-0, 3-2-1 и 3-2-1-0-5, которые содержат вершину 2 (но не содержат вершины с большими номерами). В правом столбце показаны ребра, добавленные при просмотре путей через вершины 3, 4 и 5. Последняя итерация (правый столбец, внизу) добавляет в вершину 4 ребра из вершин 0, 1 и 2, т.к. все ориентированные пути из этих вершин в вершину 4 содержат 5 — вершину с наибольшим номером.

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

Программа 19.3. Алгоритм Уоршелла

Конструктор класса TC вычисляет транзитивное замыкание графа G в приватном члене данных T, чтобы клиентские программы могли использовать объекты TC для проверки, достижима ли заданная вершина орграфа из любой другой вершины. Конструктор инициализирует T копией графа G, добавляет петли, и затем использует алгоритм Уоршелла. Класс tcGraph должен содержать реализацию проверки существования ребра edge.

  template <class tcGraph, class Graph>
    class TC
      { tcGraph T;
      public:
        TC(const Graph G) : T(G)
        { for (int s = 0; s < T.V(); s++)
          T.insert(Edge(s, s));
          for (int i = 0; i < T.V(); i++)
            for (int s = 0; s < T.V(); s++)
              if (T.edge(s, i))
                for (int t = 0; t < T.V(); t++)
                  if (T.edge(i, t))
                    T.insert(Edge(s, t));
        }
      bool reachable(int s, int t) const
        { return T.edge(s, t); }
      } ;

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

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

Мы будем использовать термин абстрактное транзитивное замыкание (abstract transitive closure) для обозначения АТД, который позволяет клиентам выполнять проверки после предварительной обработки графа, как в программе 19.3. В этом контексте необходимо оценивать алгоритмы не только по затратам на вычисление транзитивного замыкания (стоимость предварительной обработки), но и по объему памяти и времени ответа на запросы. То есть мы предлагаем следующую формулировку леммы 19.7:

Лемма 19.8. Можно обеспечить проверки достижимости в заданном орграфе (абстрактное транзитивное замыкание) за постоянное время, используя на предварительную обработку объем памяти, пропорциональный V², и время, пропорциональное V³.

Доказательство. Эта лемма непосредственно следует из базовых рабочих характеристик алгоритма Уоршелла. $$$\blacksquare$$$

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

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

Сначала мы рассмотрим взаимосвязь между транзитивным замыканием и задачей определения кратчайших путей для всех пар вершин (all-pairs shortest-paths). Для орграфов задача заключается в том, чтобы для каждой пары вершин найти ориентированный путь с минимальным количеством ребер.

Для заданного орграфа мы инициализируем целочисленную матрицу A размером

  V х V: элемент A[s][t] содержит 1, если в орграфе существует ребро из s в t, 
или сигнальное значение V, если такого ребра нет. 
Эту задачу выполняет следующий код:
    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])
            A[s][t] = A[s][i] + A[i][t];

Данный код отличается от алгоритма Уоршелла, приведенного непосредственно перед леммой 19.7, только оператором if во внутреннем цикле. В самом деле, в соответствующей абстрактной форме эти вычисления эквивалентны (см. упражнения 19.55 и 19.56). Несложно преобразовать доказательство леммы 19.7 в прямое доказательство того, что этот метод делает то, что нужно. Данный метод является частным случаем алгоритма Флойда (Floid) поиска кратчайших путей во взвешенных графах (см. ). Решение для ориентированных графов на основе поиска в ширину, рассмотренное в , также может (после соответствующей модификации) отыскивать кратчайшие пути в орграфах. Кратчайшие пути будут рассматриваться в , поэтому мы отложим детальное сравнение рабочих характеристик до этой главы.

Далее. Как мы видели, задача транзитивного замыкания также тесно связана с задачей перемножения булевых матриц. Рассмотренные выше базовые алгоритмы решения обеих задач на основе аналогичной вычислительной схемы требуют времени, пропорционального V³. Умножение булевых матриц является сложной вычислительной задачей: известны алгоритмы, асимптотически более быстрые, чем простые методы, однако получаемая выгода обычно не оправдывает усилий на их реализацию. Этот факт имеет большое значение в данном контексте, поскольку мы могли бы воспользоваться быстрым алгоритмом умножения булевых матриц для разработки быстрого алгоритма транзитивного замыкания (медленнее алгоритма умножения лишь в . И наоборот, можно оценить нижнюю границу сложности вычисления транзитивного замыкания.

Лемма 19.9. Алгоритм транзитивного замыкания можно использовать для вычисления произведения двух булевых матриц с разницей времени вычисления не более чем в постоянное количество раз.

Доказательство. Пусть даны булевы матрицы A и B размером V х V. Построим следующую матрицу размером 3Vх 3V: $$ $$\left(\begin{array}{ccc} I A 0\\ 0 I B\\ 0 0 I \end{array}\right)$$ $$

Здесь 0 означает нулевую матрицу размером V х V, все элементы которой равны 0, а I — единичную матрицу размером V х V, все элементы которой равны 0, за исключением элементов, стоящих на главной диагонали, которые равны 1. Будем рассматривать эту матрицу как матрицу смежности орграфа, и вычислим его транзитивное замыкание повторными возведениями в квадрат. Для этого потребуется лишь одно действие: $$ $$\left(\begin{array}{ccc} I A 0\\ 0 I B\\ 0 0 I \end{array}\right)^{2}=\left(\begin{array}{ccc} I A A*B\\ 0 I B\\ 0 0 I \end{array}\right)$$ $$

Матрица в правой части этого равенства является транзитивным замыканием, поскольку последующие умножения дают эту же матрицу. Однако в верхнем правом углу этой матрицы содержится произведение A * B. Любой алгоритм вычисления транзитивного замыкания можно применить для перемножения булевых матриц с теми же затратами (в пределах постоянного множителя). $$$\blacksquare$$$

Важность этой леммы определяется убежденностью экспертов в сложности задачи умножения булевых матриц: математики десятилетиями пытаются точно оценить ее сложность, но решения пока нет; наилучшие известные результаты говорят, что время выполнения умножения должно быть пропорционально примерно V^2,5(см. раздел ссылок). Но если мы сможем найти линейное по времени решение задачи транзитивного замыкания (т.е. пропорциональное V² ), то мы получим и линейное решение задачи перемножения булевых матриц. Подобная зависимость между задачами называется сведением (reduction): мы говорим, что задача перемножения булевых матриц сводится (reduce) к задаче транзитивного замыкания (см. раздел 21.6 и часть 8). На самом деле приведенное выше доказательство показывает, что умножение булевых матриц сводится к нахождению в орграфе путей длиной 2.

Несмотря на интенсивные исследования многих специалистов, никто не смог найти линейный алгоритм умножения булевых матриц — значит, мы не сможем предложить простого линейного алгоритма транзитивного замыкания. Но ведь и никто не доказал, что такие алгоритмы не существуют, так что возможность появления такого алгоритма не исключается. В общем, лемму 19.9 можно трактовать так: если не будет прорыва в исследованиях, то не следует ожидать, что время выполнения любого алгоритма транзитивного замыкания будет пропорционально V² в худшем случае. Однако возможны быстрые алгоритмы для отдельных классов орграфов. Например, мы уже упоминали простой метод вычисления транзитивного замыкания, который работает для разреженных графов гораздо быстрее алгоритма Уоршелла.

Лемма 19.10. Алгоритм DFS позволяет отвечать за постоянное время на запросы относительно абстрактного транзитивного замыкания орграфа, используя на предварительную обработку (вычисление транзитивного замыкания) объем памяти, пропорциональный V², и время, пропорциональное V(E + V).

Доказательство. Как было сказано в предыдущем разделе, поиск в глубину по представлению списками смежности позволяет найти все вершины, достижимые из исходной, за время, пропорциональное E (лемма 19.5 и рис 19.11). И если выполнить поиск в глубину V раз, считая каждую вершину исходной, то можно вычислить множество вершин, достижимых из каждой вершины, т.е. транзитивное замыкание, за время, пропорциональное и упражнение 19.66). $$$\blacksquare$$$

Программа 19.4 содержит реализацию алгоритма транзитивного замыкания на основе алгоритма поиска. Этот класс реализует тот же интерфейс, что и программа 19.3. Результат работы программы на орграфе с рис 19.1 показан первым деревом каждого леса на рис 19.11.

В случае разреженных орграфов этот подход, основанный на поиске, удобнее всего. Например, если E пропорционально V, то программа 19.4 вычисляет транзитивное замыкание за время, пропорциональное V². Но как она это делает, учитывая сведение к умножению булевых матриц? Ответ таков: данный алгоритм транзитивного замыкания действительно является оптимальным способом умножения определенных типов булевых матриц (с количеством ненулевых элементов O(V)). Нижняя граница показывает, что не стоит надеяться найти алгоритм транзитивного замыкания, который выполняется за время, пропорциональное V², для всех орграфов — однако это не исключает, что можно найти подобные алгоритмы, которые работают быстрее на некоторых классах орграфов.

Программа 19.4. Вычисление транзитивного замыкания на основе поиска в глубину

Данный класс DFS реализует тот же интерфейс, что и программа 19.3. Он вычисляет транзитивное замыкание T, выполняя поиск в глубину для каждой вершины графа G и вычисляя множество узлов, достижимых из этой вершины. Каждый вызов рекурсивной функции добавляет ребро из начальной вершины и выполняет рекурсивные вызовы, чтобы заполнить соответствующую строку в матрице транзитивного замыкания. Эта матрица используется также для пометки посещенных вершин при работе поиска в глубину, поэтому необходимо, чтобы класс Graph поддерживал проверку существования ребер.

  template <class Graph>
  class tc
    { Graph T; const Graph G;
      void tcR(int v, int w)
        { T.insert(Edge(v, w));
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (!T.edge(v, t)) tcR(v, t);
        }
    public:
      tc(const Graph G) : G(G), T(G.V(), true)
        { for (int v = 0; v < G.V(); v++) tcR(v, v); }
      bool reachable(int v, int w)
        { return T.edge(v, w); }
    };

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

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

В таблице 19.1 приведены эмпирические результаты сравнения элементарных алгоритмов транзитивного замыкания, описанных в данном разделе. Реализация решения на основе поиска по представлению списками смежности является наиболее быстрым методом для разреженных графов. Все реализации вычисляют матрицу смежности (размера V² ), поэтому ни одна из них не годится для обработки крупных разреженных графов.

Эмпирическое сравнение алгоритмов транзитивного замыкания
Разреженные (`10V` ребер)					Насыщенные (250 вершин)
V	W	W*	A	L	E	W	W*	A	L
25	0	0	1	0	5000	289	203	177	23
50	3	1	2	1	10000	300	214	184	38
125	35	24	23	4	25000	309	226	200	97
250	275	181	178	13	50000	315	232	218	337
500	2222	1438	1481	54	100000	326	246	235	784

Обозначения:
W	Алгоритм Уоршелла (раздел 19.3)
W*	Усовершенствованный алгоритм Уоршелла (программа 19.3)
A	DFS по матрице смежности (программы 19.4 и 17.7)
L	DFS по спискам смежности (программа 17.9)

В данной таблице приведены значения времени выполнения различных алгоритмов вычисления транзитивного замыкания для случайных орграфов, как насыщенных, так и разреженных. Для всех алгоритмов, кроме DFS по спискам смежности, при удвоении V время выполнения возрастает в 8 раз — это подтверждает, что время пропорционально V³. DFS по спискам смежности требует для своего выполнения время, пропорциональное VE. Поэтому время выполнения этого алгоритма возрастает в примерно в 4 раза при удвоении и V, и E (разреженные графы), и примерно в 2 раза при удвоении E (насыщенные графы) — кроме случаев снижения производительности при обходе сильно насыщенных графов.

В случае разреженных графов, транзитивные замыкания которых тоже разрежены, можно использовать реализацию замыкания списками смежности, поэтому размер ее выходных данных пропорционален количеству ребер в транзитивном замыкании. Конечно, это число служит нижней границей стоимости вычисления транзитивного замыкания, которое можно получить для различных видов орграфов с помощью различных алгоритмических технологий (см. упражнения 19.64 и 19.65). Однако в общем случае мы считаем, что результат транзитивного замыкания является насыщенным. Тогда можно воспользоваться реализацией наподобие DenseGRAPH, которая способна легко отвечать на запросы о достижимости, и мы рассматриваем алгоритмы, которые вычисляют матрицу транзитивного замыкания за время, пропорциональное V², как оптимальные, поскольку время их выполнения пропорционально размеру их выходных данных.

Если матрица смежности симметрична, она эквивалентна неориентированному графу, и тогда поиск транзитивного замыкания эквивалентен поиску связных компонентов: транзитивное замыкание представляет собой объединение полных графов для вершин в связных компонентах (см. упражнение 19.48). Алгоритмы определения связности, представленные в , эквивалентны вычислению абстрактного транзитивного замыкания для симметричных орграфов (неориентированных графов), используют объем памяти, пропорциональный V, и также способны отвечать на запросы о достижимости за постоянное время. Возможно ли такое в случае орграфов общего вида? Для каких видов орграфов можно вычислить транзитивное замыкание за линейное время? Для ответа на эти вопросы нам нужно подробнее ознакомиться со структурой орграфов, и в первую очередь — со структурой DAG-графов.

Упражнения

19.46. Как выглядит транзитивное замыкание орграфа, который состоит лишь из направленного цикла с V вершинами?

19.47. Сколько ребер содержит транзитивное замыкание орграфа, который состоит лишь из простого ориентированного пути с V вершинами?

19.48. Приведите транзитивное замыкание неориентированного графа

3-71-47-80-55-23-82-90-64-92-66-4.

19.49. Покажите, как можно построить орграф с V вершинами и E ребрами, такой, что количество ребер в транзитивном замыкании пропорционально t, для любого t от E до V². Как обычно, предполагается, что E > V.

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

19.51. Представьте в стиле рис 19.15 процесс вычисления транзитивного замыкания орграфа

3-71-47-80-55-23-82-90-64-92-66-4

многократным возведением в квадрат.

19.52. Представьте в стиле рис 19.16 процесс вычисления транзитивного замыкания орграфа

3-71-47-80-55-23-82-90-64-92-66-4 с помощью алгоритма Уоршелла.

19.53. Опишите семейство разреженных орграфов, для которых усовершенствованный вариант алгоритма Уоршелла для вычисления транзитивного замыкания (программа 19.3) выполняется за время, пропорциональное VE.

19.54. Найдите разреженный орграф, для которого усовершенствованный вариант алгоритма Уоршелла для вычисления транзитивного замыкания (программа 19.3) выполняется за время, пропорциональное V³.

19.55. Разработайте базовый класс для порождения производных классов, которые реализуют как алгоритм Уоршелла, так и алгоритм Флойда. (Это упражнение — вариант упражнения 19.56 для тех, кто лучше знаком с абстрактными типами данных, чем с абстрактной алгеброй).

19.56. Воспользуйтесь аппаратом абстрактной алгебры для разработки обобщенного алгоритма, который заключает в себе как алгоритм Уоршелла, так и алгоритм Флойда. (Это упражнение — вариант упражнения 19.55 для тех, кто лучше ознакомлен с абстрактной алгеброй, чем с абстрактными типами данных).

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

19.58. Является ли произведение двух симметричных булевых матриц симметричным? Обоснуйте ваш ответ.

19.59. Добавьте в программы 19.3 и 19.4 общедоступную функцию-член, которая позволит клиентам использовать объекты tc для определения количества ребер в транзитивном замыкании.

19.60. Разработайте способ ведения счетчика количества ребер в транзитивном замыкании, изменяя его при добавлении и удалении ребер. Определите стоимость добавления и удаления ребер в соответствии с вашей схемой.

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

19.62. Эмпирически определите количество ребер в транзитивном замыкании различных видов орграфов (см. упражнения 19.11—19.18).

19.63. Рассмотрите представление графа битовой матрицей, описанное в упражнении 17.23. Какой из методов можно ускорить с его помощью в B раз (где B есть количество битов в слове вашего компьютера) — алгоритм Уоршелла или алгоритм на основе поиска в глубину? Проверьте ответ, разработав соответствующую программную реализацию.

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

19.65. Реализуйте алгоритм абстрактного транзитивного замыкания для разреженных графов, который использует объем памяти, пропорциональный T, и может отвечать на запросы о достижимости за постоянное время после предварительной обработки за время, пропорциональное VE + T, где T — количество ребер в транзитивном замыкании. Указание. Воспользуйтесь динамическим хешированием.

19.66. Напишите версию программы 19.4, которая основана на обобщенном поиске на графе (см. ), и эмпирически определите, влияет ли выбор алгоритма поиска на графе на ее производительность.

Отношения эквивалентности и частичные порядки

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

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

Обычно отношение обозначается символом R, а выражение sRt означает утверждение " упорядоченная пара (s, t) находится в отношении R " . Например, символ " < " используется для представления отношения " меньше чем " . Пользуясь этой терминологией, можно описывать различные свойства отношений. Например, отношение R называется симметричным, если для всех s и t из sRt следует tRs; отношение называется рефлексивным, если для всех s справедливо sRs. Симметричные отношения соответствуют неориентированным графам. Рефлексивные отношения соответствуют графам, в которых в каждой вершине есть петли; отношения, соответствующие графам, в которых ни у одной из вершин нет петель, называются нерефлексивными.

Говорят, что отношение транзитивно, когда из sRt и tRu следует sRu для всех s, t и и. Имеется и определение для транзитивного замыкания (transitive closure) отношения; однако мы не будем давать его определение в контексте теории множеств, а воспользуемся определением для орграфов из раздела 19.3. Любое отношение эквивалентно некоторому орграфу, а транзитивное замыкание отношения эквивалентно соответствующему транзитивному замыканию орграфа. Транзитивное замыкание любого отношения само транзитивно.

В контексте алгоритмов на графах для нас особо важны два специальных транзитивных отношения, которые определяются дополнительными ограничениями. Эти два вида широко распространенных отношений известны как отношения эквивалентности (equivalence relation) и частичные порядки (partial order).

Отношение эквивалентности (=) есть транзитивное отношение, которое к тому же рефлексивно и симметрично. Вообще-то симметричное и транзитивное отношение, которое помещает каждый объект в некоторую упорядоченную пару, должно быть и отношением эквивалентности: если s = t, то t = s (в силу симметричности), откуда s = s (в силу транзитивности). Отношение эквивалентности разбивает объекты множества на подмножества — классы эквивалентности (equivalence class). Два объекта s и t содержатся в одном и том же классе эквивалентности тогда и только тогда, когда s = t. Ниже приведены типичные примеры отношений эквивалентности:

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

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

При создании АТД графа, который позволяет клиентам проверять, находятся ли две вершины в одном и том же связном компоненте, мы реализуем АТД отношения эквивалентности, который предоставляет клиентам возможность проверки эквивалентности двух объектов. На практике это соответствие имеет большое значение, поскольку граф является сжатым представлением отношения эквивалентности (см. упражнение 19.71). Фактически, как мы видели в и 18, для построения такого АТД достаточно использовать единственный вектор, индексированный именами вершин.

Частичный порядок (partial order) $$$\prec $$$ есть транзитивное нерефлексивное отношение. Нетрудно доказать, что из нерефлексивности и транзитивности следует, что частичные порядки асимметричны: если $$$s\prec t$$$ и $$$t\prec s$$$, то $$$s\prec s$$$ (в силу транзитивности), а это противоречит нерефлексивности, т.е. невозможно одновременно $$$s\prec t$$$ и $$$t\prec s$$$. Продолжая эти рассуждения, можно показать, что частичный порядок не может содержать циклы, такие как $$$s\prec t$$$, $$$t\prec u$$$ и $$$u\prec s$$$. Ниже приведены примеры типичных частичных порядков:

Включение подмножеств. Отношение " включает, но не равно " ($$$\subset$$$), определенное для подмножеств заданного множества, является частичным порядком — конечно, он не рефлексивен, и если $$$s\subset t$$$ и $$$t\subset u$$$, то $$$s\subset u$$$.

Пути в DAG-графах. Отношение " достижим по непустому пути из... " является частичным порядком на вершинах DAG-графа без петель, поскольку оно транзитивно и нерефлексивно. Подобно отношениям эквивалентности и неориентированным графам, этот конкретный частичный порядок важен для многих приложений, поскольку DAG — это сжатое неявное представление частичного порядка.

Например, на рис 19.17 приведены DAG-графы частичных порядков включения подмножеств, количество ребер которых составляет лишь небольшую часть мощности частичного порядка (см. упражнение 19.73).

(рис 19.17) DAG-граф включения множеств

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

Вообще-то частичные порядки редко определяются перечислением всех упорядоченных пар, поскольку таких пар очень много. Вместо этого обычно определяется нерефлексивное отношение (DAG) и рассматривается его транзитивное замыкание. Это и есть основная причина изучения реализаций АТД для абстрактных транзитивных замыканий DAG-графов. Работа с DAG-графами и примеры частичных порядков будут рассматриваться в разделе 19.5.

Полный порядок (total order) T — это частичный порядок, в котором для всех s Ф t выполняется либо sTt, либо tTs. Знакомыми нам примерами полного порядка являются отношение " меньше чем " на множествах целых или вещественных чисел или лексикографическое упорядочение строк символов. Наши алгоритмы сортировки и поиска в частях III и IV основываются на реализации АТД полного порядка множеств. В полном порядке существует один и только один способ упорядочить элементы множества так, чтобы выполнялось отношение sTt, если s предшествует t; а в частичном порядке, который не является полным, может быть много способов такого упорядочения. Алгоритмы решения этой задачи будут рассмотрены в разделе 19.5.

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

Отношения и орграфы.

Симметричные отношения и неориентированные графы.

Транзитивные отношения и пути в графах.

Отношения эквивалентности и пути в неориентированных графах.

Частичные порядки и пути в DAG-графах.

Этот список упорядочивает виды изучаемых нами графов и алгоритмов и является дополнительным стимулом изучения базовых свойств DAG-графов и алгоритмов их обработки.

Упражнения

19.67. Покажите, что отношение " имеет тот же остаток при делении на k " транзитивно (и, следовательно, является отношением эквивалентности) на множестве целых чисел.

19.68. Покажите, что отношение " в том же реберно-связном компоненте, что и... " является отношением эквивалентности на множестве вершин любого графа.

19.69. Покажите, что отношение " в том же двусвязном компоненте, что и. " не является отношением эквивалентности на множестве вершин любого графа.

19.70. Докажите, что транзитивное замыкание отношения эквивалентности также является отношением эквивалентности, и что транзитивное замыкание частичного порядка также является частичным порядком.

19.71. Мощность отношения — это количество его упорядоченных пар. Покажите, что мощность отношения эквивалентности равна сумме квадратов мощностей классов эквивалентности этого отношения.

19.72. Используя онлайновый словарь, постройте граф, который представляет отношение эквивалентности " имеет к общих букв с. " на множестве слов. Определите количество классов эквивалентности для к = 1, ..., 5.

19.73. Мощность частичного порядка равна количеству его упорядоченных пар. Какова мощность частичного порядка включения подмножеств для множества из n элементов?

19.74. Покажите, что частичный порядок " является делителем " представляет собой частичный порядок на множестве целых чисел.

DAG -графы

В этом разделе мы рассмотрим различные приложения DAG-графов (directed acyclic graph — ориентированный ациклический граф). На то имеются две причины. Во-первых, они служат неявными моделями частичных порядков, и зачастую в приложениях мы имеем дело непосредственно с DAG-графами — поэтому нужны эффективные алгоритмы обработки таких графов. Во-вторых, такие приложения помогают лучше понять сущность DAG-графов, а понимание DAG-графов важно для понимания орграфов вообще.

Поскольку DAG-графы являются частным видом орграфов, все задачи обработки DAG-графов элементарно сводятся к задачам обработки орграфов. Естественно ожидать, что обрабатывать DAG-графы проще, чем обрабатывать орграфы общего вида, однако понятно, что если мы столкнемся с задачей, которая трудно решается на DAG-графе, то решение этой же задачи на орграфах общего вида вряд ли будет проще. Как мы увидим, задача вычисления транзитивного замыкания принадлежит как раз к этой категории. Оценка сложности обработки DAG-графов также важна, ведь каждый орграф содержит коренной DAG (см. лемму 19.2), т.е. DAG-графы встречаются даже при работе с орграфами, не являющимися DAG-графами.

Классическое приложение, в котором непосредственно возникают DAG-графы, называется составлением расписания (scheduling). В общем случае решение задачи составления расписаний заключается в организации выполнения некоторого множества задач (task) при наличии множества ограничений (constraint) т.е. в указании, когда и как должны выполняться эти задачи. Ограничениями могут быть некоторые функции от времени выполнения или от других ресурсов, потребляемых задачами. Наиболее важный вид ограничений — ограничения предшествования (precedence constraints), которые определяют, что одни задачи должны быть обязательно выполнены перед выполнением других задач, т.е. задают на множестве задач частичный порядок. Различные виды дополнительных ограничений порождают различные виды задач составления расписаний разной степени сложности. Изучены уже буквально тысячи различных задач, и для многих из них исследователи продолжают поиск более совершенных алгоритмов.

Возможно, простейшую нетривиальную задачу составления расписания можно сформулировать следующим образом:

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

В этом базовом виде задача составления расписания называется топологической сортировкой (topological sorting). Ее решение несложно, и в следующем разделе мы рассмотрим два алгоритма. В более сложных практических приложениях могут понадобиться дополнительные ограничения на планирование выполнения задач, и тогда задача усложняется. Например, задачи могут соответствовать курсам лекций в расписании занятий студентов, а частичный порядок может определяться требованиями подготовки к каждому курсу. Топологическая сортировка способна найти расписание занятий, удовлетворяющее требованиям подготовки, но она может не справиться с другими видами ограничений, которые бывает нужно добавить в модель: конфликты курсов, ограничения на количество слушателей курса и т.д. Еще один пример: задачи могут быть частями некоторого производственного процесса, а частичный порядок может задавать цепочки конкретных процессов. Топологическая сортировка позволяет планировать задачи, но, возможно, существует другой способ, требующий меньше времени, денег или других ресурсов, не учтенных в модели. Различные варианты задачи составления расписаний, которые учитывают подобные более общие ситуации, будут рассмотрены в и .

Часто сначала нужно проверить, действительно ли заданный DAG-граф не содержит направленных циклов. Как было показано в 19.2, нетрудно реализовать класс, который позволяет клиентам проверять за линейное время, является ли орграф общего типа DAG-графом — для этого нужно выполнить стандартный поиск в глубину и проверить, что в лесе DFS нет обратных ребер (см. упражнение 19.75). Для реализации алгоритмов обработки DAG-графов мы реализуем специальные клиентские классы нашего стандартного АТД GRAPH, которые предназначены для обработки орграфов без циклов, а проверку отсутствия циклов должны выполнять клиентские программы. При этом возможно, что алгоритм обработки DAG-графов выдаст полезные результаты, даже если запустить его на орграфе с циклами, и иногда это бывает нужно. Разделы 19.6 и 19.7 посвящены реализациям классов топологической сортировки (DAGts) и классов определения достижимости в DAG-графах (DAGts и DAGreach); программа 19.13 представляет собой пример клиента такого класса.

В некотором смысле DAG — это частично дерево и частично граф. Конечно, мы воспользуемся этими особенностями структуры для их обработки. Например, при желании можно рассматривать DAG как дерево. Предположим, что необходимо выполнить обход вершин DAG-графа D, как будто это дерево с корнем в вершине w — чтобы, например, результат обхода двух DAG-графов на рис. 19.18 рис 19.18 с помощью этой программы был одним и тем же. Следующая простая программа выполняет эту задачу так же, как это сделал бы рекурсивный обход дерева:

  void traverseR(Dag D, int v)
    { visit(v);
      typename Dag::adjIterator A(D, v);
      for (int t = A.beg(); !A.end(); t = A.nxt())
        traverseR(D, t);
    }

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

Поскольку DAG-графы обеспечивают компактное представление деревьев, в которых имеются идентичные поддеревья, мы часто используем их вместо деревьев для представления различных вычислительных абстракций. В контексте построения алгоритмов различия между представлением выполнения программы в виде DAG являются существенным компонентом динамического программирования (см., например, рис 19.18 и упражнение 19.78). Кроме того, DAG-графы широко используются в компиляторах в качестве промежуточных представлений арифметических выражений и программ (см., например, рис 19.19) и в системах проектирования электронных схем в качестве промежуточных представлений комбинационных элементов.

(рис 19.18) Модель DAG вычислений чисел Фибоначчи

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

При работе с бинарными деревьями часто возникает важная ситуация. На DAG-графы можно наложить те же ограничения, что и на деревья при определении бинарных деревьев.

Определение 19.6. Бинарный DAG (binary DAG) — это ориентированный ациклический граф с двумя ребрами, исходящими из каждого узла (левое и правое ребро), каждое из которых или оба сразу могут быть пустым

(рис 19.19) Представление арифметического выражение с помощью DAG-графа

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

Различие между бинарными DAG-графами и бинарными деревьями заключается в том, что в бинарном DAG на конкретный узел может указывать более чем одна ссылка. Как и наше определение бинарных деревьев, это определение моделирует естественное представление, где каждый узел представляет собой структуру с левой ссылкой и с правой ссылкой, которые указывают на другие узлы (либо пусты), и действует лишь глобальное ограничение: не разрешены направленные циклы. Бинарные DAG-графы имеют большое значение, поскольку они обеспечивают компактный способ представления бинарных деревьев в некоторых приложениях. Например, как показано на рис 19.20 и в программе 19.5, trie-дерево существования можно сжать до бинарного DAG без изменения реализации поиска.

(рис 19.20) Сжатие бинарного дерева

Таблица из девяти пар целых чисел в левой части рисунка является компактным представлением бинарного DAG (внизу справа), который представляет собой сжатую версию бинарного дерева, показанного вверху. В этой структуре данных метки узлов не хранятся в явном виде: таблица представляет восемнадцать ребер 1-0, 1-0, 2-1, 2-1, 3-1, 3-2 и т.д., однако содержит только конечные вершины левых и правых ребер каждого узла (как в бинарном дереве), а их начальные вершины неявно задаются индексом таблицы.

Алгоритм, который зависит только от формы дерева, эффективно работает и на DAG-графах. Пусть, например, дерево является trie-деревом существования для двоичных ключей, соответствующих листовым узлам, т.е. оно представляет ключи 0000, 0001, 0010, 0110, 1100 и 1101.

Успешный поиск ключа 1101 проходит вправо, вправо, влево и вправо, и завершается в листовом узле. В DAG-графе такой же поиск шел бы от 9 через 8, 7 и 2 в 1.

Эквивалентный вариант — рассматривать ключи trie-дерева как соответствующие строкам в таблице истинности булевской функции, для которых эта функция возвращает истинное значение (см. упражнения 18.84—18.87). Бинарный DAG есть модель экономичной схемы, которая вычисляет эту функцию. В таком приложении бинарные DAG-графы называются деревьями решений (binary decision diagram — BDD).

Программа 19.5. Представление бинарного дерева в виде бинарного DAG-графа

Этот кодовый фрагмент реализует обратный обход, который выполняет построение бинарного DAG, соответствующего структуре бинарного дерева (см. главу 12 ), выявляя общие поддеревья. В нем применяется класс индексирования наподобие ST из программы 17.15 (измененный для работы с парами целых чисел, а не строковых ключей), чтобы присваивать уникальные целочисленные значения каждой отдельной древовидной структуре и применять их в представлении DAG вектором структур из двух целых чисел (см. рис. 19.20 рис 19.20). Пустому дереву (пустая ссылка) присваивается индекс 0 , дереву с единственным узлом (и с двумя пустыми ссылками) — индекс 1 и т.д.

Индекс, соответствующий каждому поддереву, вычисляется рекурсивно. Затем создается ключ — такой, что каждый узел с такими же поддеревьями будет иметь тот же индекс, и этот индекс возвращается после заполнения ссылок ребра (поддерева) DAG-графа.

  int compressR(link h)
    { STx st;
      if (h == NULL) return 0;
      l = compressR(h->l);
      r = compressR(h->r);
      t = st. index(l, r) ;
      adj[t].l = l; adj[t].r = r;
      return t;
    }

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

Упражнения

19.75. Реализуйте класс DFS, который может использоваться клиентами для проверки, что DAG-граф не содержит циклов.

19.76. Напишите программу, которая генерирует случайные DAG-графы: для этого она строит случайные орграфы, выполняет поиск в глубину из случайной исходной точки и отбрасывает обратные ребра (см. упражнение 19.40). Экспериментально определите параметры программы для получения DAG-графов с приблизительно E ребрами при заданном V.

19.77. Сколько узлов содержит дерево и DAG-граф, соответствующие рис 19.18, для вычисления N-го числа Фибоначчи (F_N)?

19.78. Приведите DAG-граф, соответствующий примеру динамического программирования, для модели задачи о ранце из (см. рис 5.17).

19.79. Разработайте АТД для бинарных DAG-графов.

19.80. Можно ли любой DAG представить в виде бинарного DAG (см. лемму 5.4)?

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

19.82. В стиле рис 19.20 нарисуйте trie-дерево существования и соответствующий бинарный DAG для ключей 01001010 10010101 00100001 11101100 01010001 00100001 00000111 01010011.

19.83. Реализуйте АТД, основанный на построении trie-дерева существования из набора 32-битовых ключей, сжатии его до бинарного DAG и использовании этой структуры данных для ответов на запросы о существовании.

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

19.85. Напишите функцию, которая принимает в качестве аргумента 2ⁿ-разрядную таблицу истинности и возвращает соответствующее дерево решений. Например, для аргумента .

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

19.87. Эмпирически определите эффективность стратегии из упражнения 19.85 для различных булевых функций, как стандартных, так и случайно сгенерированных.

19.88. Напишите программу, аналогичную программе 19.5, которая поддерживает удаление общих подвыражений: для заданного бинарного дерева, представляющего арифметическое выражение, нужно вычислить бинарный DAG-граф, представляющий то же выражение, из которого удалены общие подвыражения.

19.89. Начертите все неизоморфные DAG-графы с двумя, тремя, четырьмя и пятью вершинами.

19.90. Сколько существует различных DAG-графов с Vвершинами E ребрами?

19.91. Сколько существует различных DAG-графов с Vвершинами E ребрами, если считать два DAG различными только если они не изоморфны?

Топологическая сортировка

Цель топологической сортировки заключается в обеспечении обработки вершин DAG-графа так, чтобы каждая вершина была обработана до всех вершин, на которые она указывает. Существуют два естественных и, по существу, эквивалентных способа определения этой базовой операции. В любом случае выполняется перестановка целых чисел от 0 до V— 1, которые, как обычно, находятся в векторах, индексированных именами вершин.

Топологическая сортировка (перенумерация). Нужно перенумеровать вершины заданного DAG-графа так, чтобы каждое ориентированное ребро вело из вершины с меньшим номером в вершину с большим номером (см. рис 19.21).

Топологическая сортировка (переупорядочение). Нужно переупорядочить вершины заданного DAG-графа по горизонтали так, чтобы все ориентированные ребра были направлены слева направо (рис 19.22).

(рис 19.21) Топологическая сортировка (перенумерация)

Для заданного произвольного DAG-графа (вверху), топологическая сортировка позволяет переименовать его вершины так, что каждое ребро будет вести из вершины с меньшим номером в вершину с большим номером (внизу). В этом примере номера вершин 4, 5, 7 и 8 заменяются, соответственно, на 7, 8 , 5 и 4, как показано в массиве tsI. Существует много возможных способов перенумерации, позволяющих получить нужный результат.

Легко установить (см. рис 19.22), что перенумерация и переупорядочение перестановок обратны по отношению друг к другу: при наличии переупорядочения перенумерацию можно получить, присвоив номер 0 первой вершине списка, 1 второй вершине списка и т.д. Например, если в векторе ts вершины размещены в порядке топологической сортировки, то цикл

  for (i = 0; i < V; i++) tsI[ts[i]] = i;

определяет перенумерацию в векторе tsI, индексированном именами вершин. И можно получить переупорядочение из перенумерации с помощью цикла

  for (i = 0; i < V; i++) ts[tsI[i]] = i;

который помещает первой в список вершину с номером 0, потом вершину с номером 1 и т.д. Чаще всего мы будем называть топологической сортировкой (topological sort) вариант задачи с переупорядочением. Обратите внимание, что ts не есть вектор, индексированный именами вершин. Обычно порядок вершин, устанавливаемый топологической сортировкой, не уникален. Например,

8 7 0 1 2 3 6 4 9 10 11 12 5

0 1 2 3 8 6 4 9 10 11 12 5 7

0 2 3 8 6 4 7 5 9 10 1 11 12

8 0 7 6 2 3 4 9 5 1 11 12 10

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

Как уже было сказано, иногда полезно рассматривать ребра орграфа по-другому: если ребро направлено из s в t, это означает, что вершина s " зависит " от вершины t. Например, вершины могут представлять определения терминов в некоторой книге — тогда ребро направлено из s в t, если в определении s используется определение t. В этом случае нужно найти упорядочение, при котором определение каждого термина дается перед тем, как оно будет использовано в другом определении. Подобное упорядочение соответствует такому выстраиванию вершин в ряд, что все ребра будут направлены справа налево — это обратная топологическая сортировка (reverse topological sort). На рис 19.23 показана обратная топологическая сортировка на нашем примере DAG.

Но, оказывается, мы уже знакомы с алгоритмом обратной топологической сортировки: это наш старый знакомый — стандартный рекурсивный поиск в глубину! Если входным графом является DAG, то обратная нумерация размещает вершины в обратном топологическом порядке. То есть последним действием рекурсивная функция DFS нумерует каждую вершину так же, как в векторе post в программе 19.2. Как видно из рис 19.24, эта нумерация эквивалентна обратной нумерации узлов в лесе DFS и обеспечивает топологическую сортировку: вектор post, индексированный именами вершин, выполняет перенумерацию, а обратный ему вектор (см. рис 19.23) — обратную топологическую сортировку DAG-графа.

(рис 19.22) Топологическая сортировка (переупорядочение)

Эта диаграмма позволяет по-другому взглянуть на топологическую сортировку, представленную на рис 19.21: в ней определяется способ переупорядочения, а не перенумерации вершин. Если разместить вершины в порядке, указанном в массиве ts, слева направо, то все ориентированные ребра будут направлены вправо. Инверсия перестановки ts есть перестановка tsI, которая определяет перенумерацию, приведенную на рис 19.21.

(рис 19.23) Обратная топологическая сортировка

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

(рис 19.24) Лес DFS для DAG-графа

Лес DFS заданного орграфа не имеет обратных ребер (ребер, ведущих в узлы с большими обратными номерами) тогда и только тогда, когда этот орграф является DAG-графом. Ребра, не принадлежащие деревьям в этом лесе DFS для DAG-графа с рис 19.21 — это либо нисходящие ребра (серые квадратики), либо поперечные ребра (белые квадратики). Последовательность посещения вершин при обратном обходе леса, показанная внизу, представляет собой обратную топологическую сортировку (см. рис 19.23).

Лемма 19.11. Обратная нумерация при поиске в глубину порождает обратную топологическую сортировку для любого DAG-графа.

Доказательство. Предположим, что s и t — две вершины, такие, что s появляется раньше t в обратной нумерации, хотя в графе имеется направленное ребро s-t. Поскольку в момент присвоения номера вершине s для нее уже выполнен рекурсивный DFS, то, в частности, проверено и ребро s-t. Но если бы s-t было древесным, нисходящим или поперечным ребром, рекурсивный DFS для t был бы уже выполнен, и вершина t имела бы меньший номер. Однако s-t не может быть обратным ребром, поскольку это означало бы наличие цикла в графе. Полученное противоречие доказывает невозможность существования ребра s-t. $$$\blacksquare$$$

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

Программа 19.6. Обратная топологическая сортировка

Этот класс DFS вычисляет обратную нумерацию леса DFS (обратная топологическая сортировка). Клиенты могут использовать объект TS для перенумерации вершин DAG-графа, чтобы каждое ребро вело из вершины с большим номером в вершину с меньшим номером, либо переупорядочить вершины так, чтобы начальная вершина каждого ребра появлялась после конечной вершины (см. рис 19.23).

  template <class Dag>
  class dagTS
    { const Dag D;
      int cnt, tcnt;
      vector<int> pre, post, postI;
      void tsR(int v)
        { pre[v] = cnt++;
          typename Dag::adjIterator A(D, v);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (pre[t] == -1) tsR(t);
          post[v] = tcnt; postI[tcnt++] = v;
        }
    public:
      dagTS(const Dag D) : D(D), tcnt(0), cnt(0),
        pre(D.V(), -1), post(D.V(), -1), postI(D.V(), -1)
        { for (int v = 0; v < D.V(); v++)
          if (pre[v] == -1) tsR(v);
        }
      int operator[](int v) const { return postI[v]; }
      int relabel(int v) const { return post[v]; }
    };

С вычислительной точки зрения различие между обычной и обратной топологической сортировкой невелико. Достаточно просто изменить операцию [] так, чтобы она возвращала значение postI[G.V()-1-v], либо изменить реализацию одним из следующих способов:

Выполните обратную топологическую сортировку на обращении заданного DAG-графа.

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

Пронумеруйте вершины в обратном порядке (от V— 1 до 0). При желании вычислите обращение нумерации вершин, чтобы получить топологический порядок.

Доказательство того, что эти изменения позволяют получить правильное топологическое упорядочение, оставляем на самостоятельную проработку (см. упражнение 19.97).

Для реализации первого из перечисленных вариантов для разреженных графов (представленных списками смежности) может потребоваться программа 19.1 для вычисления обратного графа. Это удваивает объем необходимой памяти, что нежелательно в случае крупных графов. Что касается насыщенных графов (представленных матрицей смежности), то, как было сказано в разделе 19.1, можно выполнить поиск в глубину на обратном графе без дополнительной памяти и лишней работы — просто заменив строки на столбцы при обращении к матрице смежности (см. программу 19.7).

Программа 19.7. Топологическая сортировка

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

  void tsR(int v)
    { pre[v] = cnt++;
      for (int w = 0; w < D.V(); w++)
        if (D.edge(w, v))
          if (pre[w] == -1) tsR(w);
      post[v] = tcnt; postI[tcnt++] = v;
    }

А теперь мы рассмотрим альтернативный классический метод топологической сортировки, который больше похож на поиск в ширину (BFS, см. ). Он основан на следующем свойстве DAG-графов.

Лемма 19.12. У каждого DAG-графа имеется по меньшей мере один исток и по меньшей мере один сток.

Доказательство. Предположим, что существует DAG-граф без стоков. Тогда, начав с любой вершины, можно построить ориентированный путь произвольной длины, перейдя из этой вершины вдоль любого ребра в любую другую вершину (существует хотя бы одно такое ребро, поскольку в DAG-графе нет стоков), потом вдоль любого ребра из этой вершины и т.д. Но, в соответствии с принципом картотечного ящика, посетив V + 1 вершину, мы должны попасть в ориентированный цикл (см. лемму 19.6), что противоречит предположению о том, что граф является DAG-графом. Значит, в каждом DAG-графе имеется как минимум один сток. Отсюда также следует, что в каждом DAG-графе имеется как минимум один исток: это просто обращение стока. $$$\blacksquare$$$

Из этого факта можно вывести алгоритм топологической сортировки: пометим любой исток наименьшей неиспользованной меткой, затем удалим его и пометим остальную часть DAG-графа, используя тот же алгоритм. На рис. 19.25 рис 19.25 показана трасса работы этого алгоритма на нашем демонстрационном DAG-графе.

Эффективная реализация этого алгоритма — классическое упражнение по проектированию структур данных (см. раздел ссылок). Во-первых, истоков может быть несколько, и понадобится очередь для их хранения (подойдет любая обобщенная очередь). Во-вторых, необходимо находить истоки в DAG-графе после удаления какого-либо истока. Эту задачу можно выполнить с помощью вектора, индексированного именами вершин, в котором учитываются степени захода каждой вершины. Вершины со степенью захода 0 являются истоками, поэтому можно инициализировать очередь одним просмотром DAG-графа (используя поиск в глубину или любой другой метод, который просматривает все ребра). Затем, пока очередь истоков не опустеет, мы выполняем следующие операции:

Удаляем исток из очереди и присваиваем ему номер.

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

Если при уменьшении значения какой-либо элемент становится равным 0, заносим соответствующую вершину в очередь истоков.

Программа 19.8 содержит реализацию этого метода, в которой применяется очередь FIFO, а на рис 19.26 показан пример ее работы на нашем демонстрационном DAG-графе, который раскрывает дополнительные подробности динамики примера на рис 19.25.

(рис 19.25) Топологическая сортировка DAG-графа методом удаления истоков

Вершина 0 является истоком (на нее не указывает ни одно ребро) и поэтому может оказаться первой при топологической сортировке этого графа (слева вверху). Если удалить вершину 0 (и все ребра из нее в другие вершины), то истоками в полученном DAG-графе станут вершины 1 и 2 (слева, вторая диаграмма сверху), и этот граф можно сортировать при помощи того же алгоритма. На данном рисунке показано действие программы 19.8, которая выбирает один из истоков (серые узлы на каждой диаграмме), используя дисциплину FIFO, хотя на каждом шаге может быть выбран любой из источников. На рис 19.26 представлено содержимое структур данных, управляющих выбором действий алгоритма. Результатом топологической сортировки, показанной на этом рисунке, является следующий порядок узлов: 0 8 2 1 7 3 6 5 4 9 11 10 12.

Программа 19.8. Топологическая сортировка с очередью истоков

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

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

    #include "QUEUE.cc"
    template <class Dag>
    class dagTS
      { const Dag D;
        vector<int> in, ts, tsI;
      public:
        dagTS(const Dag D) : D(D), in(D.V(), 0), ts(D.V(), -1), tsI(D.V(), -1)
        { QUEUE<int> Q;
          for (int v = 0; v < D.V(); v++)
            { typename Dag::adjIterator A(D, v);
              for (int t = A.beg(); !A.end(); t = A.nxt())
                in[t]+ + ;
            }
          for (int v = 0; v < D.V(); v++)
            if (in[v] == 0) Q.put(v);
          for (int j = 0; !Q.empty(); j++)
            { ts[j] = Q.get(); tsI[ts[j]] = j;
              typename Dag::adjIterator A(D, ts[j]);
              for (int t = A.beg(); !A.end(); t = A.nxt())
                if (—in[t] == 0) Q.put(t);
            }
        }
        int operator[](int v) const { return ts[v]; }
        int relabel(int v) const { return tsI[v]; }
      };

(рис 19.26) Таблица степеней захода и содержимое очереди

Здесь показаны содержимое таблицы степеней захода (слева) и очередь истоков (справа) во время выполнения программы 19.8 на DAG-графе, соответствующем рис 19.25. В любой заданный момент времени очередь истоков содержит узлы с нулевыми степенями захода. Просматривая сверху вниз, мы извлекаем из очереди истоков самый левый узел, уменьшаем на единицу степени захода элементов, соответствующих каждому ребру, исходящему из этого узла, и заносим в очередь истоков все вершины, элементы которых стали равными 0. Например, вторая строка таблицы отражает результат удаления вершины 0 из очереди истоков, с последующим (поскольку DAG содержит ребра 0-1, 0-2, 0-3, 0-5 и 0-6) уменьшением на единицу элементов, соответствующих вершинам 1, 2, 3, 5 и 6, и занесением вершин 2 и 1 в очередь истоков (поскольку значения их степеней захода стали равными 0). Считывание самых левых элементов в очереди истоков сверху вниз дает топологическое упорядочение рассматриваемого графа.

Очередь истоков не опустеет, пока не будут помечены все вершины DAG-графа, т.к. подграф, индуцированный еще не помеченными вершинами, всегда является DAG-графом, а у каждого DAG-графа имеется хотя бы один исток. Вообще-то этот алгоритм можно использовать для проверки, является ли заданный граф DAG-графом: ведь если очередь опустеет до того, как все вершины будут помечены, то в подграфе, индуцированном еще непомеченными вершинами, должен существовать цикл (см. упражнение 19.104).

Обработка вершин в порядке, заданном топологической сортировкой, лежит в основе обработки DAG-графов. Классическим примером может служить задача вычисления длины самого длинного пути в DAG-графе. Рассматривая вершины в обратном топологическом порядке, легко вычислить самый длинный путь, начинающийся в каждой вершине v. Для этого нужно добавить единицу к максимальной из длин самых длинных путей, которые начинаются в каждой из вершин, достижимых из v через одно ребро. Благодаря топологической сортировке все такие длины известны во время обработки вершины v, поэтому никакие другие пути из v после этого выявлены не будут.

Например, просматривая слева направо обратную топологическую сортировку, показанную на рис 19.23, можно быстро вычислить следующую таблицу длин максимальных путей, начинающихся в каждой вершине демонстрационного графа с рис 19.21: 5 12 11 10 9 4 6 3 2 1 0 7 8 0 0 1 0 2 3 4 4 5 0 6 5 6

Например, значение 6, соответствующее 0 (третий столбец справа), означает, что существует путь длиной 6, начинающийся в 0. Ведь существует ребро 0-2, а ранее мы определили, что длина самого длинного пути из вершины 2 равна 5, и что ни одно из ребер, исходящих из 0, не ведет в узел, имеющий более длинный путь.

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

Использование класса DAGts в АТД DAG с последующей обработкой вершин в очередности, задаваемой вычисленным вектором.

Обработка вершин после рекурсивных вызовов при выполнении поиска в глубину.

Обработка вершин при извлечении их из очереди в процессе топологической сортировки на основе очереди истоков.

Все эти методы используются в реализациях, выполняющих обработку DAG — важно только знать, что все они эквивалентны. Другие приложения топологической сортировки будут рассмотрены в упражнениях 19.111 и 19.114 и в разделах 19.7 и 21.4.

Упражнения

19.92. Напишите функцию, которая проверяет, является ли заданная перестановка вершин DAG-графа верной топологической сортировкой этого графа.

19.93. Сколько возможно различных топологических сортировок для DAG-графа, изображенного на рис 19.6?

19.94. Приведите лес DFS и обратную топологическую сортировку, которые получаются в результате выполнения стандартного поиска в глубину по спискам смежности (с обратной нумерацией) следующего DAG-графа:

3-71-47-80-55-23-82-90-64-92-66-44-32-3.

19.95. Приведите лес DFS и обратную топологическую сортировку, которые получаются при построении стандартного представления списками смежности для DAG-графа

3-71-47-80-55-23-82-90-64-92-66-44-32-3

с последующим обращением с помощью программы 19.1 и выполнением поиска в глубину по спискам смежности с обратной нумерацией.

19.96. В программе 19.6 для выполнения обратной топологической сортировки используется обратная нумерация. Почему нельзя воспользоваться прямой нумерацией? Обоснуйте свой ответ на примере графа с тремя вершинами.

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

19.98. Приведите лес DFS и топологическую сортировку, которые получаются в результате выполнения стандартного поиска в глубину с неявным обращением на представлении списками смежности (и обратной нумерацией) для следующего DAG-графа:

3-71-47-80-55-23-82-90-64-92-66-44-32-3(см.про грамму19.7).

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

19.100. Покажите в стиле рис 19.26 процесс топологической сортировки DAG-графа

3-71-47-80-55-23-82-90-64-92-66-44-32-3 с помощью алгоритма, использующего очередь истоков (программа 19.8).

19.101. Приведите топологическую сортировку, которая получится, если в примере, представленном на рис 19.25, в качестве структуры данных использовать стек, а не очередь.

19.102. Пусть задан некоторый DAG-граф. Существует ли топологическая сортировка, которую нельзя получить алгоритмом на основе поиска в глубину, независимо от дисциплины, реализуемой очередью? Обоснуйте свой ответ.

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

19.104. Воспользуйтесь программой 19.8 для реализации класса, проверяющего отсутствие циклов в заданном DAG-графе (см. упражнение 19.75).

19.105. Преобразуйте алгоритм топологической сортировки с очередью истоков в алгоритм с очередью стоков для выполнения обратной топологической сортировки.

19.106. Напишите программу, которая генерирует все возможные топологические упорядочения заданного DAG-графа, либо, если количество таких упорядочений превышает границу, заданную в качестве аргумента, просто выводит это число.

19.107. Напишите программу, которая преобразует любой орграф с V вершинами и E ребрами в DAG-граф, выполнив топологическую сортировку на основе DFS и изменяя направление каждого встреченного обратного ребра. Докажите, что эта стратегия всегда приводит к созданию DAG-графа.

19.108. Напишите программу, которая генерирует с равной вероятностью один из возможных DAG-графов с V вершинами и E ребрами (см. упражнение 17.70).

19.109. Сформулируйте необходимые и достаточные условия существования для конкретного DAG-графа только одного возможного топологического упорядочения его вершин.

19.110. Эмпирически сравните алгоритмы топологической сортировки, приведенные в этом разделе, для различных DAG-графов (см. упражнения 19.2, 19.76, 19.107 и 19.108). Протестируйте свою программу, как описано в упражнении 19.11 (для разреженных графов) и в упражнении 19.12 (для насыщенных графов).

19.111. Измените программу 19.8 так, чтобы она могла вычислять количество различных простых путей из любого истока в каждую вершину DAG-графа.

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

19.113. Опишите семейство арифметических выражений, таких, что размер дерева выражения экспоненциально больше, чем размер соответствующего DAG-графа (и поэтому время выполнения программы из упражнения 19.112 для этого DAG пропорционально логарифму времени выполнения для дерева).

19.114. Разработайте метод поиска простого ориентированного пути максимальной длины в DAG-графе за время, пропорциональное V. Используйте этот метод для реализации класса, выполняющего вывод гамильтонова пути в заданном DAG-графе, если он существует.

Достижимость в DAG-графах

В завершение нашего изучения DAG-графов мы рассмотрим задачу вычисления транзитивного замыкания DAG-графа. Можно ли разработать алгоритмы для DAG-графов, более эффективные, чем алгоритмы для обобщенных орграфов, которые были рассмотрены в разделе 19.3?

Любой метод топологической сортировки может служить основой алгоритмов транзитивного замыкания DAG: мы просматриваем вершины в обратном топологическом порядке, вычисляя при этом вектор достижимости для каждой вершины (то есть строку матрицы транзитивного замыкания) из строк, соответствующих смежным с ней вершинам. Обратная топологическая сортировка гарантирует, что все эти строки уже вычислены тогда, когда они нужны. Мы проверяем каждый из V элементов вектора, соответствующих конечным вершинам каждого из E ребер, на что в общем нужно время, пропорциональное VE. Этот метод легко реализовать, но он обрабатывает DAG-графы ничуть не эффективнее, чем орграфы общего вида.

При использовании стандартного поиска в глубину для топологической сортировки (см. программу 19.7) можно повысить ее производительность для некоторых видов DAG-графов, как показано в программе 19.9. Поскольку в DAG-графах не может быть циклов, то при поиске в глубину не может быть обратных ребер. Однако важнее то, что как поперечные, так и нисходящие ребра ведут в узлы, в которых DFS уже завершен. Чтобы воспользоваться этим, мы разработаем рекурсивную функцию, которая вычисляет все вершины, достижимые из заданной исходной вершины, но (как обычно при поиске в глубину) без рекурсивных вызовов для вершин, для которых уже вычислено множество достижимых вершин. В этом случае достижимые вершины представлены одной из строк транзитивного замыкания, а рекурсивная функция выполняет операцию логического ИЛИ над всеми строками, соответствующими смежным вершинам. В случае древесных ребер выполняется рекурсивный вызов для вычисления этой строки; в случае поперечных ребер можно пропустить рекурсивный вызов, т.к. мы знаем, что эта строка уже была вычислена в результате предыдущего рекурсивного вызова; в случае нисходящих ребер можно пропустить все вычисление, поскольку любые достижимые узлы, которые могут быть при этом добавлены, уже учтены в множестве достижимых узлов для конечной вершины (ниже и раньше в дереве DFS).

(рис 19.27) Транзитивное замыкание DAG-графа

Данная последовательность векторов-строк представляет транзитивное замыкание DAG-графа с рис 19.21. Эти строки вычислены в обратном топологическом порядке последним действием рекурсивной функции DFS (см. программу 19.9). Каждая строка является результатом логической операции ИЛИ над строками для смежных вершин, которые находятся раньше в списке. Например, чтобы вычислить строку для вершины 0, мы выполняем логическую ИЛИ над строками для вершин 5, 2, 1 и 6 (и заносим значение 1, соответствующее самой вершине 0), т.к.ребра 0-5, 0-2, 0-1 и 0-6 приводят нас из вершины 0 в вершины, достижимые из каждой из этих вершин. Нисходящие ребра можно игнорировать, поскольку они не добавляют новой информации. Например, мы игнорируем ребро, ведущее из 0 в 3, потому что вершины, достижимые из 3, уже учтены в строке, соответствующей вершине 2.

Использование этого варианта поиска в глубину можно считать применением динамического программирования для вычисления транзитивного замыкания, т.к. мы используем уже вычисленные (и сохраненные в строках матрицы смежности, которые соответствуют ранее обработанным вершинам) результаты, чтобы не выполнять ненужных рекурсивных вызовов. На рис 19.27 показано вычисление транзитивного замыкания DAG-графа с рис 19.6.

Лемма 19.13. С помощью динамического программирования и поиска в глубину можно обеспечить постоянное время ответа на запросы относительно абстрактного транзитивного замыкания DAG-графа, затратив на предварительную обработку (вычисление транзитивного замыкания) объем памяти, пропорциональный V², и время, пропорциональное V² + VX, где X —количество поперечных ребер в лесе DFS.

Доказательство. Доказательство непосредственно следует по индукции из рекурсивной функции, приведенной в программе 19.9. Мы посещаем вершины в обратном топологическом порядке. Каждое ребро указывает на вершину, для которой уже вычислено множество всех достижимых вершин — поэтому мы можем вычислить множество достижимых вершин для любой вершины путем слияния множеств достижимых вершин, связанных с конечными вершинами каждого ребра. Завершает это слияние логическое ИЛИ над указанными строками матрицы смежности. Мы обращаемся к строке размером V каждого древесного ребра и каждого поперечного ребра. В рассматриваемом случае обратные ребра отсутствуют, а нисходящие ребра можно игнорировать, поскольку все вершины, в которые они приводят, уже учтены ранее — при обработке предшественников обеих вершин этих ребер. $$$\blacksquare$$$

Программа 19.9. Транзитивное замыкание DAG-графа

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

  template <class tcDag, class Dag>
  class dagTC
    { tcDag T; const Dag D;
      int cnt;
      vector<int> pre;
      void tcR(int w)
        { pre[w] = cnt++;
          typename Dag::adjIterator A(D, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            { T.insert(Edge(w, t));
              if (pre[t] > pre[w]) continue;
              if (pre[t] == -1) tcR(t);
              for (int i = 0; i < T.V(); i++)
                if (T.edge(t, i)) T.insert(Edge(w, i));
            }
        }
    public:
      dagTC(const Dag D) : D(D), cnt(0),
        pre(D.V(), -1), T(D.V(), true)
        { for (int v = 0; v < D.V(); v++)
          if (pre[v] == -1) tcR(v);
        }
      bool reachable(int v, int w) const
        { return T.edge(v, w); }
    } ;

Если в DAG-графе нет нисходящих ребер (см. упражнение 19.42), время выполнения программы 19.9 пропорционально VE — т.е. она ничем не лучше алгоритмов транзитивного замыкания для орграфов общего вида из раздела 19.3 (см., например, программу 19.4) или подхода на основе топологической сортировки, которая описана в начале данного раздела. Однако при большом количестве нисходящих ребер (или, что одно и то же, при малом количестве поперечных ребер) программа 19.9 работает значительно быстрее этих методов.

Задача поиска оптимального алгоритма (гарантирующего выполнение за время, пропорциональное V² ) вычисления транзитивного замыкания для насыщенных DAG-графов все еще не решена. Лучшая известная граница производительности для худшего случая равна VE. Но, конечно, лучше использовать алгоритм, который работает быстрее для большого класса DAG-графов — например, программу 19.9 — чем алгоритм, который, как программа 19.4, всегда выполняется за время, пропорциональное VE. В разделе 19.9 мы убедимся, что такое повышение производительности для DAG-графов оказывает непосредственное влияние и на нашу способность вычислять транзитивные замыкания орграфов общего вида.

Упражнения

19.115. Покажите в стиле рис 19.27 векторы достижимости, если для вычисления транзитивного замыкания DAG-графа

3-71-47-80-55-23-82-90-64-92-66-44-32-3

использовать программу 19.9.

19.116. Разработайте такую версию программы 19.9, которая использует представление транзитивного замыкания без поддержки функции проверки edge и которая выполняется за время, пропорциональное $$$V^{2}+\sum \limits_{e} v(e)$$$, где суммирование проводится по всем ребрам DAG-графа, а v(e) — количество вершин, достижимых из конечной вершины ребра е. Для некоторых видов разреженных DAG-графов такие затраты существенно меньше, чем VE (см. упражнение 19.65).

19.117. Реализуйте класс абстрактного транзитивного замыкания для DAG-графов, который использует дополнительный объем памяти, не более чем пропорциональный V (и пригодный для работы с крупными DAG-графами). Воспользуйтесь топологической сортировкой для получения быстрого ответа, если вершины не связаны, а также реализацией очереди истоков, чтобы возвращать длину пути, когда вершины связаны.

19.118. Разработайте реализацию транзитивного замыкания на основе обратной топологической сортировки с очередью стоков (см. упражнение 19.105).

19.119. Требует ли ваше решение задачи 19.118 просмотра всех ребер DAG-графа или игнорирует некоторые ребра — например, нисходящие ребра в DFS? Приведите пример, когда необходим просмотр всех ребер, или опишите ребра, которые можно пропустить.

Сильные компоненты в орграфах

Неориентированные графы и DAG-графы — более простые структуры данных, чем орграфы общего вида, в силу структурной симметрии, которая характеризует отношения достижимости среди вершин: из того, что в неориентированном графе существует путь из s в t, следует, что существует путь из t в s; если в DAG-графе существует путь из s в t, то мы знаем, что путь из t в s не существует. В случае орграфов общего вида тот факт, что вершина t достижима из s, не несет никакой информации о достижимости s из t.

Чтобы понять структуру орграфов, мы рассмотрим сильную связность (strong connectivity), обладающую интересующей нас симметрией. Если s и t являются сильно связанными вершинами (каждая из них достижима из другой), то, по определению, таковыми являются и t и s. Как было сказано в разделе 19.1, из такой симметрии следует, что вершины орграфа разбиваются на классы сильных компонентов, состоящие из взаимно достижимых вершин. В этом разделе мы рассмотрим три алгоритма поиска сильных компонентов в орграфах.

Мы будем использовать тот же интерфейс, что и для задачи связности в алгоритмах поиска на неориентированных графах общего вида (см. программу 18.4). Назначение наших алгоритмов в том, чтобы присвоить номера компонентов каждой вершине в векторе, индексированном именами вершин, используя для обозначения сильных компонентов числа 0, 1, ... . Наибольший из присваиваемых номеров равен числу, на единицу меньшему количества сильных компонентов. Эти номера компонентов можно использовать для проверки за постоянное время, входят ли две заданные вершины в один и тот же сильный компонент.

Нетрудно разработать примитивный алгоритм решения этой задачи. С помощью АТД абстрактного транзитивного замыкания проанализируем каждую пару вершин s и t: достижима ли t из s и достижима ли s из t. Затем определим неориентированный граф с ребрами для каждой такой пары: связные компоненты этого графа соответствуют сильным компонентам орграфа. Этот алгоритм нетрудно описать и реализовать, а время его выполнения определяется в основном реализацией абстрактно-транзитивного замыкания, как сказано, скажем, в лемме 19.10.

Алгоритмы, которые мы рассмотрим в данном разделе — воплощение последних достижений в области построения алгоритмов. Они могут найти сильные компоненты любого графа за линейное время, т.е. в Vраз быстрее примитивного алгоритма. Для графов, содержащих 100 вершин, эти алгоритмы работают в 100 раз быстрее примитивного алгоритма, а для 1000 вершин — в 1000 раз быстрее, и мы можем решать подобные задачи для графов с миллионами вершин. Эта задача является характерным примером хорошего проектирования алгоритма, и мощным стимулом пристального изучения алгоритмов на графах. Где еще можно сэкономить используемые ресурсы в миллион и более раз за счет выбора элегантного алгоритма решения практически важной задачи?

История этой задачи достаточно поучительна (см. раздел ссылок). В пятидесятые и шестидесятые годы математики и специалисты по вычислительной технике приступили к серьезному изучению алгоритмов на графах. В это время как раз развивался сам анализ алгоритмов как область исследований. Во время бурного развития компьютерных систем, языков и формирования понятия эффективных вычислений приходилось рассматривать разнообразные алгоритмы обработки графов, однако многие такие задачи оставались нерешенными. Постепенно компьютерные специалисты стали постигать многие базовые принципы анализа алгоритмов и стали понимать, какие задачи на графах могут быть решены эффективно, а для каких задач это невозможно, и начали разрабатывать все более эффективные алгоритмы решения для первого набора задач. Р. Тарьян (R. Tarjan) предложил линейные по времени алгоритмы решения задачи сильной связности и других задач на графах в 1972 году, и в этом же году Р Карп (R. Karp) доказал невозможность эффективного решения задачи коммивояжера и многих других задач на графах. Долгое время с алгоритма Тарьяна начинались многие продвинутые курсы по анализу алгоритмов, поскольку он решает важную практическую задачу, используя простые структуры данных. В 1980-х годах Р Косарайю (R. Kosaraju) рассмотрел эту задачу с другой стороны и разработал новое решение; позднее оказалось, что статья с описанием этого же метода была опубликована в советской научной литературе намного раньше — в 1972 г. Позже, в 1999 г., Г. Габову (H. Gabov) удалось получить простую реализацию одного из первых подходов, предложенных в шестидесятых годах, то есть третий линейный по времени алгоритм для этой задачи.

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

Метод Косарайю прост для понимания и реализации. Чтобы найти сильные компоненты графа, сначала выполняется поиск в глубину на его обращении, который вычисляет перестановку вершин, определенных обратной нумерацией. (Такой процесс представляет собой топологическую сортировку, если орграф является DAG-графом.) Затем выполняется еще один DFS на этом графе, но чтобы найти следующую вершину для поиска (при вызове рекурсивной функции поиска — в самом начале и при каждом возврате управления рекурсивной функцией в функцию поиска более высокого уровня), берется непосещенная вершина с максимальным обратным номером.

Фокус в этом алгоритме заключается в том, что при такой проверке непосещенных вершин в соответствии с топологической сортировкой деревья в лесе DFS определяют сильные компоненты — так же, как деревья в лесе DFS определяют связные компоненты в неориентированных графах: две вершины принадлежат одному и тому же сильному компоненту тогда и только тогда, когда они принадлежат одному и тому же дереву в этом лесе. На рис 19.28 демонстрируется этот факт для нашего примера, а доказательство будет приведено чуть ниже. Поэтому можно пронумеровать компоненты, как в случае неориентированных графов, увеличивая номер компонента на единицу при каждом возврате рекурсивной функции на более высокий уровень. В программе 19.10 приведена полная реализация этого метода.

(рис 19.28) Вычисление сильных компонентов (алгоритм Косарайю)

Чтобы вычислить сильные компоненты орграфа, изображенного внизу слева, мы сначала выполняем поиск в глубину на его обращении (вверху слева), вычисляя вектор обратных номеров, который присваивает вершинам индексы в порядке завершения рекурсивных DFS (вверху). Этот порядок эквивалентен обратному обходу леса DFS (вверху справа). Затем с помощью обращения этого порядка выполняется поиск в глубину на исходном графе (внизу). Сначала мы проверяем все узлы, доступные из вершины 9, затем просматриваем вектор справа налево и находим, что самая правая непосещенная вершина — это 1, поэтому мы выполняем рекурсивный вызов для вершины 1 и т.д. Деревья в лесе DFS, полученные в результате этого процесса, определяют сильные компоненты: все вершины каждого дерева имеют одинаковые значения в векторе id, индексированном именами вершин (внизу).

Программа 19.10. Сильные компоненты (алгоритм Косарайю)

Клиенты могут использовать объекты этого класса для определения количества сильных компонентов орграфа (count) и проверок на сильную связность (stronglyreachable). Конструктор SC сначала создает обратный орграф и вычисляет с помощью DFS обратную нумерацию. Далее он выполняет поиск в глубину на исходном орграфе, используя обращение обратного порядка из первого поиска в глубину в цикле поиска, в котором выполняются вызовы рекурсивной функции. Каждый рекурсивный вызов во втором DFS посещает все вершины сильного компонента.

  template <class Graph>
  class SC
    { const Graph G;
      int cnt, scnt;
      vector<int> postI, postR, id;
      void dfsR(const Graph G, int w)
        { id[w] = scnt;
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (id[t] == -1) dfsR(G, t);
          postI[cnt++] = w;
        }
    public:
      SC(const Graph G) : G(G), cnt(0), scnt(0),
        postI(G.V()), postR(G.V()), id(G.V(), -1)
        { Graph R(G.V(), true);
          reverse(G, R);
          for (int v = 0; v < R.V(); v++)
            if (id[v] == -1) dfsR(R, v);
          postR = postI; cnt = scnt = 0;
          id.assign(G.V(), -1);
          for (int v = G.V()-1; v >= 0; v--)
            if (id[postR[v]] == -1)
              { dfsR(G, postR[v]); scnt++; }
        }
      int count() const { return scnt; }
      bool stronglyreachable(int v, int w) const
        { return id[v] == id[w]; }
    };

Лемма 19.14. Метод Косарайю находит сильные компоненты графа с линейными затратами времени и памяти.

Доказательство. Этот метод состоит из двух процедур DFS с небольшими изменениями, поэтому время его выполнения, как обычно, пропорционально V² для насыщенных графов и V + E для разреженных графов (в случае представления списками смежности). Чтобы доказать, что он правильно вычисляет сильные компоненты, необходимо доказать, что во втором поиске две вершины s и t находятся в одном и том же дереве леса DFS тогда и только тогда, когда они взаимно достижимы.

Если вершины s и t взаимно достижимы, они обязательно находятся в одном и том же дереве DFS: когда первая из них посещена, вторая еще не посещена и достижима из первой. Поэтому она будет просмотрена до завершения рекурсивного вызова из корня.

Чтобы доказать обратное утверждение, предположим, что s и t находятся в одном и том же дереве, и пусть r — корень этого дерева. Из достижимости s из r (через ориентированный путь, состоящий из древесных ребер) следует, что в обратном орграфе существует ориентированный путь из s в r. В обратном орграфе должен существовать и путь из r в s, поскольку r имеет больший обратный номер, чем s (т.к. при втором поиске в глубину r была выбрана первой, когда обе вершины еще не были посещены), и существует путь из s в r. Ведь если бы пути из s в r не было, то путь из s в r в обратном орграфе оставил бы вершине s больший обратный номер. Итак, существуют ориентированные пути из s в r и из r в s — как в орграфе, так и в его обращении — то есть s и r сильно связаны. Аналогичные рассуждения доказывают, что t и r сильно связаны, и поэтому s и t также сильно связаны. $$$\blacksquare$$$

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

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

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

Алгоритм Тарьяна похож на программу из для поиска мостов в неориентированных графах (см. программу 18.7). Этот метод основан на двух наблюдениях, которые были сделаны в других контекстах. Во-первых, мы рассматриваем вершины в обратном топологическом порядке, чтобы в конце работы рекурсивной функции для вершины мы знали, что не встретим ни одной вершины из того же сильного компонента (потому что все вершины, достижимые из этой, уже обработаны). Во-вторых, обратные ссылки в дереве обеспечивают второй путь из одной вершины в другую и связывают сильные компоненты.

Для поиска достижимой вершины с максимальным номером (через обратную ссылку) из любого потомка каждой вершины в рекурсивной функции DFS выполняются те же вычисления, что и в программе 18.7. В ней также используется вектор, индексированный именами вершин, для отслеживания сильных компонентов и стек для хранения текущего пути поиска. Имена вершин заносятся в стек при входе в рекурсивную функцию, а после посещения последнего элемента каждого сильного компонента они выталкиваются из стека, при этом назначаются номера компонентам. Алгоритм основан на возможности определять этот момент при помощи простой проверки в конце рекурсивной процедуры (для этого отслеживается предок с максимальным номером, достижимый по одной восходящей ссылке из всех потомков каждого узла). Эта проверка сообщает, что все вершины, встреченные с момента входа (за исключением тех, которые уже приписаны какому-либо компоненту), принадлежат тому же сильному компоненту.

Реализация в программе 19.11 представляет собой полное описание рассматриваемого алгоритма, со всеми подробностями, которых нет в вышеприведенном общем описании. На рис 19.29 показана работа алгоритма на нашем демонстрационном орграфе с рис 19.1.

Программа 19.11. Сильные компоненты (алгоритм Тарьяна)

Данный класс DFS — еще одна реализация того же интерфейса, что и в программе 19.10. Он использует стек S для хранения каждой вершины до тех пор, пока не выяснится, что все вершины в верхней части стека до определенного уровня принадлежат одному и тому же сильному компоненту. Вектор low, индексированный именами вершин, отслеживает вершину с наименьшим прямым номером, достижимую из каждого узла через ряд нисходящих ссылок, за которыми следует одна восходящая ссылка (см. текст).

  #include "STACK.cc"
  template <class Graph>
  class SC
    { const Graph G;
      STACK<int> S;
      int cnt, scnt;
      vector<int> pre, low, id;
      void scR(int w)
        { int t;
          int min = low[w] = pre[w] = cnt+ + ;
          S.push(w);
          typename Graph::adjIterator A(G, w);
          for (t = A.beg(); !A.end(); t = A.nxt())
            { if (pre[t] == -1) scR(t);
              if (low[t] < min) min = low[t];
            }
          if (min < low[w]) { low[w] = min; return; }
          do
            { id[t = S.pop()] = scnt; low[t] = G.V(); }
          while ( t ! = w) ;
          scnt++;
       }
    public:
      SC(const Graph G) : G(G), cnt(0), scnt(0),
        pre(G.V(), -1), low(G.V()), id(G.V())
        { for (int v = 0; v < G.V(); v++)
            if (pre[v] == -1) scR(v);
        }
      int count() const { return scnt; }
      bool stronglyreachable(int v, int w) const
        { return id[v] == id[w]; }
    };

(рис 19.29) Вычисление сильных компонентов (алгоритмы Тарьяна и Габова)

В основе алгоритма Тарьяна лежит рекурсивный DFS с дополнительным помещением вершин в стек. Он вычисляет индекс компонента для каждой вершины в векторе id, индексированном именами вершин, используя вспомогательные векторы pre и low (в центре). Дерево DFS для нашего демонстрационного графа показано в верхней части рисунка, а трассировка ребер — внизу слева. В центре нижней части приведено содержимое главного стека: в него заносятся вершины, достижимые через древесные ребра. Используя DFS для перебора вершин в обратном топологическом порядке, мы вычисляем для каждой вершины v максимальную точку, достижимую через обратную ссылку из предшественника (low[v]). Когда для вершины v выполняется pre[v]= low[v] (в данном случае это вершины 11, 1, 0 и 7), мы выталкиваем из стека ее и все вершины выше нее, и присваиваем им всем номер следующего компонента.

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

Лемма 19.15. Алгоритм Тарьяна находит сильные компоненты орграфа за линейное время.

Схема доказательства. Если у вершины s нет потомков или восходящих ссылок в дереве DFS, либо если у нее есть потомок в дереве DFS с восходящей ссылкой, которая указывает на s, и нет потомков с восходящими ссылками, которые направлены в более высокую часть дерева, то она и все ее потомки (кроме вершин, которые удовлетворяют тому же свойству, и их потомков) составляют сильный компонент. Чтобы установить этот факт, заметим, что у каждого потомка t вершины s, который не удовлетворяет указанному свойству, имеется потомок с восходящей ссылкой, указывающей на вершину, которая находится в дереве выше t.

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

Как обычно, этот метод линеен по времени, поскольку он состоит из стандартного DFS с несколькими дополнительными операциями, выполняющимися за постоянное время. $$$\blacksquare$$$

В 1999 году Габов разработал версию алгоритма Тарьяна, приведенную в программе 19.12. Этот алгоритм использует такой же стек вершин и тем же способом, что и алгоритм Тарьяна, но он использует второй стек (вместо вектора прямых номеров, индексированного именами вершин) — для определения момента, когда нужно выталкивать из главного стека все вершины каждого сильного компонента. Этот второй стек содержит вершины, входящие в путь поиска. Когда обратное ребро показывает, что последовательность таких вершин целиком принадлежит одному и тому же сильному компоненту, мы выталкиваем содержимое этого стека, оставляя в нем только конечную вершину обратного ребра, которая находится ближе к корню дерева, чем любая другая вершина. После обработки всех ребер каждой вершины (выполняя рекурсивные вызовы всех ребер дерева, выталкивая из стека пути для обратных ребер и игнорируя прямые ребра), мы проверяем, находится ли текущая вершина в верхушке стека пути. Если это так, то она и все вершины над ней в главном стеке составляют сильный компонент — мы выталкиваем их из стека и присваиваем им номер следующего сильного компонента, как и в алгоритме Тарьяна.

Пример на рис 19.29 показывает содержимое этого второго стека. То есть эта диаграмма может служить иллюстрацией работы алгоритма Габова.

Программа 19.12. Сильные компоненты (алгоритм Габова)

Данная альтернативная реализация рекурсивной функции-члена из программы 19.11 использует вместо вектора low, индексированного номерами вершин, второй стек path, чтобы определять, когда нужно выталкивать из главного стека вершины каждого сильного компонента (см. текст).

  void scR(int w)
    { int v; 
      pre[w] = cnt++;
      S.push(w); path.push(w);
      typename Graph::adjIterator A(G, w);
      for (int t = A.beg(); !A.end(); t = A.nxt())
        if (pre[t] == -1)
          scR(t);
        else if (id[t] == -1)
          while (pre[path.top()] > pre[t]) path.pop();
      if (path.top() == w) path.pop(); else return;
      do { id[v = S.pop()] = scnt; } while (v != w);
      scnt++;
    }

Лемма 19.16. Алгоритм Габова находит сильные компоненты орграфа за линейное время.

Формализация вышеизложенного рассуждения и доказательство взаимосвязи содержимого стеков, на котором оно основано — полезное упражнение для математически подготовленных читателей (см. упражнение 19.132). Этот метод также линеен по времени, поскольку он состоит из стандартного DFS с несколькими дополнительными операциями, выполняющимися за постоянное время. $$$\blacksquare$$$

Все рассмотренные в данном разделе алгоритмы выявления сильных компонентов оригинальны и обманчиво просты. Мы рассмотрели все три алгоритма, поскольку они демонстрируют мощь фундаментальных структур данных и тщательно разработанных рекурсивных программ. С практической точки зрения время выполнения всех этих алгоритмов пропорционально количеству ребер орграфа, и различия в производительности больше зависят от деталей реализации. Например, внутренний цикл алгоритмов Тарьяна и Габова составляют операции АТД стека магазинного типа. В нашей реализации используются простейшие реализации класса стека из ; реализации, использующие контейнеры stack из библиотеки STL, которые выполняют разные проверки и других действия, могут работать медленнее. Реализация алгоритма Косарайю — пожалуй, простейшая из всех трех, но она содержит небольшой недостаток (для разреженных графов): в ней выполняются три прохода по ребрам (один проход для построения обратного графа и два прохода поиска в глубину).

Теперь мы рассмотрим ключевое приложение, вычисляющее сильные компоненты: построение АТД эффективной достижимости (абстрактное транзитивное замыкание) в орграфах.

Упражнения

19.120. Опишите, что произойдет, если воспользоваться алгоритмом Косарайю для поиска сильных компонентов DAG-графа.

19.121. Опишите, что произойдет, если воспользоваться алгоритмом Косарайю для поиска сильных компонентов орграфа, который состоит из одного цикла.

19.122. Можно ли не вычислять обращение орграфа в версии метода Косарайю для представления списками смежности (программа 19.10), используя одну из трех технологий, описанных в разделе 19.4, которые позволяют не вычислять обращение при выполнении топологической сортировки? Для каждой технологии либо докажите, что она работает, либо приведите контрпример, показывающий, что она не работает.

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

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

3-71-47-80-55-23-82-90-64-92-66-4.

19.125. Реализуйте алгоритм Косарайю для поиска сильных компонентов орграфа в представлении, которое поддерживает проверку существования ребра. Реализация не должна содержать явное вычисление обращения графа. Указание. Рассмотрите возможность использования двух различных рекурсивных функций DFS.

19.126. Опишите, что произойдет, если использовать алгоритм Тарьяна для поиска сильных компонентов DAG-графа.

19.127. Опишите, что произойдет, если использовать алгоритм Тарьяна для поиска сильных компонентов орграфа, который состоит из одного цикла.

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

19.129. Покажите в стиле рис 19.28 лес DFS, содержимое стека во время выполнения алгоритма и окончательное содержимое вспомогательных векторов, индексированных именами вершин, которые получаются при использовании алгоритма Тарья-на для вычисления сильных компонентов орграфа

3-71-47-80-55-23-82-90-64-92-66-4.

19.130. Измените реализации алгоритма Тарьяна в программе 19.11 и алгоритма Габова в программе 19.12, чтобы они могли использовать сигнальные значения и не выполнять явную проверку поперечных ссылок.

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

3-71-47-80-55-23-82-90-64-92-66-4.

19.132. Приведите полное доказательство леммы 19.16.

19.133. Разработайте версию алгоритма Габова, которая находит мосты и реберносвязные компоненты в неориентированных графах.

19.134. Разработайте версию алгоритма Габова, который находит точки сочленения и двусвязные компоненты в неориентированных графах.

19.135. Составьте таблицу в стиле таблица 18.1 для изучения сильных компонентов в случайных графах (см. таблица 19.2). Пусть S — множество вершин в наибольшем сильном компоненте. Изменяя размер множества S, проанализируйте процент ребер в следующих четырех классах: соединяющие две вершины внутри S, указывающие на вершины вне S, указывающие на вершины внутри S, и соединяющие две вершины вне S.

19.136. Эмпирически сравните примитивный метод вычисления сильных компонентов, описанный в начале этого раздела, с алгоритмом Косарайю, с алгоритмом Тарьяна и с алгоритмом Габова для различных типов орграфов (см. упражнения 19.11-19.18).

19.137. Разработайте линейный по времени алгоритм для задачи сильной 2-связности: нужно определить, остается ли сильно связанный орграф сильно связным после удаления любой вершины (и всех инцидентных ей ребер).

Еще раз о транзитивном замыкании

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

В основе этого алгоритма лежит предварительная обработка — построение коренного DAG-графа исходного орграфа (см. лемму 19.2). Алгоритм эффективен, если размер коренного DAG-графа меньше размеров исходного орграфа. Если исходный граф сам является DAG-графом (и поэтому идентичен коренному DAG) или если он содержит лишь несколько небольших циклов, экономия будет незначительной. Но если орграф содержит большие циклы или большие сильные компоненты (т.е. небольшой коренной DAG), то можно разработать оптимальные либо почти оптимальные алгоритмы. Для определенности предположим, что коренной DAG достаточно мал, чтобы представить его матрицей смежности, хотя основная идея применима и для больших коренных DAG.

Для реализации абстрактного транзитивного замыкания мы выполним следующую предварительную обработку графа:

Найдем его сильные компоненты.

Построим его коренной DAG.

Вычислим транзитивное замыкание коренного DAG.

Для поиска сильных компонентов можно воспользоваться алгоритмом Косарайю, Тарьяна или Габова; затем выполнить один проход по ребрам для построения коренного DAG (как описано в следующем абзаце); и выполнить поиск в глубину (программа 19.9) для вычисления транзитивного замыкания. После этой предварительной обработки можно непосредственно получать информацию, необходимую для определения достижимости.

При наличии вектора, индексированного именами вершин, с сильными компонентами орграфа построение представления его коренного DAG в виде матрицы смежности не представляет труда. Вершины DAG-графа являются номерами компонентов орграфа. Для каждого ребра s-t исходного графа нужно просто занести в D->adj[sc[s]] [sc[t]] значение 1. Если бы мы воспользовались представлением списками смежности, нам пришлось бы решать проблему одинаковых ребер в коренном DAG, а в матрице смежности повторяющиеся ребра просто соответствуют занесению 1 в элемент матрицы, который уже равен 1. Этот нюанс очень важен, т.к. в рассматриваемом приложении количество одинаковых ребер в принципе может быть огромным (по сравнению с размером коренного DAG).

Лемма 19.17. Пусть s и t — две вершины в орграфе D, а sc(s) и sc(t) — соответствующие им вершины в коренном DAG-графе K орграфа D. Тогда t достижима из s в D тогда и только тогда, когда sc(t) достижима из sc(s) в K.

Этот простой факт следует из определений. В частности, в данной лемме предполагается, что любая вершина достижима сама из себя (все вершины имеют петли). Если две вершины находятся в одном и том же сильном компоненте (sc(s) = sc(t)), то они взаимно достижимы. $$$\blacksquare$$$

Для определения, достижима ли вершина t из заданной вершины s, мы воспользуемся тем же способом, что и для построения коренного DAG. С помощью вектора, индексированного именами вершин, который вычисляется алгоритмом определения сильных компонентов, мы получим (за постоянное время) номера компонентов sc(s) и sc(t), которые будем рассматривать как индексы абстрактных вершин (abstract vertex) в коренном DAG. Их использование в качестве индексов вершин для транзитивного замыкания коренного DAG даст искомый результат.

Программа 19.13 воплощает эти идеи в реализации АТД абстрактного транзитивного замыкания. Кроме того, мы используем интерфейс абстрактного транзитивного замыкания и в коренном DAG. Время выполнения этой реализации зависит не только от количества вершин и ребер орграфа, но и от свойств его коренного DAG. Для анализа алгоритма предположим, что коренной DAG представляется матрицей смежности, поскольку мы ожидаем, что коренной DAG является небольшим и, скорее всего, насыщенным.

Лемма 19.18. На запросы относительно абстрактного транзитивного замыкания орграфа можно отвечать за постоянное время, при затратах памяти, пропорциональных V + v2, и времени, пропорциональных E + v2 + vx, на предварительную обработку (вычисление транзитивного замыкания). Здесь v означает количество вершин в коренном DAG, а x — количество поперечных ребер в его лесе DFS.

Доказательство. Непосредственно следует из леммы 19.13. $$$\blacksquare$$$

Если орграф сам является DAG-графом, то вычисление сильных компонентов не дает никакой новой информации, а этот алгоритм делает то же, что и программа 19.9; однако в орграфах общего вида, содержащих циклы, этот алгоритм обычно работает гораздо быстрее, чем алгоритм Уоршелла или решение на основе DFS. Например, из леммы 19.18 сразу вытекает следующий результат.

Лемма 19.19. Можно отвечать за постоянное время на запросы относительно транзитивного замыкания любого графа, в коренном DAG которого содержится менее $$$\sqrt[3]{V}$$$ вершин, при затратах объема памяти, пропорционального V, и времени, пропорционального E + V, на предварительную обработку.

Доказательство. Достаточно подставить $$$v< \sqrt[3]{V}$$$ в лемму 19.18 и учесть, что x < v2. $$$\blacksquare$$$

Программа 19.13. Транзитивное замыкание на основе сильных компонентов

В данном классе реализован интерфейс (абстрактного) транзитивного замыкания орграфов путем вычисления сильных компонентов (с помощью, скажем, программы 19.11), коренного DAG и транзитивного замыкания коренного DAG (программой 19.9). Предполагается, что в классе SC имеется общедоступная функция-член ID, которая возвращает индекс сильного компонента (из массива id) для любой заданной вершины. Эти числа представляют собой индексы вершин в коренном DAG. Вершина t орграфа достижима из вершины s тогда и только тогда, когда ID(t) достижима из ID(s) в коренном DAG.

  template <class Graph>
  class TC
    { const Graph G; DenseGRAPH *K;
      dagTC<DenseGRAPH, Graph> *Ktc;
      SC<Graph> *Gsc;
    public:
      TC(const Graph G) : G(G)
        { Gsc = new SC<Graph>(G);
          K = new DenseGRAPH(Gsc->count(), true);
          for (int v = 0; v < G.V(); v++)
            { typename Graph::adjIterator A(G, v);
              for (int t = A.beg(); !A.end(); t = A.nxt())
                K->insert(Edge(Gsc->ID(v), Gsc->ID(t)));
            }
          Ktc = new dagTC<DenseGRAPH, Graph>(*K);
        }
    ~TC() { delete K; delete Ktc; delete Gsc; }
    bool reachable(int v, int w)
        { return Ktc->reachable(Gsc->ID(v), Gsc->ID(w)); }
    } ;

Можно рассмотреть и другие варианты этих границ. Например, если мы можем выделить объем памяти, пропорциональный E, то можно достичь того же времени, когда коренной DAG содержит до $$$\sqrt[3]{E}$$$ вершин. Более того, эти временные границы обычно завышены, поскольку они предполагают, что коренной DAG насыщен поперечными ребрами — конечно, это совсем не обязательно.

Главный ограничивающий фактор применимости этого метода — это размер коренного DAG. Чем больше рассматриваемый орграф похож на DAG-граф (чем больше его коренной DAG), тем труднее вычислить его транзитивное замыкание. Обратите внимание: мы (конечно) не нарушили нижней границы, установленной в лемме 19.9, поскольку для насыщенных DAG-графов алгоритм выполняется за время, пропорциональное V³. Мы просто значительно расширили класс графов, для которых производительность выше, чем в худшем случае. Вообще-то сложно построить модель случайного орграфа для генерации орграфов, на которых рассматриваемый алгоритм работает медленно (см. упражнение 19.142).

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

Свойства случайных орграфов
E	Случайные ребра		Случайные из 10 соседей
E	v	e	v	e
1000 вершин
1000	983	981	916	755
2000	424	621	713	1039
5000	13	13	156	313
10000	1	1	8	17
20000	1	1	1	1
10000 вершин
50000	144	150	1324	150
100000	1	1	61	123
200000	1	1	1	1

Обозначения:
v	Количество вершин в коренном DAG
e	Количество ребер в коренном DAG

В данной таблице показано количество вершин и ребер в коренных DAG для случайных орграфов, построенных на базе двух различных моделей (ориентированные версии моделей из таблицы 18.1). В обоих случаях при увеличении насыщенности коренной DAG-граф получается небольшим (и разреженным).

Упражнения

19.138. Разработайте версию реализации абстрактного транзитивного замыкания для орграфов с представлением коренного DAG в виде разреженного графа. Основная сложность состоит в устранении из списка одинаковых ребер без излишних затрат времени или памяти (см. упражнение 19.65).

19.139. Приведите коренной DAG, вычисленный программой 19.13, и его транзитивное замыкание для орграфа

3-71-47-80-55-23-82-90-64-92-66-4.

19.140. Преобразуйте реализацию абстрактного транзитивного замыкания на основе вычисления сильных компонентов (программа 19.13) в эффективную программу, которая вычисляет матрицу смежности транзитивного замыкания орграфа, представленного матрицей смежности, используя алгоритм Габова для вычисления сильных компонентов и усовершенствованный алгоритм Уоршелла для вычисления транзитивного замыкания DAG-графа.

19.141. Эмпирически оцените ожидаемый размер коренного DAG для различных видов орграфов (см. упражнения 19.11—19.18).

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

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

Перспективы

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

На протяжении данной главы постоянно упоминалось решение задачи абстрактного транзитивного замыкания, где используется АТД, который после предварительной обработки может определить, существует ли ориентированный путь из одной заданной вершины в другую. Хотя нижняя граница затрат на предварительную обработку в худшем случае значительно больше V², метод, рассмотренный в разделе 19.7, сводит базовые методы из этой главы к простому решению, которое обеспечивает оптимальную производительность для многих типах орграфов; заметное исключение составляют лишь насыщенные DAG-графы. Нижняя граница означает, что трудно достичь более высокой гарантированной производительности на всех графах, однако для графов, встречающихся на практике, рассмотренные методы позволяют получить неплохую производительность.

Трудоемкость операций обработки орграфов в худшем случае
Задача	Затраты	Алгоритм
Орграфы
Обнаружение циклов	E	DFS
Транзитивное замыкание	`V(E+V)`	DFS из каждой вершины
Кратчайшие пути из одного источника	E	DFS
Все кратчайшие пути	`V(E+V)`	DFS из каждой вершины
Сильные компоненты	E	Косарайю, Тарьяна или Габова
Транзитивное замыкание	`E+v(v+x)`	Коренной DAG
DAG-графы
Проверка на отсутствие циклов	E	DFS или очередь истоков
Топологическая сортировка	E	DFS или очередь истоков
Транзитивное замыкание	`V(E+V)`	DFS
Транзитивное замыкание	`V(E+X)`	DFS / динамическое программирование

Здесь приведены данные о затратах (время выполнения в худшем случае) на выполнение различных задач обработки орграфов, рассмотренных в этой главе — для случайных графов и графов, в которых ребра случайным образом соединяют каждую вершину с одной из 10 заданных соседних вершин. Все затраты определялись для представления списками смежности. В случае представления матрицей смежности вместо E элементов появляются V² элементов, и тогда, например, затраты на вычисление всех кратчайших путей пропорциональны V³. Линейные по времени алгоритмы являются оптимальными, поэтому затраты позволяют с достаточной уверенностью предсказывать время выполнения для любых входных данных; оценки для других могут быть слишком осторожными, и время выполнения для некоторых видов графов может оказаться меньшим. Характеристики производительности самого быстрого алгоритма вычисления транзитивного замыкания орграфа зависят от структуры орграфа — в частности, от размера его коренного DAG.

Разработка алгоритмов с характеристиками производительности, аналогичными характеристикам алгоритмов объединения-поиска из , для насыщенных орграфов остается призрачной мечтой. В идеальном случае хотелось бы определить АТД, позволяющий добавлять ориентированные ребра или проверять достижимость одной вершины из другой, и разработать реализацию с выполнением всех операций за постоянное время (см. упражнения 19.153—19.155). Как было сказано в , можно довольно близко подойти к этой цели в случае неориентированных графов, но аналогичные решения для орграфов или DAG-графов до сих пор не известны. (Учтите, что удаление ребер — сложная задача даже для неориентированных графов.) Эта задача динамической достижимости (dynamic reachability) не только интересует математиков и имеет практическое применение, но и играет исключительно важную роль в разработке алгоритмов на более высоком уровне абстракции. Например, достижимость лежит в основе задачи реализации сетевого симплексного алгоритма для определения потоков с минимальной стоимостью — эту широко применяемую модель решения задач мы рассмотрим в .

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

Доминаторы. Пусть задан DAG-граф, все вершины которого достижимы из одного истока г. Говорят, что вершина v доминирует (dominate) над вершиной t, если каждый путь из г в t содержит s. (В частности, каждая вершина доминирует сама над собой.) Каждая вершина v, отличная от источника, имеет непосредственный доминатор, который доминирует над вершиной v, но не доминирует над другим доминатором v и над самим собой. Множество непосредственных доминаторов представляет собой дерево, которое охватывает все вершины, достижимые из источника. Эта структура имеет важное значение для построения компиляторов. Доминаторное дерево может быть вычислено за линейное время с помощью подхода на основе DFS, который использует несколько вспомогательных структур данных, хотя обычно на практике применяется несколько более медленная версия.

Транзитивное приведение. Для заданного орграфа требуется найти орграф, который имеет то же транзитивное замыкание и минимальное количество ребер из всех таких орграфов. Эта задача разрешима (см. упражнение 19.150); однако при дополнительном ограничении — чтобы результатом был подграф исходного графа — она является NP-трудной.

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

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

Ориентированный гамильтонов путь. Нужно найти в орграфе простой ориентированный путь максимальной длины. Эта задача относится к числу NP-трудных, однако легко решается, если граф представляет собой DAG (см. упражнение 19.114).

Односвязный подграф. Говорят, что граф односвязен (uniconnected), если между любой парой вершин существует не более чем один ориентированный путь. Если задан орграф и целое число к, нужно определить, существует ли односвязный подграф с не менее чем к ребрами. Для произвольного к эта задача является NP-трудной.

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

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

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

Упражнения

19.144. Используйте программы 17.18 и 17.19 для реализации функции АТД, которая выводит эйлеров путь в орграфе, если он существует. Поясните назначение каждого изменения и дополнения, которые понадобится внести в код.

19.145. Начертите дерево доминаторов орграфа

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6

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

19.147. Найдите транзитивное приведение орграфа

3-71-47-80-55-23-02-90-64-92-66-41-58-29-08-34-52-31-63-57-6

19.148. Найдите подграф графа

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6

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

19.149. Докажите, что у каждого DAG-графа имеется уникальное транзитивное приведение, и напишите эффективную реализацию функции АТД для вычисления транзитивного приведения DAG-графа.

19.150. Напишите эффективную функцию АТД для орграфов, которая вычисляет транзитивное приведение.

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

19.152. Найдите наибольший односвязный подграф в орграфе

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6

19.153. Напишите класс орграфа, который поддерживает операции вставки ребра, удаления ребра и проверки, находятся ли две вершины в одном и том же сильном компоненте. Операции построения, вставки ребра и удаления должны выполняться за линейное время, а ответы на запросы о сильной связности — за постоянное время.

19.154. Выполните упражнение 19.153 так, чтобы вставка ребра, удаление ребра и запросы относительно сильных компонентов выполнялись за время, пропорциональное log V в худшем случае.

19.155. Выполните упражнение 19.153 так, чтобы вставка ребра, удаление ребра и запросы относительно сильных компонентов выполнялись за почти постоянное время (как в алгоритмах поиска-объединения для определения связности в неориентированных графах).

Страницы:

(рис 19.1)

Ориентированный граф (орграф)

(рис 19.2) Подсчет количества графов

Упражнения

19.3. Постройте таблицу, аналогичную представленной на рис 19.2, но без учета графов и орграфов с петлями.

19.4. Каково количество орграфов, содержащих V вершин и E ребер?

19.5. Сколько орграфов соответствует каждому неориентированному графу, содержащему V вершин и E ребер?

19.6. Сколько цифр содержит десятичное число, равное количеству орграфов с V вершинами и E ребрами?

19.7. Начертите неизоморфные орграфы, содержащие три вершины.

Глоссарий и правила игры

(рис 19.3) Решетчатый орграф

(рис 19.4) Представления орграфа

(рис 19.5) Обращение орграфа

Программа 19.1. Обращение орграфа

  template <class inGraph, class outGraph>
  void reverse(const inGraph G, outGraph R)
    { for (int v = 0; v < G.V(); v++)
        { typename inGraph::adjIterator A(G, v);
          for (int w = A. beg() ; !A.end() ;
            w = A.nxt())
          R.insert(Edge(w, v));
        }
    }

(рис 19.6) Ориентированный ациклический граф (DAG-граф)

В этом графе нет циклов, хотя это не очевидно ни из списка ребер, ни даже из чертежа графа.

(рис 19.7) Терминология орграфов

(рис 19.8) Сильные компоненты и коренной DAG

достижима ли t из s;

являются ли s и t сильно связными (взаимно достижимыми).

Упражнения

19.10. Приведите структуру списков смежности, построенных программой 17.9 для орграфа

3-71-47-80-55-23-82-90-64-92-66-4.

19.21. Покажите структуру списков смежности, которая получится при построении обращения орграфа

3-71-47-80-55-23-82-90-64-92-66-4

с помощью программы 19.1.

19.22. Опишите обращение отображения.

19.26. Приведите сильные компоненты и коренной DAG для орграфа

3-71-47-80-55-23-82-90-64-92-66-4.

19.27. Приведите коренной DAG решетчатого орграфа с рис 19.3.

19.28. Сколько графов имеют V вершин, каждая из которых имеет степень выхода, равную k?

Анатомия DFS в орграфах

(рис 19.9) Лес DFS для орграфов

Прямой	Обратный	Пример	Тип ребра
<	>	`4-2`	Нисходящее
>	<	`2-0`	Обратное
>	>	`7-6`	Поперечное

Ребра, представляющие рекурсивный вызов (древесные (tree) ребра).

Ребра, ведущие из вершины к предку в ее дереве DFS (обратные (back) ребра).

Ребра, ведущие из вершины к потомку в ее дереве DFS (нисходящие (down) ребра).

(рис 19.10) Трассировка орграфа поиска в глубину

(рис 19.11) Лес DFS на орграфе

Программа 19.2. DFS на орграфе

  template <class Graph>
  class DFS
    { const Graph G;
      int depth, cnt, cntP;
      vector<int> pre, post;
      void show(char *s, Edge e)
        { for (int i = 0; i < depth; i++) 
        cout << " ";
          cout << e.v << "-" << e.w << s << endl;
        }
      void dfsR(Edge e)
        { int w = e.w; show(" древесное", e);
          pre[w] = cnt++; depth++;
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            { Edge x( w, t) ;
              if (pre[t] == -1) dfsR(x);
              else if (post[t] == -1) show(" обратное", x);
              else if (pre[t] > pre[w]) show(" нисходящее", x);
              else show(" поперечное", x);
            }
          post[w] = cntP++; depth--;
        }
    public:
      DFS(const Graph G) : G(G), cnt(0), cntP(0),
        pre(G.V(), -1), post(G.V(), -1)
        { for (int v = 0; v < G.V(); v++)
            if (pre[v] == -1) dfsR(Edge(v, v));
        }
    };

Например, рассмотрим следующую фундаментальную задачу.

(рис 19.12) Декомпозиция орграфа

Упражнения

19.30. Начертите лес DFS, который получается при выполнении поиска в глубину на орграфе

3-71-47-80-55-23-82-90-64-92-66-4,представленно мспискамисмежно сти.

19.31. Начертите лес DFS, который получается при выполнении поиска в глубину на орграфе

3-71-47-80-55-23-82-90-64-92-66-4,представленно мматрицейсмежно сти.

19.34. Покажите все возможные леса DFS для орграфа

0-10-20-31-32-3,

и сведите в таблицу количество древесных, обратных, поперечных и нисходящих ребер для каждого леса.

19.37. Постройте связный DAG-граф, удалив в графе, который изображен на рис 19.1, пять ребер (см. р рис 19.11).

Достижимость и транзитивное замыкание

(рис 19.13) Транзитивное замыкание

  for (s = 0; s < V; s++)
    for (t = 0; t < V; t++)
      for (i = 0, C[s][t] = 0; i < V; i++)
        C[s][t] = A[s][i] * B[i][t];

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

  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;

(рис 19.14) Вычисление квадрата матрицы смежности

(рис 19.15) Степени матрицы смежности и ориентированные пути

) можно вычислить транзитивное замыкание орграфа за время, пропорциональное V³.

(рис 19.16) Алгоритм Уоршелла

Программа 19.3. Алгоритм Уоршелла

  template <class tcGraph, class Graph>
    class TC
      { tcGraph T;
      public:
        TC(const Graph G) : T(G)
        { for (int s = 0; s < T.V(); s++)
          T.insert(Edge(s, s));
          for (int i = 0; i < T.V(); i++)
            for (int s = 0; s < T.V(); s++)
              if (T.edge(s, i))
                for (int t = 0; t < T.V(); t++)
                  if (T.edge(i, t))
                    T.insert(Edge(s, t));
        }
      bool reachable(int s, int t) const
        { return T.edge(s, t); }
      } ;

Для заданного орграфа мы инициализируем целочисленную матрицу A размером

  V х V: элемент A[s][t] содержит 1, если в орграфе существует ребро из s в t, 
или сигнальное значение V, если такого ребра нет. 
Эту задачу выполняет следующий код:
    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])
            A[s][t] = A[s][i] + A[i][t];

Программа 19.4. Вычисление транзитивного замыкания на основе поиска в глубину

  template <class Graph>
  class tc
    { Graph T; const Graph G;
      void tcR(int v, int w)
        { T.insert(Edge(v, w));
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (!T.edge(v, t)) tcR(v, t);
        }
    public:
      tc(const Graph G) : G(G), T(G.V(), true)
        { for (int v = 0; v < G.V(); v++) tcR(v, v); }
      bool reachable(int v, int w)
        { return T.edge(v, w); }
    };

Эмпирическое сравнение алгоритмов транзитивного замыкания
Разреженные (`10V` ребер)					Насыщенные (250 вершин)
V	W	W*	A	L	E	W	W*	A	L
25	0	0	1	0	5000	289	203	177	23
50	3	1	2	1	10000	300	214	184	38
125	35	24	23	4	25000	309	226	200	97
250	275	181	178	13	50000	315	232	218	337
500	2222	1438	1481	54	100000	326	246	235	784

Обозначения:
W	Алгоритм Уоршелла (раздел 19.3)
W*	Усовершенствованный алгоритм Уоршелла (программа 19.3)
A	DFS по матрице смежности (программы 19.4 и 17.7)
L	DFS по спискам смежности (программа 17.9)

Упражнения

19.46. Как выглядит транзитивное замыкание орграфа, который состоит лишь из направленного цикла с V вершинами?

19.48. Приведите транзитивное замыкание неориентированного графа

3-71-47-80-55-23-82-90-64-92-66-4.

19.51. Представьте в стиле рис 19.15 процесс вычисления транзитивного замыкания орграфа

3-71-47-80-55-23-82-90-64-92-66-4

многократным возведением в квадрат.

19.52. Представьте в стиле рис 19.16 процесс вычисления транзитивного замыкания орграфа

3-71-47-80-55-23-82-90-64-92-66-4 с помощью алгоритма Уоршелла.

19.58. Является ли произведение двух симметричных булевых матриц симметричным? Обоснуйте ваш ответ.

Отношения эквивалентности и частичные порядки

(рис 19.17) DAG-граф включения множеств

Отношения и орграфы.

Симметричные отношения и неориентированные графы.

Транзитивные отношения и пути в графах.

Отношения эквивалентности и пути в неориентированных графах.

Частичные порядки и пути в DAG-графах.

Упражнения

DAG -графы

Возможно, простейшую нетривиальную задачу составления расписания можно сформулировать следующим образом:

  void traverseR(Dag D, int v)
    { visit(v);
      typename Dag::adjIterator A(D, v);
      for (int t = A.beg(); !A.end(); t = A.nxt())
        traverseR(D, t);
    }

(рис 19.18) Модель DAG вычислений чисел Фибоначчи

(рис 19.19) Представление арифметического выражение с помощью DAG-графа

(рис 19.20) Сжатие бинарного дерева

Программа 19.5. Представление бинарного дерева в виде бинарного DAG-графа

  int compressR(link h)
    { STx st;
      if (h == NULL) return 0;
      l = compressR(h->l);
      r = compressR(h->r);
      t = st. index(l, r) ;
      adj[t].l = l; adj[t].r = r;
      return t;
    }

Упражнения

19.75. Реализуйте класс DFS, который может использоваться клиентами для проверки, что DAG-граф не содержит циклов.

19.77. Сколько узлов содержит дерево и DAG-граф, соответствующие рис 19.18, для вычисления N-го числа Фибоначчи (F_N)?

19.79. Разработайте АТД для бинарных DAG-графов.

19.80. Можно ли любой DAG представить в виде бинарного DAG (см. лемму 5.4)?

19.89. Начертите все неизоморфные DAG-графы с двумя, тремя, четырьмя и пятью вершинами.

19.90. Сколько существует различных DAG-графов с Vвершинами E ребрами?

Топологическая сортировка

(рис 19.21) Топологическая сортировка (перенумерация)

  for (i = 0; i < V; i++) tsI[ts[i]] = i;

  for (i = 0; i < V; i++) ts[tsI[i]] = i;

8 7 0 1 2 3 6 4 9 10 11 12 5

0 1 2 3 8 6 4 9 10 11 12 5 7

0 2 3 8 6 4 7 5 9 10 1 11 12

8 0 7 6 2 3 4 9 5 1 11 12 10

(рис 19.22) Топологическая сортировка (переупорядочение)

(рис 19.23) Обратная топологическая сортировка

(рис 19.24) Лес DFS для DAG-графа

Программа 19.6. Обратная топологическая сортировка

  template <class Dag>
  class dagTS
    { const Dag D;
      int cnt, tcnt;
      vector<int> pre, post, postI;
      void tsR(int v)
        { pre[v] = cnt++;
          typename Dag::adjIterator A(D, v);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (pre[t] == -1) tsR(t);
          post[v] = tcnt; postI[tcnt++] = v;
        }
    public:
      dagTS(const Dag D) : D(D), tcnt(0), cnt(0),
        pre(D.V(), -1), post(D.V(), -1), postI(D.V(), -1)
        { for (int v = 0; v < D.V(); v++)
          if (pre[v] == -1) tsR(v);
        }
      int operator[](int v) const { return postI[v]; }
      int relabel(int v) const { return post[v]; }
    };

Выполните обратную топологическую сортировку на обращении заданного DAG-графа.

Программа 19.7. Топологическая сортировка

  void tsR(int v)
    { pre[v] = cnt++;
      for (int w = 0; w < D.V(); w++)
        if (D.edge(w, v))
          if (pre[w] == -1) tsR(w);
      post[v] = tcnt; postI[tcnt++] = v;
    }

Лемма 19.12. У каждого DAG-графа имеется по меньшей мере один исток и по меньшей мере один сток.

Удаляем исток из очереди и присваиваем ему номер.

(рис 19.25) Топологическая сортировка DAG-графа методом удаления истоков

Программа 19.8. Топологическая сортировка с очередью истоков

    #include "QUEUE.cc"
    template <class Dag>
    class dagTS
      { const Dag D;
        vector<int> in, ts, tsI;
      public:
        dagTS(const Dag D) : D(D), in(D.V(), 0), ts(D.V(), -1), tsI(D.V(), -1)
        { QUEUE<int> Q;
          for (int v = 0; v < D.V(); v++)
            { typename Dag::adjIterator A(D, v);
              for (int t = A.beg(); !A.end(); t = A.nxt())
                in[t]+ + ;
            }
          for (int v = 0; v < D.V(); v++)
            if (in[v] == 0) Q.put(v);
          for (int j = 0; !Q.empty(); j++)
            { ts[j] = Q.get(); tsI[ts[j]] = j;
              typename Dag::adjIterator A(D, ts[j]);
              for (int t = A.beg(); !A.end(); t = A.nxt())
                if (—in[t] == 0) Q.put(t);
            }
        }
        int operator[](int v) const { return ts[v]; }
        int relabel(int v) const { return tsI[v]; }
      };

(рис 19.26) Таблица степеней захода и содержимое очереди

Обработка вершин после рекурсивных вызовов при выполнении поиска в глубину.

Упражнения

19.93. Сколько возможно различных топологических сортировок для DAG-графа, изображенного на рис 19.6?

3-71-47-80-55-23-82-90-64-92-66-44-32-3.

3-71-47-80-55-23-82-90-64-92-66-44-32-3

3-71-47-80-55-23-82-90-64-92-66-44-32-3(см.про грамму19.7).

19.100. Покажите в стиле рис 19.26 процесс топологической сортировки DAG-графа

3-71-47-80-55-23-82-90-64-92-66-44-32-3 с помощью алгоритма, использующего очередь истоков (программа 19.8).

Достижимость в DAG-графах

(рис 19.27) Транзитивное замыкание DAG-графа

Программа 19.9. Транзитивное замыкание DAG-графа

  template <class tcDag, class Dag>
  class dagTC
    { tcDag T; const Dag D;
      int cnt;
      vector<int> pre;
      void tcR(int w)
        { pre[w] = cnt++;
          typename Dag::adjIterator A(D, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            { T.insert(Edge(w, t));
              if (pre[t] > pre[w]) continue;
              if (pre[t] == -1) tcR(t);
              for (int i = 0; i < T.V(); i++)
                if (T.edge(t, i)) T.insert(Edge(w, i));
            }
        }
    public:
      dagTC(const Dag D) : D(D), cnt(0),
        pre(D.V(), -1), T(D.V(), true)
        { for (int v = 0; v < D.V(); v++)
          if (pre[v] == -1) tcR(v);
        }
      bool reachable(int v, int w) const
        { return T.edge(v, w); }
    } ;

Упражнения

19.115. Покажите в стиле рис 19.27 векторы достижимости, если для вычисления транзитивного замыкания DAG-графа

3-71-47-80-55-23-82-90-64-92-66-44-32-3

использовать программу 19.9.

Сильные компоненты в орграфах

(рис 19.28) Вычисление сильных компонентов (алгоритм Косарайю)

Программа 19.10. Сильные компоненты (алгоритм Косарайю)

  template <class Graph>
  class SC
    { const Graph G;
      int cnt, scnt;
      vector<int> postI, postR, id;
      void dfsR(const Graph G, int w)
        { id[w] = scnt;
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (id[t] == -1) dfsR(G, t);
          postI[cnt++] = w;
        }
    public:
      SC(const Graph G) : G(G), cnt(0), scnt(0),
        postI(G.V()), postR(G.V()), id(G.V(), -1)
        { Graph R(G.V(), true);
          reverse(G, R);
          for (int v = 0; v < R.V(); v++)
            if (id[v] == -1) dfsR(R, v);
          postR = postI; cnt = scnt = 0;
          id.assign(G.V(), -1);
          for (int v = G.V()-1; v >= 0; v--)
            if (id[postR[v]] == -1)
              { dfsR(G, postR[v]); scnt++; }
        }
      int count() const { return scnt; }
      bool stronglyreachable(int v, int w) const
        { return id[v] == id[w]; }
    };

Лемма 19.14. Метод Косарайю находит сильные компоненты графа с линейными затратами времени и памяти.

Программа 19.11. Сильные компоненты (алгоритм Тарьяна)

  #include "STACK.cc"
  template <class Graph>
  class SC
    { const Graph G;
      STACK<int> S;
      int cnt, scnt;
      vector<int> pre, low, id;
      void scR(int w)
        { int t;
          int min = low[w] = pre[w] = cnt+ + ;
          S.push(w);
          typename Graph::adjIterator A(G, w);
          for (t = A.beg(); !A.end(); t = A.nxt())
            { if (pre[t] == -1) scR(t);
              if (low[t] < min) min = low[t];
            }
          if (min < low[w]) { low[w] = min; return; }
          do
            { id[t = S.pop()] = scnt; low[t] = G.V(); }
          while ( t ! = w) ;
          scnt++;
       }
    public:
      SC(const Graph G) : G(G), cnt(0), scnt(0),
        pre(G.V(), -1), low(G.V()), id(G.V())
        { for (int v = 0; v < G.V(); v++)
            if (pre[v] == -1) scR(v);
        }
      int count() const { return scnt; }
      bool stronglyreachable(int v, int w) const
        { return id[v] == id[w]; }
    };

(рис 19.29) Вычисление сильных компонентов (алгоритмы Тарьяна и Габова)

Лемма 19.15. Алгоритм Тарьяна находит сильные компоненты орграфа за линейное время.

Программа 19.12. Сильные компоненты (алгоритм Габова)

  void scR(int w)
    { int v; 
      pre[w] = cnt++;
      S.push(w); path.push(w);
      typename Graph::adjIterator A(G, w);
      for (int t = A.beg(); !A.end(); t = A.nxt())
        if (pre[t] == -1)
          scR(t);
        else if (id[t] == -1)
          while (pre[path.top()] > pre[t]) path.pop();
      if (path.top() == w) path.pop(); else return;
      do { id[v = S.pop()] = scnt; } while (v != w);
      scnt++;
    }

Лемма 19.16. Алгоритм Габова находит сильные компоненты орграфа за линейное время.

Упражнения

3-71-47-80-55-23-82-90-64-92-66-4.

19.126. Опишите, что произойдет, если использовать алгоритм Тарьяна для поиска сильных компонентов DAG-графа.

3-71-47-80-55-23-82-90-64-92-66-4.

19.132. Приведите полное доказательство леммы 19.16.

Еще раз о транзитивном замыкании

Найдем его сильные компоненты.

Построим его коренной DAG.

Вычислим транзитивное замыкание коренного DAG.

Доказательство. Непосредственно следует из леммы 19.13. $$$\blacksquare$$$

Доказательство. Достаточно подставить $$$v< \sqrt[3]{V}$$$ в лемму 19.18 и учесть, что x < v2. $$$\blacksquare$$$

Программа 19.13. Транзитивное замыкание на основе сильных компонентов

  template <class Graph>
  class TC
    { const Graph G; DenseGRAPH *K;
      dagTC<DenseGRAPH, Graph> *Ktc;
      SC<Graph> *Gsc;
    public:
      TC(const Graph G) : G(G)
        { Gsc = new SC<Graph>(G);
          K = new DenseGRAPH(Gsc->count(), true);
          for (int v = 0; v < G.V(); v++)
            { typename Graph::adjIterator A(G, v);
              for (int t = A.beg(); !A.end(); t = A.nxt())
                K->insert(Edge(Gsc->ID(v), Gsc->ID(t)));
            }
          Ktc = new dagTC<DenseGRAPH, Graph>(*K);
        }
    ~TC() { delete K; delete Ktc; delete Gsc; }
    bool reachable(int v, int w)
        { return Ktc->reachable(Gsc->ID(v), Gsc->ID(w)); }
    } ;

Свойства случайных орграфов
E	Случайные ребра		Случайные из 10 соседей
E	v	e	v	e
1000 вершин
1000	983	981	916	755
2000	424	621	713	1039
5000	13	13	156	313
10000	1	1	8	17
20000	1	1	1	1
10000 вершин
50000	144	150	1324	150
100000	1	1	61	123
200000	1	1	1	1

Обозначения:
v	Количество вершин в коренном DAG
e	Количество ребер в коренном DAG

Упражнения

19.139. Приведите коренной DAG, вычисленный программой 19.13, и его транзитивное замыкание для орграфа

3-71-47-80-55-23-82-90-64-92-66-4.

19.141. Эмпирически оцените ожидаемый размер коренного DAG для различных видов орграфов (см. упражнения 19.11—19.18).

Перспективы

Трудоемкость операций обработки орграфов в худшем случае
Задача	Затраты	Алгоритм
Орграфы
Обнаружение циклов	E	DFS
Транзитивное замыкание	`V(E+V)`	DFS из каждой вершины
Кратчайшие пути из одного источника	E	DFS
Все кратчайшие пути	`V(E+V)`	DFS из каждой вершины
Сильные компоненты	E	Косарайю, Тарьяна или Габова
Транзитивное замыкание	`E+v(v+x)`	Коренной DAG
DAG-графы
Проверка на отсутствие циклов	E	DFS или очередь истоков
Топологическая сортировка	E	DFS или очередь истоков
Транзитивное замыкание	`V(E+V)`	DFS
Транзитивное замыкание	`V(E+X)`	DFS / динамическое программирование

Упражнения

19.145. Начертите дерево доминаторов орграфа

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6

19.147. Найдите транзитивное приведение орграфа

3-71-47-80-55-23-02-90-64-92-66-41-58-29-08-34-52-31-63-57-6

19.148. Найдите подграф графа

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6

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

19.150. Напишите эффективную функцию АТД для орграфов, которая вычисляет транзитивное приведение.

19.152. Найдите наибольший односвязный подграф в орграфе

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Глоссарий и правила игры

Анатомия DFS в орграфах

Достижимость и транзитивное замыкание

Отношения эквивалентности и частичные порядки

DAG -графы

Топологическая сортировка

Достижимость в DAG-графах

Сильные компоненты в орграфах

Еще раз о транзитивном замыкании

Перспективы

Глоссарий и правила игры

Анатомия DFS в орграфах

Достижимость и транзитивное замыкание

Отношения эквивалентности и частичные порядки

DAG -графы

Топологическая сортировка

Достижимость в DAG-графах

Сильные компоненты в орграфах

Еще раз о транзитивном замыкании

Перспективы

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!