Ключ для дерева

Дерево . k spanner (или просто k -spanner ) графа - $G$ является связующим поддеревом $T$ из $G$ в котором расстояние между каждой парой вершин не более $k$ раз их расстояние в $G$.

результаты

На тему гаечных ключей написано несколько статей. Один из них назывался « Деревянные гаечные ключи». написанная математиками Лейженом Цаем и Дереком Корнейлом , в которой исследовались теоретические и алгоритмические проблемы, связанные с ключами деревьев. Некоторые выводы из этой статьи перечислены ниже. $n$ всегда количество вершин графа, а $m$ это его количество ребер.

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