Аннотация:Александра обобщила алгоритм проверки корневых деревьев на изоморфизм до произвольных деревьев и доказала его линейность. Следовательно, для любых классов графов, где количество занумерованных деревьев зависит от числа вершин полиномиально, существует эффективный алгоритм перечисления неизоморфных остовных деревьев. Это и было продемонстрировано в курсовой работе Измайловой.
В качестве исследуемого класса были выбраны графы с фиксированным цикломатическим числом γ. Для них существует не более n^γ занумерованных остовных деревьев. Измайлова А.А. показала, что алгоритм перечисления неизоморфных остовных деревьев имеет сложность O(n^(2γ+1)).