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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

  1. Древесный 1-каркас, если существует, является наименьшим остовным деревом и может быть найден за время (в терминах сложности) для взвешенных графов, где . Более того, любой древесный 1-каркас взвешенного графа, если существует, содержит единственное минимальное остовное дерево.
  2. Древесный 2-каркас может быть построен за линейное время , а задача нахождения древесного -каркаса является NP-полной для любого фиксированного целого .
  3. Сложность нахождения наименьшего древесного каркаса в орграфе равна , где является функцией, обратной функции Аккермана.
  4. Наименьший древесный 1-каркас взвешенного графа может быть найден за время .
  5. Для любого фиксированного рационального числа определение, содержит ли взвешенный граф древесный 1-каркас, является NP-полной задачей, даже если все веса рёбер заданы как целые положительные числа.
  6. Орграф содержит максимум одни древесный каркас.
  7. Квазидревесный каркас взвешенного орграфа может быть найден за время time.

Примечания

[править | править код]
  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). — ISBN 978-3-540-41183-3. — doi:10.1007/3-540-40064-8_20.
  • Leizhen Cai, Derek G. Corneil. Tree Spanners. — 1995. — Т. 8, вып. 3. — С. 359–387. — doi:10.1137/S0895480192237403.