трусики женские украина

На головну

 Знаходження мінімального остовного дерева алгоритмом Краскала - Математика

Зміст

Введення

1. Постановка завдання

2. Методи вирішення даної проблеми

3. Опис алгоритму Краскала

4. Приклад роботи алгоритму Краскала

5. Код програми

6. Огляд роботи програми

Висновок

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

Введення

Мінімальним остовне деревом (МОД) зв'язкового зваженого графа називається його зв'язний підграф, що складається з усіх вершин вихідного дерева і деяких його ребер, причому сума ваг ребер максимально можлива. Якщо вихідний граф незв'язний, то описувану нижче процедуру можна застосовувати по черзі до кожної його компоненті зв'язності, отримуючи тим самим мінімальні остовне дерева для цих компонент.

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

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

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

· Алгоритм Прима;

· Алгоритм Краскала;

· Алгоритм Борувки.

1. Постановка завдання

Нехай є зв'язний неорієнтовані граф G, на ребрах якого задана вагова функція c (e). Зв'язний підграф графа G, що є деревом і містить всі його вершини, називають покриває деревом (spanning-tree) цього графа (іноді використовують термін кістяк або остов). Вагою остовного дерева будемо вважати суму ваг всіх його ребер. Тоді виникає задача про знаходження максимального покриває дерева, тобто такого, що його вага найбільший, або дорівнює вазі будь-якого з покривають дерев для даного графа. Будемо позначати найбільше покриває дерево графа G як MAX (G).

 2. Методи вирішення даної проблеми

Остовним деревом графа називається дерево, що містить всі вершміни V графа. Вартість остовного дерева обчислюється як сума вартостей всіх ребер.

Ідея рішення:

Для остовного дерева вірно наступне властивість:

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

На цій властивості заснований алгоритм Прима. У цьому алгоритмі будується безліч вершин U, з якого "виростає" кістяк. Нехай V = {1,2 ,. n}. Спочатку U = {1}. На кожному кроці алгоритму знаходиться ребро найменшої вартості (u, v) таке, що u з U і v з V \ U, потім вершина v переноситься з безлічі V \ U в безліч U. Процес продовжується до тих пір, поки безліч U не буде рівним безлічі V.

Деталі реалізації:

Зручно вибрати уявлення у вигляді списку дуг.

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

Визначимо поняття каркаса більш формально. Якщо дано зв'язний неорієнтовані граф G = (V, E), то каркас (також званий остовне або стягивающим деревом) T = (V, E '), де E'IE - це зв'язний граф без циклів. Іншими словами, каркас неорієнтованого графа G - це подграф графа G, дерево, що містить всі вершини графа. Зрозуміло, що для того, щоб T мало той же набір вершин, що і зв'язний граф G, і щоб T не мало циклів, воно повинно містити рівно | V | -1 ребро.

Припустимо, що для кожного ребра eIE існує вагу w (e), причому таку вагу може виражати, наприклад, ціну, довжину або час, необхідний для проходу по ребру (у нашому прикладі - довжину кабелю між будівлями). У зваженому графі вага подграфа - це сума ваг його ребер. Тоді каркас T максимального ваги - це каркас G, в якому вага дерева максимальний щодо всіх остовних дерев G.

Якщо граф G незв'язний, він не може мати остовного дерева, але у нього є остовное ліс. Також можна змінити алгоритм знаходження остовного дерева максимальної ваги, щоб на виході отримувати мінімальний остовное ліс.

кістяк алгоритм Краскала

В алгоритмі Краскала використовується жадібний підхід до вирішення завдання, тобто в будь-який момент виконання даних алгоритмів існує безліч ребер E ', що представляє підмножина деякого мінімального остовного дерева графа G. На кожному кроці алгоритмів з решти ребер вибирається "краще" ребро, що володіє певними властивостями, і додається до формованому каркасу максимального ваги. Одним з важливих властивостей будь-якого ребра, який додається до E ', є його безпека, тобто те, що оновлене безліч ребер E 'буде продовжувати представляти підмножина деякого мінімального остовного дерева.

 3. Опис алгоритму Краскала

Алгоритм Краскала може будувати дерево одночасно для декількох компонент зв'язності, які в процесі вирішення об'єднуються в одне пов'язане дерево.

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

Алгоритм складається з наступної послідовності дій:

1. Створюється список ребер R, що містить довжину ребра, номер вихідної вершини ребра (i), номер кінцевої вершини ребра (j), ознака включення даного ребра в дерево.

2. Даний список впорядковується в порядку зростання довжин ребер.

3. Проглядається список R і вибирається з нього ребро з максимальною довжиною, ще не включене в результуюче дерево і не утворює циклу з вже побудованими ребрами.

4. Якщо всі вершини включені в дерево і кількість ребер на одиницю менше кількості вершин, то алгоритм свою роботу закінчив. В іншому випадку здійснюється повернення до пункту 3.

Або в термінах теорії графів:

