Page 93 - 4496

2. Для вершин 5, 7, 3,2 розглядаємо ребра у вершини 1,
4, 6, 8.
За мінімальним ребром віднесемо до кістяка вершину 1.
2. Для вершин 5, 7, 3, 2, 1 по мінімальному вихідному з
них ребру виберемо вершину 4.
2. Для вершин кістяка 1, 2, 3, 4, 5, 7 по мінімальному
вихідному з них ребру виділимо вершину 6.
2. Для вершини 8 визначимо єднальне її ребро з
вершиною або 4, або 7, або 5.
Розв'язок побудований.

3.15.3 Дерева Штейнера

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

90