1. Постановка завдання

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

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

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

Розглянемо неорієнтований зв'язний граф: G = (V, Е, h), у якому V={v₁, v₂,..., v_n} – кінцева множина вершин, Е={e₁, e₂,…, e_m) – кінцева множина дуг, h – вагова функція дуг. Для математичної постановки завдання зручно позначити окремі значення вагової функції дуг: c_ij=h(e_k), де дуга відповідає впорядкованій парі вершин (v_i, v_j). Згідно змістовній постановці даного завдання окремі значення: c_ij=h(v_i, v_j) інтерпретуються як довжина, витрати або вартість ділянки (i, j) початкового графа.