О
Определение
бобщенное дерево Штейнера
Задан граф G=(V,E), вершины которого разбиты на кластеры, а ребра имеют неотрицательные целые весаcij.
Проблема обобщенного дерева (TheGeneralizedSteinerTreeProblem–GSTP) формулируется двумя способами:
на графе G=(V,E) построить связное (но не обязательно каркасное) минимальное по стоимости дерево, содержащеепо крайней мере одну вершину из каждого кластера (проблемаL-GSTP).
на графе G=(V,E) построить связное (но не обязательно каркасное) минимальное по стоимости дерево, содержащееточно одну вершину из каждого кластера (проблемаE-GSTP).
Класс сложности
Проблемы L-GSTPиE-GSTPотносятся кNP-тяжелым.
1Термин «триангуляция» по-разному трактуется в вычислительной геометрии, геодезии, теории графов и других областях.