Державне освітня установа
вищого професійної освіти
Уфімський державний авіаційний технічний університет
Курсова робота
по дискретних математики
на тему: Побудова матриці досяжності
Уфа 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...
