Реферати українською » Математика » Побудова матриці досяжності


Реферат Побудова матриці досяжності

Державне освітнє установа

вищого професійної освіти

>Уфимский державний авіаційний технічний університет

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

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

на задану тему: Побудова матриці досяжності

Уфа 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 довжиниk1.Столбец під номером 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)vw вершиниv,w належать однієї компонентісвязности;

3) нічого для будь-якого класу еквівалентностіV1псевдографG1, породжений безліччюV1, є компонентомсвязностипсевдографа G. Дляорграфа: Нехай1-отношение досяжності на безлічі V всіх вершин орієнтованогопсевдографа D. Нехай2-отношение двосторонньої досяжності на безлічі V. (>2=11-1). Тоді

1)1 - рефлексивно,транзитивно;

2)2 – еквівалентність на V;

3)v2w коли вершини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;

>UsesCRT;

>constMaxNodes = 5; { Кількість вершин в графі }

>typeNodePtr =1..MaxNodes;

>Element = 0..1;

>AdjMatrix =Array [>NodePtr,NodePtr] ofElement;

>varAdj :AdjMatrix; { Матрицясмежностей }

>Path:AdjMatrix; { Матриця досяжності }

>i,j :NodePtr;

>PROCEDUREP_r_o_d (>A,B:AdjMatrix;var З:AdjMatrix);

{ Матриця З отримує значеннябулевского }

{ твори матриць A і B }

>varVal :Element;

>i,j,k:Integer;

>BEGIN

>Fori:=1 toMaxNodesdo

>Forj:=1 toMaxNodesdobegin

>Val:=0;

>Fork:=1 toMaxNodesdo

>Val:=ValOR (>A[i,k]ANDB[k,j]);

>C[i,j]:=Val end

>END;

>PROCEDURET_r_a_n_s_C_l_o_s_e (>Adj:AdjMatrix;varPath:AdjMatrix);

{Вичислени матриці досяжностіPath по }

{ заданої матрицісмежностейAdj }

>vari,j,k :NodePtr;

>NewProd:AdjMatrix;

>AdjProd:AdjMatrix;BEGIN

>AdjProd:=Adj;Path:=Adj;

>Fori:=1 toMaxNodes-1dobegin

>P_r_o_d (>AdjProd,Adj,NewProd);

>Forj:=1 toMaxNodesdoFork:=1 toMaxNodesdo

>Path[j,k]:=Path[j,k]ORNewProd[j,k];

>AdjProd:=NewProd

end

>END;

>BEGIN

>clrscr;

{ Введення матрицісмежностей заданого графа }

>WriteLn ('>Вводите елементи матрицісмежностей по рядкам:');

>Fori:=1 toMaxNodesdo

>Forj:=1 toMaxNodesdobegin

>Write ('‚ЗапровадьтеAdj[',i,',',j, ']: ');ReadLn (>Adj[i,j]) end;

{Вичисление та виведення матриці досяжності }

>T_r_a_n_s_C_l_o_s_e (>Adj,Path);

>WriteLn ('Матриця досяжності: ');

>Fori:=1 toMaxNodesdobeginForj:=1 toMaxNodesdoifi=jthenPath[i,j]:=1; end;

>Fori:=1 toMaxNodesdobeginForj:=1 toMaxNodesdoWrite (>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


Укладання

У виконання курсової роботи було розроблено програму для обчислення матриці досяжності. Діяльність було вирішено всі поставлені маємо завдання: теоретичне пояснення принципу обчислення матриці досяжності; уявлення тексту програми з коментарями, і навіть уявлення його вигляді блок – схем; перевірка правильності роботи програми тобто уявлення результатів тестування.

Програма написана мовоюTURBOPASCAL, проте то, можливо легко переписана будь-якою з сучасних мов програмування, оскільки наведено досить прості алгоритми. Були максимально передбачені всіх можливих помилки, які можуть виникнути під час використання даної програми.


Список використаної літератури

1. Нефедов В.М., Осипова В.А. // Курс дискретної математики. // М.: МАІ, 1992.

2. КузнєцовО.П.,Адельсон-ВельскийГ.М. //Дискретная математика для інженера. // М.:Энергоатомиздат, 1988.

3. Кук Д.,Бейз Р. // Комп'ютерна математика. // М. Наука, 1990.

4. Бронштейн О.М. // Сила-силенна і функції. // Методичні вказівки. Уфа:УГАТУ. 1988.

5.Житников У. П. //Конспект лекцій з дискретної математиці. // Уфа:УГАТУ. 2007.

6. Павловська Т. А. Щупак Ю. А. // Підручник із практичному програмування (Бейсик, З, Паскаль). // Санкт-Петербург. 2005.


Схожі реферати:

Навігація