(v_i, v_j), входе в шукане покриваюче дерево мінімальної вартості, і x_ij = 0, в противному випадку, тобто якщо ребро (v_i, v_j) не входить в оптимальне покриваюче дерево. Відмітимо, що кількість даних булевих змінних рівно m, де m – кількість ребер початкового графа.

Тоді в загальному випадку математична постановка завдання про мінімальне покриваюче дерево в графі може бути сформульована таким чином:

де множина допустимих альтернатив формується наступною системою обмежень типу рівності і нерівностей:

Відмітимо, що ті змінні x_ij, для яких вагова функція ребер h не визначена або рівна 0, взагалі не входять в математичну постановку даного завдання (2.2) —(2.3). При цьому перших обмеженнях (2.3) виконання першого з відмічених раніше властивостей в шуканому покриваючому дереві не повинно бути ізольованої вершини. Четверте обмеження вимагає виконання другої з відмічених раніше властивостей, тобто шукане покриваюче дерево повинне містити рівно n - 1 ребер. Постановка завдання про максимальне покриваюче дерево в графі. У виразі цільової функції (2.2) операцію відшукання мінімуму необхідно замінити операцією відшукання максимуму, то може бути одержана