Государственное образовательное учреждение
высшего профессионального образования
Уфимский государственный авиационный технический университет
Курсовая работа
по Дискретной математике
на тему: Построение матрицы достижимости
Уфа 2006 г.
Введение
Цель работы:
Разработать программу на языке TURBOPASCAL, осуществляющую вычисление матрицы достижимости.
Постановка задачи:
Составить программу определения матрицы достижимости. Теоретически объяснить принцип вычисления матрицы достижимости. Представить текст программы с комментариями, а также показать ее схематически (в виде блок – схем). Проверить правильность работы программы, тем самым показать результаты тестирования. В итоге сделать выводы по проделанной работе.
Матрицы достижимости и связности
Пусть 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.
Текст программы (с комментариями)
PROGRAMG_r_a_p_h;
Uses CRT;
const MaxNodes = 5; { Количество вершин в графе }
type NodePtr = 1..MaxNodes;
Element = 0..1;
AdjMatrix = Array [NodePtr,NodePtr] of Element;
var Adj : AdjMatrix;
Внимание, отключите Adblock
Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!
Одними из наиболее популярных услуг на рынке IT-технологий являются создание и продвижение лендингов. Они способны положительно влиять на деятельность любого бизнес-проекта в интернете. Судя по многочисленным отзывам, заказавшие создание лендингов люди ни разу не пожалели о потраченных деньгах. Они вложили в будущее, которое неразрывно связано с интернетом. Всё больше и больше предпринимателей обращаются к услугам разных агентств, веб-студий, чтобы заказать создание лендинга у профессионалов.