Связующее дерево
-
Определение и свойства остовных деревьев
- Остовное дерево — это дерево, которое соединяет все вершины графа.
- Остовное дерево является минимальным деревом, содержащим все вершины графа.
- Остовное дерево может быть найдено за линейное время, если граф связный.
-
Примеры и вычисления
- Остовные деревья существуют для деревьев, циклов и двудольных графов.
- Для n-мерного гиперкуба число остовных деревьев вычисляется по формуле.
- В общем случае число остовных деревьев может быть вычислено с помощью теоремы Кирхгофа.
-
Рекуррентность удаления-сокращения
- Число остовных деревьев удовлетворяет рекуррентности удаления-сокращения.
- При сжатии графа необходимо учитывать соединения вершин несколькими ребрами.
-
Многочлен Татта и его применение
- Многочлен Татта графа представляет собой сумму по остовным деревьям.
- Его значение при (1,1) равно числу остовных деревьев.
- Вычислительная сложность точного вычисления многочлена Татта высока.
-
Алгоритмы построения и оптимизации
- Существуют алгоритмы для построения остовных деревьев в глубину и в ширину.
- Изучены задачи оптимизации для остовных деревьев, включая минимальное остовное дерево и другие.
-
Рандомизация и перечисление
- Существуют алгоритмы для генерации однородных и случайных минимальных остовных деревьев.
- Перечисление всех остовных деревьев невозможно за полиномиальное время.
-
Бесконечные графы и аксиома выбора
- Для бесконечных связных графов существование остовного дерева эквивалентно аксиоме выбора.
- Лемма Цорна требует наличия максимального элемента в частичном порядке бесконечных деревьев.
Полный текст статьи: