Текст программы (с комментариями)

 

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

Введите 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.