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

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


==См.==
==См. также==
''[[Задача Штейнера на графах]], [[Евклидова задача Штейнера]]''.
* ''[[Задача Штейнера на графах]],''
* ''[[Евклидова задача Штейнера]].''
==Литература==
==Литература==
[Лекции],  
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.


[Кристофидес]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Текущая версия от 22:40, 1 июня 2016

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

См. также

Литература

  • Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.