Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 19, Орграфы и ориентированные ациклические графы. Доказательство: Пусть даны булевы матрицы А и В размерности V на V, построим матрицу размерности ЗV на 3Vследующего вида:
|
|
|
| Доказательство: Пусть даны булевы матрицы А и В размерности V на V, построим матрицу размерности ЗV на 3Vследующего вида: |
Здесь 0 означает матрицу размерности V на V, все элементы которой равны 0, /означает тождественную матрицу размерностью V на V, все элементы которой равны О, за исключением элементов, стоящих на главной диагонали, которые равны 1. Теперь рассмотрим, как эту матрицу можно использовать в качестве матрицы смежности орграфа и вычислить его транзитивное замыкание посредством многократного возведения в квадрат. Для этого потребуется выполнить всего лишь одно действие:
Матрица в правой части этого уравнения есть транзитивное замыкание, поскольку последующие умножения дают эту же матрицу. В то же время в этой матрице содержится элемент А*В в ее верхнем правом углу. Какой бы алгоритм мы ни использовали для решения задачи получения транзитивного замыкания, мы можем применить его для решения задачи перемножения булевых матриц на том же уровне затрат (т.е. разница в затратах определяется некоторым постоянным множителем). ■
Важность значения этого свойства определяется убежденностью экспертов в том, что задача умножения булевых матриц относится к числу сложных: математики десятилетиями работают над тем, чтобы исследовать, насколько она трудна, и решение этой проблемы еще не найдено; наиболее известные результаты говорят в пользу того, что время выполнения умножения примерно пропорционально V25 (см. раздел ссылок). Теперь, если мы сможем найти решение задачи транзитивного замыкания с линейной зависимостью по времени (пропорциональное V2), то мы получим также и решение задачи перемножения булевых матриц с линейной временной зависимостью. Подобная зависимость между задачами известна как приведение (reduction); мы говорим, что задача перемножения булевых матриц сводится (reduces) к задаче транзитивного замыкания (см. раздел 21.6 и часть 8). В самом деле, приведенное выше доказательство показывает, что умножения булевых матриц сводится к нахождению в орграфе путей длиной 2.
Несмотря на проведение интенсивных исследований с участием многих математиков, ни один из них не смог предложить алгоритм умножения булевых матриц с линейной временной зависимостью, следовательно, и мы не сможем предложить простого алгоритма транзитивного замыкания с линейной временной зависимостью. С другой стороны, никому еще не удалось доказать, что такие алгоритмы не существуют, так что возможность появления такого алгоритма не исключается. Короче говоря, мы можем понимать свойство 19.9 в том смысле, что, отвергая возможность прорыва в исследованиях, мы не вправе ожидать, что в худшем случае время выполнения любого алгоритма транзитивного замыкания, какой только мы можем придумать, будет пропорционально V2. Однако вопреки этому заключению, мы можем разработать быстрые алгоритмы для некоторых
Часть 5. Алгоритмы но графах
специальных классов орграфов. Например, мы уже упоминали простой метод вычисления транзитивного замыкания, быстродействие которого для разреженных графов намного выше, чем у алгоритма Уоршалла.
Свойство 19.10. С помощью DFS мы можем поддерживать постоянное время ответа на запросы относительно абстрактного транзитивного замыкания орграфа, затрачивая пространство памяти, пропорциональное V2, и время, пропорциональное V(E+V), на предварительную обработку (вычисление транзитивного замыкания).
Доказательство: Как отмечалось в предыдущем разделе, поиск в глубину позволяет найти все вершины, достижимые из исходной, за время, пропорциональное Е, если мы используем представление графа в виде списков смежных вершин (свойство 19.5 и рис. 19.11). В силу этого обстоятельства, если мы выполняем поиск в глубину V раз, по одному разу на каждую вершину, используя ее как исходную, то мы можем вычислить набор вершин, достижимых из каждой вершины, т.е. транзитивное замыкание, за время, пропорциональное V(Е + V), Этот же аргумент справедлив для каждого обобщенного поиска (см. раздел 18.8 и упражнение 19.66). ■
Программа 19.4. Транзитивное замыкание, построенное на основе поиска в глубину
Класс DFS (поиска в глубину) реализует тот же интерфейс, что и программа 19.3. Она вычисляет транзитивное замыкание Т, запуская DFS в каждой вершине графа G, для вычисления набора узлов, достижимых из этой вершины. Каждое обращение к рекурсивной функции добавляет ребро, исходящее из начальной вершины, и генерирует рекурсивные вызовы с целью заполнения соответствующей строки в матрице транзитивного замыкания. Эта матрица используется также для маркирования посещенных вершин в процессе выполнения поиска в глубину, так что он требует, чтобы класс Graph поддерживал проверку edge на предмет существования ребра.
template < class Graph> class tc { Graph T; const Graph & G; void tcR(int v, int w)
{