![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Достижимость и транзитивное замыкание
Чтобы получить эффективное решение задачи достижимости в орграфах, начнем с формулировки фундаментального определения. Определение 19.5. Транзитивное замыкание (transitive closure) орграфа есть орграф с теми же вершинами, но ребро из s в t в этом транзитивном замыкании возможно в том и только том случае, когда существует ориентированный путь из s в t в заданном орграфе. Другими словами, в транзитивном замыкании имеется ребро, исходящее из любой вершины в каждую вершину, достижимую из этой вершине в исходном орграфе. Вполне понятно, что транзитивное замыкание содержит в себе всю информацию, необходимую для решения задачи достижимости. На рис. 19. 13 предлагается к рассмотрению небольшой пример. Один из привлекательных способов понять транзитивное замыкание основан на представлениях орграфа в виде матрицы смежности и на следующей фундаментальной вычислительной задаче. Перемножение булевых матриц. Булевой матрицей (Boolean matrix) называется матрица, элементы которой принимают двоичные значения, т.е. 0 или 1. Пусть заданы булевы матрицы А и В. Вычислите произведение С двух заданных матриц, используя логические операции and (u) и or (или), соответственно, вместо арифме- РИСУНОК 19.13. ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ Рассматриваемый орграф (вверху) содержит восемь ориентированных ребер, но его транзитивное замыкание (внизу) показывает, что существуют ориентированные пути, соединяющие 19 из 30 пар вершин. Структурные свойства орграфа отражаются в его транзитивном замыкании. Например, строки 0, 1 и 2 матрицы смежности в транзитивном замыкания идентичны (равно как и столбцы О, 1 и 2), поскольку эти вершины содержатся в ориентированном цикле рассматриваемого орграфа. В матричной системе обозначений мы просто записываем эту операцию как С = А* В. Эта операция определена для матриц, состоящих из любых типов элементов, для которых определены операции 0, + и *. В частности, если а + b интерпретируется как логическая операция or, а операция а*Ь — как логическая операция and, то получается умножение булевых матриц. В языке C++ мы можем воспользоваться следующим вариантом: Глава 19. Орграфы и ориентированные ациклические графы 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 в том и только том случае, когда результат побитового выполнения операции and над строкой s матрицы А столбца t матрицы В имеет ненулевое значение. Теперь предположим, что А - это матрица смежности орграфа А, и мы используем приведенный выше программный код для вычисления С = А*А = А2 (простая замена в программном коде обозначения В на А). Если рассматривать этот программный код применительно к матрицам смежности, то сразу становится ясно, что он вычисляет: для каждой пары вершин s и t мы помещаем в С ребро, ведущее из s и t, в том и только том случае, когда имеется такая вершина i, для которой в А существует как путь из s и i, так и путь из i и t Другими словами, ориентированные ребра в А2 в точности соответствуют ориентированным путям длиной 2 в А. Если при этом мы учтем петли в каждой вершине графа А, то в А2 появятся ребра графа А, иначе их там не будет. Эта зависимость между умножением булевых матриц и путей в орграфе показана на рис. 19.14. Она немедленно приводит нас к элегантному методу вычисления транзитивного замыкания любого орграфа. Свойство 19.6. Транзитивное замыкание орграфа можно вычислить путем построения матрицы смежности А этого графа, добавления петли каждой вершины и вычисления Ау. Доказательство: В соответствии с аргументацией предыдущего параграфа, А3 содержит ребро для каждого пути орграфа длиной меньшего или равного 3, в матрице А 4 содержится каждый путь орграфа, длина которого меньше или равна 4 и т.д. У нас нет необходимости рассматривать пути, длина которых больше V, в силу принципа " картотечного ящика": любой такой путь хотя бы один раз должен повторно пройти через одну из вершин (поскольку в графе всего V вершин), поэтому он не добавляет какую-то новую информацию в транзитивное замыкание, поскольку обе вершины, связанные таким путем, соединены также ориентированным путем, длина которого меньше V (который можно получить за счет удаления цикла из пути в повторно посещенную вершину). ■
РИСУНОК 19.14.
|