Page 90 - 4496

Розглянемо кроки побудови за цим методом на
прикладі дерева, наведеного на рис.3.14.
На першому кроці границею є корінь дерева, який
заміняється вершинами, пов'язаними з ним по вихідних дугах
– вершинами 2(12), 3(3), 4(4). Тут у дужках зведені ваги,
приписувані вершинам. Серед вершин границею вибирається
вершина 3, що має мінімальну вагу. Ця вершина не є листком,
вона видаляється із границі, а замість неї в границю вводяться
вершини 7, з вагою, рівною 12 (сума ваг вершини 3, рівною 3,
і дуги (3,7), рівноюї 9) і 8 з вагою 11.
Нова границя: 2(12), 7(12), 8(11), 4(4). На ній
вибирають вершину 4, яку замінюють вершинами 9,10 і 11,
що приводить до нової границі: 2(12), 7(12), 8(11), 9(11),
10(10), 11(7). Для продовження береться гілка, пов'язана з
вершиною 11. Вона видаляється із границі, і замість неї
вводяться пов'язані з нею по вихідних дугах вершини 18, 19,
20. Результатом буде нова границя з вершин 2(12), 7(12),
8(11), 9(11), 10(10), 18(11), 19(9), 20(10). Вибирається нова
гілка з мінімальною вагою – вершина 19, а вона є листком.
Розв'язок знайдений. Ним є шлях у вершину 19, вага розв'язку
рівна 9.

13.15.2. Пошук мінімального кістяка

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

87