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

Деревний k-кістяк (або просто k-кістяк) графа ${\displaystyle G}$ — кістякове піддерево ${\displaystyle T}$ графа ${\displaystyle G}$, в якому відстань між будь-якою парою вершин не перевищує ${\displaystyle k}$-разової відстані між ними у графі ${\displaystyle G}$.

Відомі результати

Є кілька статей на тему деревних кістяків. Одну з них під назвою Tree Spanners (Деревні кістяки) написали математики Лейчжень Кай і ^[en], які досліджували теоретичні та алгоритмічні проблеми, пов'язані з деревними кістяками. Деякі висновки цієї статті наведено нижче. Тут ${\displaystyle n}$ скрізь позначає число вершин графа, а ${\displaystyle m}$ — число ребер.

1. Деревний 1-кістяк, якщо існує, є найменшим кістяковим деревом і для зважених графів його можна знайти за час ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ (у термінах складності), де ${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leqslant m/n\right\}}$. Більш того, будь-який деревний 1-кістяк зваженого графа, якщо існує, містить єдине мінімальне кістякове дерево.
2. Деревний 2-кістяк можна побудувати за лінійний час ${\displaystyle {\mathcal {O}}(m+n)}$, а задача знаходження деревного ${\displaystyle t}$-кістяка є NP-повною для будь-якого фіксованого цілого ${\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}$ визначення, чи містить зважений граф деревний 1-кістяк, є NP-повною задачею, навіть якщо всі ваги ребер задано як цілі додатні числа.
6. Орграф містить максимум один деревний кістяк.
7. Квазідеревний кістяк зваженого орграфа можна знайти за час ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$.

Див. також

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

Примітки

1. Термінологія в українськомовній літературі зустрічається рідко і не встановилася. Іноді кістяком графа називають кістякове дерево графа (англ. spanning tree). Тут вислів «деревний кістяк» (англ. tree spanner) має інший сенс. Під кістяком у цій статті (англ. spanner) розуміють (розріджений) граф, у якому відстані приблизно дорівнюють відстаням у щільному графі або іншому метричному просторі. Кістяк графа називають також кістяковим графом, а k-кістяк називають у цьому випадку k-кістяковим графом.
2. Cai, Corneil, 1995, с. 359–387.

Література

• Dagmar Handke, Guy Kortsarz. Tree spanners for subgraphs and related tree covering problems // Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings. — 2000. — Т. 1928. — С. 206–217. — (Lecture Notes in Computer Science) — . — DOI:10.1007/3-540-40064-8_20.
• Leizhen Cai, Derek G. Corneil. Tree Spanners // SIAM Journal on Discrete Mathematics. — 1995. — Т. 8, вип. 3 (19 червня). — С. 359–387. — DOI:10.1137/S0895480192237403.