Построение матрицы достижимости

Понятие матрицы достижимости и связности. Операция удаления вершины из графа. Алгоритм выделения компонент сильной связности. Разработка и листинг программы на языке Turbo Pascal, осуществляющей вычисление матрицы достижимости по заданному алгоритму.
Краткое сожержание материала:

Государственное образовательное учреждение

высшего профессионального образования

Уфимский государственный авиационный технический университет

Курсовая работа

по Дискретной математике

на тему: Построение матрицы достижимости

Уфа 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;

PROCEDURE P_r_o_d (A,B: AdjMatrix; var C: AdjMatrix);

{ Матрица C получает значение булевского }

{ произведения матриц A и B }

var Val : Element;

i,j,k: Integer;

BEGIN

For i:=1 to MaxNodes do

For j:=1 to MaxNodes do begin

Val:=0;

For k:=1 to MaxNodes do

Val:=Val OR (A[i,k] AND B[k,j]);

C[i,j]:=Val end

END;

PROCEDURE T_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 to MaxNodes-1 do begin

P_r_o_d (AdjProd,Adj,NewProd);

For j:=1 to MaxNodes 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 to MaxNodes do

For j:=1 to MaxNodes 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 to MaxNodes do begin For j:=1 to MaxNodes do if i=j then Path[i,j]:=1; end;

For i:=1 to MaxNodes 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