Древовидный t-остовТерминология в русскоязычной литературе встречается редко и окончательно не установилась. Иногда остовом графа называется остовное дерево графа (). Здесь слово «древовидный остов» () используется в другом смысле. Под остовом в данной статье () понимается (разреженный) граф, в котором расстояния примерно равны расстояниям в плотном графе или другом метрическом пространстве. графа — это остовное поддерево графа , в котором расстояние между любой парой вершин не превосходит -кратного расстояния в графе .
Известные результаты Имеется несколько статей по теме древовидных остовов. Одну из них под заглавием Tree Spanners (Древовидные Остовы) написали математики Лейчжень Кай и Дерек Корнил, которые исследовали теоретические и алгоритмические проблемы, связанные с древовидными остовами. Некоторые из выводов этой статьи приведены ниже. Ниже везде обозначает число вершин графа, а является числом рёбер. Древовидный 1-остов, если существует, является наименьшим остовным деревом и может быть найден за время (в терминах сложности) для взвешенных графов, где . Более того, любой древовидный 1-остов взвешенного графа, если существует, содержит единственное минимальное остовное дерево. Древовидный 2-остов может быть построен за линейное время , а задача нахождения древовидного -остова является NP-полной для любого фиксированного целого . Сложность нахождения наименьшего древовидного остова в орграфе равна , где является функцией, обратной функции Аккермана. Наименьший древовидный 1-остов взвешенного графа может быть найден за время . Для любого фиксированного рационального числа определение, содержит ли взвешенный граф древовидный -остов, является NP-полной задачей, даже если все веса рёбер заданы как целые положительные числа. Орграф содержит максимум один древовидный остов. Квазидревовидный остов взвешенного орграфа может быть найден за время time.
См. также Геометрический остов
Примечания
Литература
Категория:Остовное дерево