Государственноеобразовательное учреждение
высшегопрофессионального образования
Уфимскийгосударственный авиационный технический университет
Курсовая работа
по Дискретнойматематике
на тему:Построение матрицы достижимости
Уфа 2006 г.
Введение
Цель работы:
Разработать программу наязыке 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.
Текст программы (скомментариями)
PROGRAM G_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; { Матрица смежностей }
Path:AdjMatrix; { Матрица достижимости }
i,j: NodePtr;
PROCEDUREP_r_o_d (A,B: AdjMatrix; var C: AdjMatrix);
{ Матрица Cполучает значение булевского }
{ произведения матриц A иB }
var Val:Element;
i,j,k:Integer;
BEGIN
For i:=1 toMaxNodes do
For j:=1 toMaxNodes do begin
Val:=0;
For k:=1 toMaxNodes do
Val:=Val OR(A[i,k] AND B[k,j]);
C[i,j]:=Val end
END;
PROCEDURET_r_a_n_s_C_l_o_s_e (Adj: AdjMatrix; var Path: AdjMatrix);
{ Вычислени матрицыдостижимости Path по }
{ заданной матрицысмежностей Adj }
var i,j,k: NodePtr;
NewProd:AdjMatrix;
AdjProd:AdjMatrix; BEGIN
AdjProd:=Adj;Path:=Adj;
For i:=1 toMaxNodes-1 do begin
P_r_o_d(AdjProd,Adj,NewProd);
For j:=1 toMaxNodes do For k:=1 to MaxNodes do
Path[j,k]:=Path[j,k]OR NewProd[j,k];
AdjProd:=NewProd
end
END;
BEGIN
clrscr;
{ Ввод матрицы смежностейзаданного графа }
WriteLn ('Вводитеэлементы матрицы смежностей по строкам:');
For i:=1 toMaxNodes do
For j:=1 toMaxNodes do begin
Write ('‚Введите Adj[',i,',',j, ']: '); ReadLn(Adj[i,j]) end;
{ Вычисление и выводматрицы достижимости }
T_r_a_n_s_C_l_o_s_e(Adj,Path);
WriteLn ('Матрица достижимости: ');
For i:=1 toMaxNodes do begin For j:=1 to MaxNodes do if i=j then Path[i,j]:=1; end;
For i:=1 toMaxNodes do begin For j:=1 to MaxNodes do Write (Path[i,j],' '); WriteLn end;
readkey;
END.
Блок – схемы программы
/>
/>
Подпрограмма, где матрицаС получает значение булевского произведения матриц А и В.
/>
Подпрограмма длявычисления матрицы достижимости Pathпо заданной матрицы смежности Adj.
/>
Результаты тестированияпрограммы
Тест 1
Вводите элементы матрицысмежностей по строкам:
Введите Adj[1,1]: 0
Введите Adj[1,2]: 0
Введите Adj[1,3]: 1
Введите Adj[1,4]: 0
Введите Adj[1,5]: 0
Введите Adj[2,1]: 0
Введите Adj[2,2]: 0
Введите Adj[2,3]: 0
Введите Adj[2,4]: 0
Введите Adj[2,5]: 0
Введите Adj[3,1]: 0
Введите Adj[3,2]: 1
Введите Adj[3,3]: 0
Введите Adj[3,4]: 1
Введите Adj[3,5]: 1
Введите Adj[4,1]: 0
Введите Adj[4,2]: 1
Введите Adj[4,3]: 0
Введите Adj[4,4]: 0
Введите Adj[4,5]: 0
Введите Adj[5,1]: 1
Введите Adj[5,2]: 0
Введите Adj[5,3]: 0
Введите Adj[5,4]: 1
Введите Adj[5,5]: 0
Матрица достижимости:
1 1 1 1 1
0 1 0 0 0
1 1 1 1 1
0 1 0 1 0
1 1 1 1 1
Тест 2
Вводите элементы матрицысмежностей по стро-кам:
Введите Adj[1,1]: 0
Введите Adj[1,2]: 1
Введите Adj[1,3]: 0
Введите Adj[1,4]: 1
Введите Adj[1,5]: 0
Введите Adj[2,1]: 0
Введите Adj[2,2]: 0
Введите Adj[2,3]: 0
Введите Adj[2,4]: 0
Введите Adj[2,5]: 0
Введите Adj[3,1]: 1
Введите Adj[3,2]: 1
Введите Adj[3,3]: 0
Введите Adj[3,4]: 0
Введите Adj[3,5]: 0
Введите Adj[4,1]: 0
Введите Adj[4,2]: 0
Введите Adj[4,3]: 1
Введите Adj[4,4]: 0
Введите Adj[4,5]: 0
Введите Adj[5,1]: 1
Введите Adj[5,2]: 0
Введите Adj[5,3]: 0
Введите Adj[5,4]: 1
Введите Adj[5,5]: 0
Матрица достижимости:
1 1 1 1 0
0 1 0 0 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 1
Заключение
В результате выполнениякурсовой работы была разработана программа для вычисления матрицы достижимости. В работе были решены все поставленные переднами задачи: теоретическоеобъяснение принципа вычисления матрицы достижимости; представление текстапрограммы с комментариями, а также представления ее в виде блок – схем; проверкаправильности работы программы то есть представление результатов тестирования.
Программа написана наязыке TURBO PASCAL, однако может быть легко переписана на любой изсовременных языков программирования, так как приведены довольно простые алгоритмы.Были максимально предусмотрены все возможные ошибки, которые могут возникнутьпри использовании данной программы.
Список использованнойлитературы
1. Нефедов В.Н., Осипова В.А. // Курс дискретной математики. //М.: МАИ, 1992.
2. Кузнецов О.П., Адельсон-Вельский Г.М. // Дискретнаяматематика для инженера. // М.: Энергоатомиздат, 1988.
3. Кук Д., Бейз Г. // Компьютерная математика. // М. Наука,1990.
4. Бронштейн Е.М. // Множества и функции. // Методическиеуказания. Уфа: УГАТУ. 1988.
5. Житников В. П. // Конспект лекции по дискретной математике.// Уфа: УГАТУ. 2007.
6. Павловская Т. А. Щупак Ю. А. // Учебникпо практическому программированию (Бейсик, С, Паскаль). // Санкт-Петербург.2005.