Требования к алгоритму
Работа рассчитана на 2 часа. При этом все новые программы составляются на базе подпрограмм лабораторной работы №2.1. Достижимые множества для вершин ориентированного графа определяются по тем же алгоритмам, что и для неориентированных графов. Исключение касается только несимметричности как исходной матрицы смежности, так всех производных результатов от операций над ней.
Для выявления связности ориентированного графа роме достижимых множеств, необходимо вычислять также контрадостижимые множества, или множества обратных достижимостей. По этой же причине кроме матрицы достижимостей (достижимостей в направлении ориентации дуг) потребуется ввести в рассмотрение и матрицу контрадостижимостей (достижимостей в противоположном направлении).
Контрадостижимое множество Qk (xi) - это множество таких вершин xj ориентированного графа, для которых достижима вершина xi (имеется хотя бы один путь в направлении от xj к xi):
Q (xi) = { xi } È G -1 (xi) È (G -1) 2 (xi) È…È (G-1) k (xi).
Для упрощения вычислений этих множеств воспользуемся следующим их свойством. Поскольку ребро эквивалентно двум взаимно направленным дугам, в неориентированном графе множества прямых и обратных достижимостей совпадают. В то же время, транспонирование матрицы смежности ориентированного графа дает граф с обратной ориентацией тех же самых дуг. Тогда множества ограниченных контрадостижимостей { Qk (xi) | xi Î X } первого графа совпадут с множествами ограниченных достижимостей { Rk (xi) | xi Î X } другого и наоборот. Поэтому матрицу контрадостижимостей рациональнее вычислять по следующей формуле:
Q =(R (AT)) T, где
AT -транспонированая матрица смежности исходного графа;
(R (AT)) T -транспонированая матрица достижимостей графа, имеющего транспонированную матрицу смежности исходного графа.
Для выявления сильных компонент следует поэлементно перемножить матрицу достижимостей и контрадостижимостей: R & Q. Полученную матрицу нужно привести к блочно-диагональному виду по следующему алгоритму, учитывая, что она состоит из нескольких подмножеств непересекающихся одинаковых строк и столбцов:
· собрать по группам все одинаковые строки, т.е. строки исходной матрицы переписать в промежуточную в порядке их совпадения. Затем так же выполнить для других строк. При этом в некотором промежуточном массиве следует запоминать номера переносимых строк первой матрицы. Этот массив содержит подстановку t изоморфного преобразования графов.
· в исходную матрицу собрать по группам все одинаковые столбцы, просто переписывая их из промежуточной матрицы в порядке их перечисления в подстановке t.
Все требования к структуре данных, указанные в руководстве предыдущей лабораторной работы, сохраняются и для данной работы.
Требования к результатам
Матрицы смежности ориентированных графов являются в общем случае несимметричными. Поэтому и все промежуточные матрицы, как правило, сохраняют это свойство. Исключение составляет матрица сильных компонент, которая по определению содержит информацию только о взаимной достижимости всех вершин из каждой компоненты. Эти особенности следует учесть при анализе отображаемых на экране промежуточных результатов.
После определения матрицы достижимостей на k +1 шаге по клавише “Enter” в качестве нулевого шага определения матрицы контрадостижимостей следует отобразить в верхней половине экрана матрицы A и AT, как это показано на рис. 2.3, а.
(а)(б)
Рис. 2.3. а) Нулевой шаг определения контрадостижимости и б) Окончательный результат определения связных компонент.
Первый и последующие шаги вычисления матриц ограниченных контрадостижимостей оформляются на экране аналогично сценарию определения матриц достижимостей.
После k -го шага (k уже известно после вычисления достижимостей) имеем матрицу достижимостей и матрицу контрадостижимостей. Их следует отобразить в верхней части экрана. Внизу рекомендуется отобразить матрицу R & Q, её блочно-диагональный вид t (R & Q) и вектор-столбец подстановки t (см. рис.2.3, б).
Методические указания
Необходимые методические указания даны в предыдущей лабораторной работе №2.1 и в описании алгоритма к данной работе. Задачи транспонирования и поэлементной конъюнкции матриц не должны вызывать трудности. Дополнительно об ориентированном аналоге связности - достижимости говорится в разделе 2.1.
 |
В качестве тестового графа рекомендуется следующий (см. рис. 2.4):
Рис. 2.4. Ориентированный граф для исследования свойств достижимости.
После отладки на этом тестовом графе в программу следует включить генератор ориентированных графов для исследования свойств достижимости и сильных компонент уже на примере произвольных ориентированных графов. В этом варианте программы в качестве результата следует отображать исходную матрицу смежности, матрицы достижимостей и контрадостижимостей, а также матрицу сильных компонент с вектором подстановки t. Программа должна работать по бесконечному циклу с выдачей следующего варианта по клавише “Пробел”. Выход из программы сделать по “Esc”.