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

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




НазваПрактичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда
Сторінка1/8
Дата26.09.2012
Розмір0.82 Mb.
ТипДокументи
  1   2   3   4   5   6   7   8




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


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

е

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

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

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

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


Скляренко С.М., Стеклов В.К., Беркман Л.Н. Поштовий звязок. – К.: Техніка, 2003

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


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


3



Алгоритм:


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



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

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

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

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



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


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


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


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

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


Скляренко С.М., Стеклов В.К., Беркман Л.Н. Поштовий звязок. – К.: Техніка, 2003


2 5

3



4 4 3

1 1 3 3 6 2 8




4 2 4 1 4

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

Шаг 3: Рi = 3, Bi = 1




Шаг 4: Рi = 3, Bi = 7




Шаг 5: Рi = 4, Bi = 6

Bi

*

Рi

Bk

Bi

*

Рi

Bk

Bi

*

Рi

Bk

1

*

3

3

1

*

3

3

1

*

3

3

2




7

1

2




7

1

2




7

1

3

*

2

4

3

*

2

4

3

*

2

4

4

*

0




4

*

0




4

*

0




5




999




5




999




5




999




6




4

4

6




4

4

6

*

4

4

7




3

4

7

*

3

4

7

*

3

4

8




999




8




7

7

8




6

6

  1   2   3   4   5   6   7   8

Схожі:

Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconПрограмний комплекс аналізу властивостей та характеристик графів
Анотація. Розроблено та реалізовано програмний комплекс, який аналізує дані графової структури, синтезує графи із заданими характеристиками,...
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда icon“затверджую”
Планарні графи. Формула Ейлера для плоских графів. Критерій планарності графа (сформулювати). Розфарбування графів. Хроматичні числа....
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда icon“затверджую”
Планарні графи. Формула Ейлера для плоских графів. Критерій планарності графа (сформулювати). Розфарбування графів. Хроматичні числа....
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconЛекція 11 Алгоритми на графах Основні поняття теорії графів Способи зображення графа в оперативній пам'яті Задача визначення найкоротших шляхів у зваженому графі
Ребро (дуга) І будь-яка його (її) вершина називаються інцидентними. З'єднані ребром вершини називаються суміжними. Якщо вершина V...
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconФормат опису модуля
Основи математичної логіки. Основи теорії нечітких множин. Відношення та їх властивості. Види відношень. Основи комбінаторики та...
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconL-системи. Основні поняття тертл-графіки
Алгоритм, що дозволяє отримувати графічне представлення слова за допомогою тертл-графіки
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconГубка Менгера l-системи. Основні поняття тертл-графіки
Алгоритм, що дозволяє отримувати графічне представлення слова за допомогою тертл-графіки
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconМатематичні основи інформатики
Основи теорії чисел: прості числа, ділення із залишком, найбільший спільний дільник, взаємно прості числа. Основи алгебри: многочлени...
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconВступ до теорії ймовірностей. Основні поняття
В наш час методи теорії ймовірностей широко застосовуються в теорії надійності, теорії масового обслуговування, теорії інформації,...
Практичне заняття 1 Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда iconПерший змістовний модуль “артикуліція англійських голосних (монофтонгів)”
...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи