РОЗДІЛ 2. ТЕОРЕТИЧНІ ОСНОВИ РОЗРОБКИ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ

2.1 Характеристика моделей і методів знаходження оптимальних покриваючих дерев

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

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

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