Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Мінімальна остовне дерево



План:


Введення

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


1. Приклад

Приклад мінімального остовного дерева в графі. Числа на ребрах позначають вага ребер.

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

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



2. Алгоритми

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

3. Споріднені завдання

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


Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Остовне дерево
Мінімальна поверхню
Мінімальна пара
Мінімальна нормальна підгрупа
PQ-дерево
Дерево
B-дерево
Ним (дерево)
Дерево Піфагора
© Усі права захищені
написати до нас
Рейтинг@Mail.ru