Построение всех остовных деревьев графа

В ряде случаев возникает необходимость в построении полного списка остовных деревьев графа G. Например, в том случае, когда надо отобрать «наилучшее» дерево, а критерий, позволяющий осуществить такой отбор, является очень сложным (или даже частично субъективным), так что непосредственное решение задачи оптимизации (не использующее перечисление всех остовных деревьев) оказывается невыполнимым.

Число различных остовов полного связного неориентированного помеченного графа с n вершинами равно . Число различных остовов неориентированного графа без петель с n вершинами равно значению определителя , где B₀ - матрица инциденций с одной удаленной строкой (т.е. с n-1 независимыми строками), — транспонированная матрица к B₀.