Page 91 - 4496

Рисунок 3.15 Граф з виокремленим кістяком

Якщо ребра графа зважені, то виникає завдання
виділення кістяка з мінімальною або максимальною оцінкою.

Семантика завдання. Припустимо, що вершинам графа
зіставлені полюси схеми, на які необхідно подати живлення, а
ребрам - дозволені зв'язки для ланцюга живлення. Тоді кожен
з кістяків буде визначати варіант ланцюга живлення.
Дійсно, ланцюгу співставляється граф без петель, що
включає всі вершини. Якщо ваги визначають відстань між
полюсами, то кістяку з мінімальною сумою ваг відповідає
розведення живлення з мінімальною сумарною довжиною
провідників. Таке завдання вирішується при трасуванні
друкованих плат.
Може бути запропоноване таке трактування завдання.
Вершини - абоненти, пов'язані лініями зв'язку, ваги на ребрах
- оцінка втрати конфіденційної інформації при її передачі по
цій лінії зв'язку. Тоді завданню виділення кістяка з
мінімальним добутком ваг, що входять у кістяк ребер,
відповідає завдання визначення найбільш надійної мережі для
передачі інформації.
Розглянемо два алгоритми розв'язку завдання:
«жадібний» алгоритм і алгоритм Прима.
«Жадібний алгоритм».

88