Дерево Штейнера: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Дерево Штейнера''' (''Steiner tree'') - частичный связный граф в виде дерева миним...)
 
Нет описания правки
Строка 1: Строка 1:
'''Дерево  Штейнера''' (''Steiner tree'') -  
'''Дерево  Штейнера''' (''[[Steiner tree]]'') - [[частичный граф|частичный]] [[связный граф]] в виде [[дерево|дерева]] минимального веса, множество [[вершина|вершин]] которого содержит выделенное множество вершин исходного [[граф|графа]]. Нахождение дерева Штейнера составляет проблему Штейнера на графах; какие-либо эффективные алгоритмы, решающие ее, неизвестны.
частичный связный граф в виде дерева минимального веса, множество
вершин которого содержит выделенное множество вершин исходного графа.
Нахождение дерева Штейнера составляет проблему Штейнера на графах;
какие-либо эффективные алгоритмы, решающие ее, неизвестны.


См. ''Задача Штейнера на графах, Евклидова задача Штейнера''.
==См.==
''[[Задача Штейнера на графах]], [[Евклидова задача Штейнера]]''.
==Литература==
==Литература==
[Лекции],  
[Лекции],  


[Кристофидес]
[Кристофидес]

Версия от 17:39, 14 октября 2009

Дерево Штейнера (Steiner tree) - частичный связный граф в виде дерева минимального веса, множество вершин которого содержит выделенное множество вершин исходного графа. Нахождение дерева Штейнера составляет проблему Штейнера на графах; какие-либо эффективные алгоритмы, решающие ее, неизвестны.

См.

Задача Штейнера на графах, Евклидова задача Штейнера.

Литература

[Лекции],

[Кристофидес]