Гаечный ключ для дерева

K - остов дерева (или просто k -остов ) графа — это остовное поддерево , в котором расстояние между каждой парой вершин не превышает их расстояния в . ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

Известные результаты

Существует несколько статей, посвященных остовам деревьев. Одна из них называлась Tree Spanners ^{[1] и} была написана математиками Лэйчжэнем Каем и Дереком Корнелем , в ней исследовались теоретические и алгоритмические проблемы, связанные с остовами деревьев. Некоторые выводы из этой статьи перечислены ниже. — всегда число вершин графа, — число его ребер. ${\displaystyle n}$ ${\displaystyle m}$

1. Одноостовное дерево, если оно существует, является минимальным остовным деревом и может быть найдено за время (с точки зрения сложности) для взвешенного графа, где . Более того, каждое допустимое взвешенное графовое дерево содержит уникальное минимальное остовное дерево. ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ ${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leq m/n\right\}}$
2. 2-остов дерева может быть построен за время, и задача построения остова дерева является NP-полной для любого фиксированного целого числа . ${\displaystyle {\mathcal {O}}(m+n)}$ ${\displaystyle t}$ ${\displaystyle t>3}$
3. Сложность нахождения минимального остова дерева в орграфе равна , где — функциональная обратная функция функции Аккермана ${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}$ ${\displaystyle \alpha (m+n,n)}$
4. Минимальный 1-остов взвешенного графа может быть найден за время. ${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))}$
5. Для любого фиксированного рационального числа задача определения, содержит ли взвешенный граф t-остов дерева, является NP-полной, даже если все веса ребер являются положительными целыми числами. ${\displaystyle t>1}$
6. Древовидный остов (или минимальный древовидный остов) орграфа может быть найден за линейное время.
7. Орграф содержит не более одного остова дерева.
8. Квазидерево-остов взвешенного орграфа может быть найдено со временем. ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$

Смотрите также

• Графический гаечный ключ
• Геометрический гаечный ключ

Ссылки

1. Cai, Leizhen; Corneil, Derek G. (1995). «Tree Spanners». Журнал SIAM по дискретной математике . 8 (3): 359–387. doi :10.1137/S0895480192237403.

• Хандке, Дагмар; Кортсарц, Гай (2000), «Деревья-остовы для подграфов и связанных с ними проблем покрытия деревьев», Графовые концепции в информатике: 26-й международный семинар, WG 2000 Констанц, Германия, 15–17 июня 2000 г., Труды , Lecture Notes in Computer Science, т. 1928, стр. 206–217, doi :10.1007/3-540-40064-8_20, ISBN 978-3-540-41183-3.