Практичне заняття 1. Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда (стр. 1 )

Практичне заняття 1

Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда.

е

Мета: 1.1 Ознайомитися з основними поняттями теорії графів.

1.2 Отримати практичні навики побудови матриці найкоротших відстаней.

Ключові положення

Метод. Керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.

, , Беркман зв¢язок. – К.: Техніка, 2003

Алгоритм Флойда

Цей алгоритм дає можливість найти найкоротший шлях між всіма парами вершин графа

3

Алгоритм:

1. Сформувати матрицю С,елементи якої

2. Приймемо k = 1 – номер ітерації

3. Для всіх i ¹ k, j ¹ k здійснити операцію = min[,(+)]

4. Якщо k=m, розрахунки закінчені, рішення знайдено. Якщо ні, перейти до шагу 4.

5. Приймемо k = k+1, перейти до шагу 2.

Практичне заняття 2

Задача побудови найкоротших радіальних маршрутів між вузлами мережі перевезень пошти

Мета: Розглянути приклад побудови найкоротших радіальних поштових маршрутів між вузлами мережі перевезення пошти

Ключові положення

Метод. Керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.

, , Беркман зв¢язок. – К.: Техніка, 2003

2 5

3

4 4 3

 

4 3 7

Заданий зв’язаний зважений граф, вершини якого відповідають вузлам мережі перевезень пошти, ребра – шляхам, що з’єднують ці вузли, а ваги ребер – протяжностям відповідних шляхів. Знайти найкоротші шляхи, що з’єднують задану початкову вершину з рештою вершин графа.

Початкова вершина визначається по останній цифрі номера в списку гр

упи

Алгоритм побудови рельєфа графа:

1. Створюється початковий рельєф графа. Початковій вершині присвоюється мінімальна вага, яка = 0, іншим вершинам графа присвоюється вага, яка = ¥.

2. З усіх неперевірених вершин, вибираєтся вершина с мінімальною вагою.

3. Перевіряємо зв’язки перевірочної вершини з усіма неперевіреними вершинами і розраховуємо нову вагу (розраховуємо наступним чином, до ваги перевірочної вершини додається вага розглянутого ребра і порівнюється з вагою не перевіреної вершини, якщо отримана сума менше попередньої ваги, то неперевіреній вершині присвоюється нова вага).

4. Після перевірки зв’язків перевіреної вершини з усіма неперевіреними вершинами, перевіреній вершині присвоюється мітка “перевірена” (*) і ця вершина виключається із подальшого розкладу.

5. Підрахуєм кількість вершин графа, які вже перевірені. Якщо таких вершин меньше n - 1 – здійснюється повернення на шаг 2, і процес формування рельєфа графа повторюється, якщо їх n - 1 – рельєф графа сформован і робота алгоритма закінчується.

Після закінчення роботи алгоритма необхідно сформувати найкоротший шлях між початковою вершиной і іншими вершинами графа.

Таблица 2.1 Таблица 2.2 Таблица 2.3

Шаг 0: начальный		Шаг 1: Рi = 0, Bi = 4		Шаг 2: Рi = 2, Bi = 3
Bi		*		Рi	Bk	Bi	*	Рi	Bk	Bi	*	Рi	Bk
1				999		1		4	4	1		3	3
2				999		2		999		2		999
3				999		3		2	4	3	*	2	4
4				0		4	*	0		4	*	0
5				999		5		999		5		999
6				999		6		4	4	6		4	4
7				999		7		3	4	7		3	4
8				999		8		999		8		999

Таблица 2.4 Таблица 2.5 Таблица 2.6