Дерево Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево Штейнера''' (''Steiner tree'') - частичный связный граф в виде дерева миним...) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
'''Дерево Штейнера''' (''Steiner tree'') | '''Дерево Штейнера''' (''[[Steiner tree]]'') — [[частичный граф|частичный]] [[связный граф]] в виде [[дерево|дерева]] минимального веса, множество [[вершина|вершин]] которого содержит выделенное множество вершин исходного [[граф|графа]]. Нахождение дерева Штейнера составляет проблему Штейнера на графах; какие-либо эффективные алгоритмы, решающие ее, неизвестны. Приближенный подход к решению см. в статье [[Деревья Штейнера]]. | ||
частичный связный граф в виде дерева минимального веса, множество | |||
вершин которого содержит выделенное множество вершин исходного графа. | |||
Нахождение дерева Штейнера составляет проблему Штейнера на графах; | |||
какие-либо эффективные алгоритмы, решающие ее, неизвестны. | |||
См. ''Задача Штейнера на графах, Евклидова задача Штейнера'' | ==См. также== | ||
* ''[[Задача Штейнера на графах]],'' | |||
* ''[[Евклидова задача Штейнера]].'' | |||
==Литература== | ==Литература== | ||
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. | |||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
Текущая версия от 22:40, 1 июня 2016
Дерево Штейнера (Steiner tree) — частичный связный граф в виде дерева минимального веса, множество вершин которого содержит выделенное множество вершин исходного графа. Нахождение дерева Штейнера составляет проблему Штейнера на графах; какие-либо эффективные алгоритмы, решающие ее, неизвестны. Приближенный подход к решению см. в статье Деревья Штейнера.
См. также
Литература
- Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.