Алгоритм выделения компонент сильной связности
12 Введение
Цель работы: Разработать программу на языке TURBO PASCAL, осуществляющую вычисление матрицы достижимости. Постановка задачи: Составить программу определения матрицы достижимости. Теоретически объяснить принцип вычисления матрицы достижимости. Представить текст программы с комментариями, а также показать ее схематически (в виде блок – схем). Проверить правильность работы программы, тем самым показать результаты тестирования. В итоге сделать выводы по проделанной работе. Матрицы достижимости и связности
Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v1,…, vn}. Обозначим через Ak=[a(k)ij] k-ю степень матрицы смежности A(D). Утверждение. Элемент a(k)ij матрицы Ak ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из vi в vj. Доказательство: Для k=1 очевидно в силу построения матрицы A(D). Пусть это справедливо для n=k-1. Т.е. в матрице Ak-1 в i-той строке на l-том месте стоит число, означающее кол-во маршрутов из vi в vl длины k−1. Столбец под номером j матрицы A содержит числа, означающие кол-во дуг (ребер) из vl в vj (l-номер строки). Тогда скалярное произведение i-той строки матрицы Ak-1 на j-тый столбец матрицы A равен сумме произведений. Каждое произведение означает кол-во путей из vi в vj, проходящих через vl на предпоследнем шаге. В сумме получается общее кол-во. Утверждение. Для того, чтобы n-вершинный орграф D с матрицей смежности A=A(D) имел хотя бы один контур, ó чтобы матрица K=A2+A3+… An имела ненулевые диагональные элементы (следствие предыдущего). Пусть ρ-отношение достижимости на множестве V всех вершин (неориентированного) графа G. (либо v=w, либо существует маршрут, соединяющий v и w). Тогда 1) ρ-отношение эквивалентности; 2) vρw ó вершины v,w принадлежат одной компоненте связности; 3) для любого класса эквивалентности V1 псевдограф G1, порожденный множеством V1, является компонентой связности псевдографа G. Для орграфа: Пусть 1-отношение достижимости на множестве V всех вершин ориентированного псевдографа D. Пусть ρ2-отношение двусторонней достижимости на множестве V. (ρ2=ρ1∩ρ1-1). Тогда 1) ρ1 - рефлексивно, транзитивно; 2) ρ2 – эквивалентность на V; 3) vρ2w ó когда вершины v,w принадлежат одной компоненте сильной связности; 4) для любого класса эквивалентности V1 ориент. псевдограф D1, порожденный множеством V1, является компонентой связности ор. псевдографа G. Число компонент связности орграфа D обозначается P(D). (для неор. - P(G). Определение. Под операцией удаления вершины из графа (орграфа) будем понимать операцию, заключающуюся в удалении некоторой вершины вместе с с инцидентными ей ребрами (дугами). Определение. Вершина графа, удаление которой увеличивает число компонент связности, называется точкой сочленения.
Утверждение. Если D' – орграф, полученный в результате удаления нескольких вершин из орграфа D, то A(D') получается из A(D) в результате удаления строк и столбцов, соответствующих удаленным вершинам. (Для неор. графа то же самое). Определение. Матрицей достижимости орграфа D называется квадратная матрица T(D)=[tij] порядка n, элементы которой равны - tij=1, если vj достижима из vi, - tij=0, в противном случае. Определение. Матрицей сильной связности орграфа D называется квадратная матрица S(D)=[sij] порядка n, элементы которой равны - sij=1, если vj достижима из vi и vi достижима из vj, - sij=0, в противном случае. Определение. Матрицей связности графа G называется квадратная матрица S(G)=[sij] порядка n, элементы которой равны - sij=1, если существует маршрут, соединяющий vj и vi , - sij=0, в противном случае.
Утверждение
Пусть G=(V,X) – граф, V={v1,…, vn}, A(G) – его матрица смежности. Тогда S(G)=sign[E+A+A2+A3+… An-1] (E- единичная матрица порядка n). (Следует из предыдущего).
Алгоритм выделения компонент сильной связности
1. Присваиваем p=1, S1=S(D). 2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp. 3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- кол-во компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу Sp+1, присваиваем p:=p+1 и переходим к п. 2.
12
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (355)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |