Деревний кістяк

Деревний 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))$.

Див. також

• Геометричний кістяк

Література

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