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

А дерево k-гаечный ключ (или просто k-гаечный ключ) из график ${displaystyle G}$ это охватывающее поддерево ${displaystyle T}$ из ${displaystyle G}$ в котором расстояние между каждой парой вершин не превышает ${displaystyle k}$ раз их расстояние в ${displaystyle G}$.

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

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

1. Дерево с одним гаечным ключом, если оно существует, является минимальным остовным деревом и может быть найдено в ${displaystyle {mathcal {O}} (mlog eta (m, n))}$ время (по сложности) для взвешенного графа, где ${displaystyle eta (m, n) = min left {imid log ^ {i} nleq m / night}}$. Кроме того, любой допустимый взвешенный граф с одним остовным деревом содержит единственное минимальное остовное дерево.
2. Дерево с двумя ключами можно построить в ${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. Для любого фиксированного рационального числа ${displaystyle t> 1}$, это NP-полный, чтобы определить, содержит ли взвешенный граф дерево t-образный ключ, даже если все веса ребер являются положительными целыми числами.
6. Древовидный ключ (или минимальный древовидный ключ) орграфа можно найти за линейное время.
7. Орграф содержит не более одного гаечного ключа дерева.
8. Квазидревесный гаечный ключ взвешенного орграфа можно найти в ${displaystyle {mathcal {O}} (mlog eta (m, n))}$ время.

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

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

Рекомендации

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