Древесный каркас

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

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

Имеется несколько статей по теме древесных каркасов. Одну из них под заглавием Tree Spanners (Древесные Каркасы)Шаблон:Sfn написали математики Лейчжень Кай и Дерек Корнил, которые исследовали теоретические и алгоритмические проблемы, связанные с древесными каркасами. Некоторые из выводов этой статьи приведены ниже. Ниже $n$ везде обозначает число вершин графа, а $m$ является числом рёбер.

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

См. также

• Геометрический остов

Литература

• Шаблон:Книга
• Шаблон:Статья