Аннотация:
Описывается алгоритм перечисления всех остовных деревьев (остовов) связного графа с конечным числом вершин. Приводятся результаты работы компьютерной программы, составленной по этому алгоритму.
Обсуждается также вопрос о перечислении всех триангуляций плоского графа.
Ключевые слова:связный граф, планарный граф, остовное дерево, число остовных деревьев,
триангуляция, число триангуляций, выпуклая оболочка.
Полный текст:
PDF файл (332 kB)