Міністерство освіти і науки України

Сумський Державний Університет

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

з дисципліни

«Теорія алгоритмів та математична логіка»

На тему

«Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала»

Виконав студент

факультету ЕлІТ групи ІН-83

Горбатенко О. О.

Перевірив Кузіков Б. О.

Суми 2010

Завдання роботи

При виконанні ОДЗ необхідно реалізувати алгоритми Прима та Крускала побудови остового дерева у графі, та протестувати її на тестовому графі наведеному у завданнях до ОДЗ згідно вашого варіанту. У пояснювальній записці до ОДЗ повинно бути викладено наступне:

• Вступ. Короткі відомості про поняття остового дерева;

• Завдання роботи, Включаючи тестовий приклад графу, згідно варіанта;

• Алгоритм Прима:

◦ короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосіб представлення графу та його обґрунтування (10%);

◦ остове дерево, отримане за допомогою алгоритму (5%);

◦ фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу (10%);

◦ оцінку швидкодії реалізованого варіанта алгоритму (10%).

• Алгоритм Крускала:

◦ короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосіб представлення графу та його обґрунтування(10%);

◦ остове дерево, отримане за допомогою алгоритму (5%);

◦ фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу (10%);

◦ оцінку швидкодії реалізованого варіанта алгоритму (10%).

• Порівняння алгортимів, контрольні приклади:

◦ висновок що до умов, коли доцільно використовувати той чи інший алгоритм (10%)

◦ довільний граф (10 або більше вершин), на якому алгоритм Прима дає перевагу, навести фактичні параметри швидкодії (10%);

◦ довільний граф (10 або більше вершин), на якому алгоритм Крускала дає перевагу, навести фактичні параметри швидкодії (10%).

Поставлене завдання: маючи на вході граф G, одержати на виході його остовне дерево мінімальної вартості, використати алгоритми Крускала й Прима. Порівняти використовувані алгоритми.

Вступ

Нехай G = (V, Е) — зв'язний граф, у якому кожне ребро (u,v ) позначено числом c(u, v), що називається вартістю ребра. Остовним деревом графа G називається вільне дерево, що містить всі вершини V графа G. Вартість остовного дерева обчислюється як сума вартостей всіх ребер, що входять у це дерево.

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

Існують різні методи побудови остовних дерев мінімальної вартості. Багато хто з них ґрунтуються на наступній властивості остовних дерев мінімальної вартості. Нехай G = (V, Е) — зв'язний граф із заданою функцією вартості, що задана на множині ребер. Позначимо через U підмножину вершин V. Якщо (і, v) — таке ребро найменшої вартості, що й належить U і v належить V \ U, тоді для графа G існує остовное дерево мінімальної вартості, що містить ребро (і, v).

Існують два популярних алгоритми побудови остовного дерева мінімальної вартості для позначеного графа G = (V, Е), основані на описаній властивості: Прима й Крускала. ............