Дерево Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево Штейнера''' (''Steiner tree'') - частичный связный граф в виде дерева миним...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Дерево Штейнера''' (''Steiner tree'') - | '''Дерево Штейнера''' (''[[Steiner tree]]'') - [[частичный граф|частичный]] [[связный граф]] в виде [[дерево|дерева]] минимального веса, множество [[вершина|вершин]] которого содержит выделенное множество вершин исходного [[граф|графа]]. Нахождение дерева Штейнера составляет проблему Штейнера на графах; какие-либо эффективные алгоритмы, решающие ее, неизвестны. | ||
частичный связный граф в виде дерева минимального веса, множество | |||
вершин которого содержит выделенное множество вершин исходного графа. | |||
Нахождение дерева Штейнера составляет проблему Штейнера на графах; | |||
какие-либо эффективные алгоритмы, решающие ее, неизвестны. | |||
См. ''Задача Штейнера на графах, Евклидова задача Штейнера''. | ==См.== | ||
''[[Задача Штейнера на графах]], [[Евклидова задача Штейнера]]''. | |||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||
[Кристофидес] | [Кристофидес] | ||
Версия от 17:39, 14 октября 2009
Дерево Штейнера (Steiner tree) - частичный связный граф в виде дерева минимального веса, множество вершин которого содержит выделенное множество вершин исходного графа. Нахождение дерева Штейнера составляет проблему Штейнера на графах; какие-либо эффективные алгоритмы, решающие ее, неизвестны.
См.
Задача Штейнера на графах, Евклидова задача Штейнера.
Литература
[Лекции],
[Кристофидес]