6.7: Остовні дерева

Last updated

Oct 27, 2022
Save as PDF
- 6.6: Гамільтонові схеми та проблема комівояжера
- 6.8: Вправа

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$gt52.svg$ Компанія вимагає надійного підключення до Інтернету та телефону між п'ятьма офісами (названими A, B, C, D та E для простоти) у Нью-Йорку, тому вони вирішують орендувати виділені лінії від телефонної компанії. Телефонна компанія стягуватиме плату за кожне зроблене посилання. Витрати, в тисячах доларів на рік, наведені на графіку.

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

Остовне дерево

Остовне дерево - це зв'язаний граф, який використовує всі вершини, в яких відсутні схеми.

Іншими словами, існує шлях від будь-якої вершини до будь-якої іншої вершини, але ніяких ланцюгів.

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

$gt53.svg$

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

Звичайно, будь-яке випадкове остовне дерево насправді не те, що ми хочемо. Ми хочемо мінімальну вартість охоплюючого дерева (MCST).

Мінімальна вартість охоплюючого дерева (MCST)

Мінімальна вартість остовного дерева - це остовне дерево з найменшою загальною вагою краю.

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

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

Виберіть найдешевшу невикористану ребро на графіку.
Повторіть крок 1, додавши найдешевший невикористаний край, якщо тільки:
1. додавання краю створить схему
Повторюйте, поки не утвориться остовне дерево

Приклад 22

$gt54.svg$ Використовуючи наш графік телефонної лінії зверху, почніть додавати ребра:

\ (\ begin {масив} {lll}\ mathrm {AB} &\ $4 &\\ mathrm {OK}\\ mathrm {AE} &\ $5 &\ mathrm {OK}
\\ текст {BE} &\ $\ текст {6} &\ текст {відхили-замикає ланцюг ABEA}\\ текст {DC} &\ $7 &\ текст {OK}\\ текст {AC} &\ $8 &\ text {OK}\ end {масив}\)

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

Примітно, що алгоритм Крускала є оптимальним і ефективним; ми гарантовано завжди створюємо оптимальний MCST.

Приклад 23

Енергетичній компанії необхідно прокласти оновлені розподільні лінії, що з'єднують десять міст Орегону нижче до електромережі. Як вони можуть мінімізувати кількість нової лінії, яку потрібно прокласти?

\ (\ begin {масив} {|c|c|c|c|c|c|c|c|c|c|c|c|}
\ hline & & & & & & & &\\
text {Ешленд} &\ текст {Асторія} &\ текст {Вигин} &\ текст {Корвалліс} &\ текст {Озеро Кратер} &\ текст {Євген}\ текст {Ньюпорт} amp;\ текст {Портленд} &\ текст {Салем} &\ текст {Приморський}\
\ hline\ текст {Ешленд} &\ _ & 374 & 200 & 223 & 108 & 252 & 285 & 240 & 356\
\ hline\ текст {Асторія} & 374 &\ _ & 255 & 166 & 433 & 199 & 135 & 95 & 136 & 17\\
\ hline\ текст {згин} & 200 & 255 &\ _ & 128 & 277 & 128 & 180 & 131 & 247\ 247\
\ hline\ текст {Корвалліс} & 223 & 166 & 128 &\ _ & 430 & 47 & 52 & 84 & 40 & 155\
\ hline\ текст {Озеро Кратер} & 108 & 433 & 277 & 430 &\ _ & 453 & 478 & 344 & 423\\ hline
\ текст {Євген} & 178 & 199 & 128 & 47 & 453 & 91 & 110 & 64 & 181\\
\ hline\ текст {Ньюпорт} & 252 & 135 & 180 & 52 & 478 & 91 &\ _ & 114 & 83 & 117
\\\ hline\ текст {Портленд} & 285 & 95 & 160 & 84 & 110 & 114 &\ _ & 47 & 78\\
\ hline\ текст {Салем} & 240 & 136 & 131 & 40 & 389 & 64 & 83 & 47 &\ _ & 118\\
\ hline\ текст {Приморський} & 356 & 17 & 247 & 155 & 423 & 181 & 117 & 78 & 118 &\ _\\
\\ hline
\ кінець {масив}\)

Рішення

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

$gt55.svg$ $\begin{array}{ll} \text{Seaside to Astoria} & 17 \text{ miles} \\ \text{Corvallis to Salem} & 40 \text{ miles} \\ \text{Portland to Salem} & 47 \text{ miles} \\ \text{Corvallis to Eugene} & 47 \text{ miles} \\ \text{Corvallis to Newport} & 52 \text{ miles} \\ \text{Salem to Eugene} & \text{reject – closes circuit} \\ \text{Portland to Seaside} & 78 \text{ miles} \end{array}$

Графік до цієї точки показаний праворуч.

Продовжуючи,

$gt56.svg$ $\begin{array}{ll} \text{Newport to Salem} & \text{reject} \\ \text{Corvallis to Portland} & \text{reject} \\ \text{Eugene to Newport} & \text{reject} \\ \text{Portland to Astoria} & \text{reject} \\ \text{Ashland to Crater Lk} & 108\text{ miles} \\ \text{Eugene to Portland} & \text{reject} \\ \text{Newport to Portland} & \text{reject} \\ \text{Newport to Seaside} & \text{reject} \\ \text{Salem to Seaside} & \text{reject} \\ \text{Bend to Eugene} & 128\text{ miles} \\ \text{Bend to Salem} & \text{reject} \\ \text{Astoria to Newport} & \text{reject} \\ \text{Salem to Astoria} & \text{reject} \\ \text{Corvallis to Seaside} & \text{reject} \\ \text{Portland to Bend} & \text{reject} \\ \text{Astoria to Corvallis} & \text{reject} \\ \text{Eugene to Ashland} & 178\text{ miles} \end{array}$

Це пов'язує графік. Загальна довжина кабелю для прокладки становила б 695 миль.

Спробуйте зараз 7

Знайдіть мінімальну вартість охоплюючого дерева на графіку нижче за допомогою алгоритму Kruskal.

$gt57.svg$

Відповідь

$gt60.svg$ AB: Додати, вартість 11

БГ: Додати, вартість 13

AE: Додати, вартість 14

А.Г.: Пропустити, створив би схему ABGA

EF: Додати, вартість 16

EC: Додати, вартість 17

На цьому остовне дерево закінчено.