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

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

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

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

1. 1-опор дерева, если он существует, является минимальным остовным деревом и может быть найден за время (с точки зрения сложности) для взвешенного графа, где . Более того, каждое допустимое взвешенное граф с 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. Для любого фиксированного рационального числа NP-полно определить, содержит ли взвешенный граф t-опор дерева, даже если все веса ребер являются положительными целыми числами. ${\displaystyle t>1}$
6. Опорный элемент дерева (или минимальный связующий элемент дерева) орграфа можно найти за линейное время.
7. Орграф содержит не более одного ключа дерева.
8. Ключ квазидерева взвешенного орграфа можно найти во времени. ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$

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

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

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

1. Цай, Лэйчжэнь; Корнейл, Дерек Г. (1995). «Деревянные ключи». SIAM Journal по дискретной математике . 8 (3): 359–387. дои : 10.1137/S0895480192237403.

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