Деревний k-кістякТермінологія в українськомовній літературі зустрічається рідко і не встановилася. Іноді кістяком графа називають кістякове дерево графа (). Тут вислів «деревний кістяк» () має інший сенс. Під кістяком у цій статті () розуміють (розріджений) граф, у якому відстані приблизно дорівнюють відстаням у щільному графі або іншому метричному просторі. Кістяк графа називають також кістяковим графом, а k-кістяк називають у цьому випадку k-кістяковим графом. (або просто k-кістяк) графа — кістякове піддерево графа , в якому відстань між будь-якою парою вершин не перевищує -разової відстані між ними у графі .
Відомі результати Є кілька статей на тему деревних кістяків. Одну з них під назвою Tree Spanners (Деревні кістяки) написали математики Лейчжень Кай і , які досліджували теоретичні та алгоритмічні проблеми, пов'язані з деревними кістяками. Деякі висновки цієї статті наведено нижче. Тут скрізь позначає число вершин графа, а — число ребер.
Деревний 1-кістяк, якщо існує, є найменшим кістяковим деревом і для зважених графів його можна знайти за час (у термінах складності), де . Більш того, будь-який деревний 1-кістяк зваженого графа, якщо існує, містить єдине мінімальне кістякове дерево. Деревний 2-кістяк можна побудувати за лінійний час , а задача знаходження деревного -кістяка є NP-повною для будь-якого фіксованого цілого . Складність знаходження найменшого деревного кістяка в орграфі дорівнює , де — функція, обернена до функції Акермана. Найменший деревний 1-кістяк зваженого графа можна знайти за час . Для будь-якого фіксованого раціонального числа визначення, чи містить зважений граф деревний 1-кістяк, є NP-повною задачею, навіть якщо всі ваги ребер задано як цілі додатні числа. Орграф містить максимум один деревний кістяк. Квазідеревний кістяк зваженого орграфа можна знайти за час .
Див. також Геометричний кістяк
Примітки
Література