Как вычисляется количество остовных деревьев в неориентированном графе?

Количество остовных деревьев в неориентированном графе можно вычислить с помощью матричной теоремы о деревьях. ru.ruwiki.ru ru.wikipedia.org

Алгоритм: studfile.net

1. Для неориентированного графа строится матрица M={mij}, где диагональный элемент mii — число рёбер, имеющих вершину xi в качестве одной из концевых вершин, а элемент mij — число параллельных рёбер между вершинами xi и xj со знаком минус. studfile.net
2. Число всех остовных деревьев равно определителю подматрицы, получающейся вычёркиванием одной строки и одного столбца из матрицы M. studfile.net

Также для построения остовных деревьев можно использовать процедуры поиска, например в глубину (DFS-дерево) или ширину (BFS-дерево). old-vt.chuvsu.ru

С увеличением числа вершин число остовных деревьев растёт экспоненциально. old-vt.chuvsu.ru Например, полный граф с n вершинами имеет nn–2 остовных деревьев. old-vt.chuvsu.ru