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