Дан граф з n вершинами; довжини ребер задані матрицею. Знайти кістяк максимальної довжини.

У задачі Прима-Краскала, що не здається особливо простий, жадібний алгоритм дає точне оптимальне рішення.

Як відомо (це легко довести по індукції), дерево з n вершинами має n-1 ребер. Виявляється, кожне ребро потрібно вибирати жадібно (лише б не виникали цикли). Тобто n-1 раз вибирати найкоротший ребро з ще не вибране ребро за умови, що воно не утворює циклу з вже обраними.

А як стежити, щоб нове ребро не утворювалися циклу зі старими? Зробити це просто. До побудови дерева забарвимо кожну вершину i у відмінний від інших колір i. При виборі чергового ребра, наприклад (i, j), де i і j мають різні кольори, вершина j і все, пофарбовані в її колір (тобто раніше з нею з'єднані) перефарбовуються в колір i. Таким чином, вибір вершин різного кольору забезпечує відсутність циклів. Після вибору n-1 ребер всі вершини отримують один колір.

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

Якщо до дерева додати ребро, то в дереві з'явиться цикл, що містить це ребро.

Дійсно, нехай додано ребро (u, v) - "додано" означає, що ребро - нове, що раніше його в дереві не було. Оскільки дерево є пов'язаною графом, то існує ланцюг C (u, ..., v) з декількох ребер, що з'єднує вершини u і v. Додавання ребра (u, v) замикає ланцюг, перетворюючи її в цикл.

Теорема. Алгоритм Прима-Краскала отримує максимальне кістяк.

Доказ. Результатом роботи алгоритму є набір з n-1 ребер. Вони не утворюють циклу, бо на кожному з n-1 кроків з'єднувалися вершини різного кольору, тобто раніше не зв'язані. Цей граф зв'язний, тому що після проведення 1-го ребра залишилося n-1 різних кольорів, ..., після проведення (n-1) - го ребра залишився один колір, тобто одна компонента зв'язності. Отже, отриманий набір ребер утворює зв'язний граф без циклів, що містить n-1 ребер і n вершин. Отже, граф є кістяк. Залишилося довести, що воно має мінімальну довжину. Нехай {,, ...,} ребра остовного дерева в тому порядку як їх вибирав алгоритм, т.е.?. Припустимо для простоти докази, що всі ребра мережі мають різну довжину, тобто

>> ...> (1)

Якщо отримане дерево не максимально, то існує інше дерево, задане набором з n-1 ребер {,, ...,}, таке що сума длінбольше суми довжин. З точністю до позначень

>> ...> (2)

Можливо =, = і т.д., але оскільки дерева різні, то в послідовностях (1) і (2) знайдеться місце, де ребра відрізняються. Нехай саме ліве таке місце - k, так, что?. Посколькувибіралось за алгоритмом найбільшим з що не утворюють циклу з ребрами ,, ... ,, то>. Тепер додамо до дерева (2) ребро. У ньому з'явиться цикл, що містить реброі, можливо, якісь (або всі) ребра ,, ... ,, але вони самі не утворюють циклу, тому в циклі буде обов'язково ребро d з набору, ... ,, причому d>. Викинемо з отриманого графа з одним циклом ребро d. Ми знову отримаємо дерево, але воно буде на d-коротше мінімального, що неможливо. Отримане протиріччя доводить теорему для мережі з усіма різними ребрами.

 4. Приклад роботи алгоритму Краскала

Малюнок 1. Початковий граф

Малюнок 2. Максимальна кістяк.

В алгоритмі Краскала ми не зберігаємо масив used [N]. Замість цього ми будемо на кожній ітерації алгоритму перевіряти, чи належать кінці розглянутого ребра до різних компонентів зв'язності (і додавати ребро до каркаса, якщо це так).

Введемо лічильник int counter = 0. Нехай N - кількість вершин графа.

Впорядкуємо список ребер по зростанню ваги.

Якщо counter == N - 1, закінчимо виконання алгоритму.

Проходячи по списку ребер, знайдемо ребро (i, j) таке, що i і j належать різним компонентам зв'язності. Так як список впорядкований по зростанню ваги ребер, ми будемо вибирати ребро з максимальною вагою, що задовольняє умові.

Додамо це ребро в каркас, збільшимо на одиницю лічильник counter.

Перейдемо до кроку 2.

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

 5. Код програми

// ---------------------------------------------

#include

#include

#include

// -------------------------------------------

typedef int * tint; // Покажчик на int

void main ()

{// Int max = 100; // Максимальна вага ребра

int n; // Кількість вершин

tint * G; // Вихідний граф

tint * H; // Матриця списку ребер з вагою

tint * K; / * Матриця, що відзначає приналежність

вершини компоненті * /

tint * T; // Матриця остовного дерева

tint * L; // Список ребер з цінами мінімального дерева

// ----- Введення графа

int max;

cout << "Maximalno dopustimoe zna4enie vesa rebra =";

cin >> max;

cout << "\ n Vvedite 4ilo vershin: \ n";

cin >> n;

G = new tint [n];

for (int i = 0; iG [i] = new int [n];

cout << "Vvedite nignij treugolnik matrici stoimosti: \ n";

for (int i = 1; ifor (int j = 0; jcin >> G [i] [j];

}

for (int i = 1; ifor (int j = 0; jG [j] [i] = G [i] [j];

// --- Виділення пам'яті для списку ребер ---

int kolreb = 0;

for (int i = 1; ifor (int j = 0; jif (G [i] [j] kolreb ++;

H = new tint [kolreb];

for (int i = 0; iH [i] = new int [3];

// -------------------------------------------

int a = 0;

for (int i = 1; ifor (int j = 0; jif (G [i] [j] H [a] [0] = i + 1;

H [a] [1] = j + 1;

H [a] [2] = G [i] [j];

a ++;

}

cout <// ---- Сортування ребер по зростанню ваги

int f, d, s;

for (int i = 0; ifor (int j = 0; jif (H [j] [2] f = H [j] [2];

H [j] [2] = H [j + 1] [2];

H [j + 1] [2] = f;

d = H [j] [0];

H [j] [0] = H [j + 1] [0];

H [j + 1] [0] = d;

s = H [j] [1];

H [j] [1] = H [j + 1] [1];

H [j + 1] [1] = s;

}

// Вивід ребер відсортованих по зростанню ваги

cout << "Matrica dostigimosni otsortirovannoe po ubivaniuy: \ n";

for (int i = 0; icout <";

cout <cout <cout << "";

}

for (int i = 0; iH [i] [0] - -;

H [i] [1] - -;

}

// Матриця для визначення компоненти

K = new tint [n];

for (int i = 0; iK [i] = new int [2];

for (int i = 0; iK [i] [0] = i;

K [i] [1] = 0;

}

// ---- Матриця остовного дерева

T = new tint [n];

for (int i = 0; iT [i] = new int [n];

for (int i = 0; ifor (int j = 0; jT [i] [j] = 0;

// -приєднання Першого ребра

T [H [0] [0]] [H [0] [1]] = H [0] [2];

T [H [0] [1]] [H [0] [0]] = H [0] [2];

K [H [0] [0]] [1] = 1;

K [H [0] [1]] [1] = 1;

// Алгоритми з'єднання ребер без створення циклу:

int m = 2; // Номер компоненти

for (int i = 1; iif (K [H [i] [0]] [1]! = K [H [i] [1]] [1])

// Якщо 2 вершини не з однієї компоненти

{

if (K [H [i] [0]] [1]> 0 && K [H [i] [1]] [1]> 0)

// Якщо обидві вершини належать різним компоненті

{

for (int j = 0; jif (K [H [i] [1]] [1] == K [j] [1])

K [j] [1] = K [H [i] [0]] [1];

K [H [i] [1]] [1] = K [H [i] [0]] [1];

T [H [i] [0]] [H [i] [1]] = H [i] [2];

T [H [i] [1]] [H [i] [0]] = H [i] [2];

}

if ((K [H [i] [0]] [1]> 0 && K [H [i] [1]] [1] == 0)

|| (K [H [i] [0]] [1] == 0 && K [H [i] [1]] [1]> 0))

// Якщо одна вершина має компоненту а ін. Немає

{

if (K [H [i] [0]] [1]! = 0)

K [H [i] [1]] [1] = K [H [i] [0]] [1];

if (K [H [i] [1]] [1]! = 0)

K [H [i] [0]] [1] = K [H [i] [1]] [1];

T [H [i] [0]] [H [i] [1]] = H [i] [2];

T [H [i] [1]] [H [i] [0]] = H [i] [2];

}

if (K [H [i] [0]] [1] == 0 && K [H [i] [1]] [1] == 0)

// Якщо обидві вершини не мали компоненти

{

K [H [i] [0]] [1] = m;

K [H [i] [1]] [1] = m;

T [H [i] [0]] [H [i] [1]] = H [i] [2];

T [H [i] [1]] [H [i] [0]] = H [i] [2];

m ++;

}

} // Кінець перевірки всіх ребер

// --- Виділення пам'яті для списку ребер

kolreb = 0;

for (int i = 1; ifor (int j = 0; jif (T [i] [j] kolreb ++;

L = new tint [kolreb];

for (int i = 0; iL [i] = new int [3];

// ------------------------------------------

// --- Висновок ребер

cout <a = 0;

for (int i = 1; ifor (int j = 0; jif (T [i] [j] L [a] [0] = i + 1;

L [a] [1] = j + 1;

L [a] [2] = T [i] [j];

a ++;

}

for (int i = 0; icout <";

cout <cout <}

int b = 0;

for (int i = 0; ib + = L [i] [2];

cout <4. Кузнєцов О.П., Адельсон-Бєльський Г.М. Дискретна математика для інженера. - М .: Вища школа, 1988.

5. http: // rain. ifmo.ru

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка