Повна проблема дерева Штейнера☆ Дано повний граф G=(V,E) із функцією довжини на E та правильною підмножиною R⊂V, проблема щоб знайти повне дерево Штейнера мінімальної довжини в G, яке є різновидом дерева Штейнера з усіма вершинами R як його листками.

Дано неорієнтований граф з невід’ємними вагами ребер і підмножиною вершин, які зазвичай називають терміналами, проблема дерева Штейнера в графах вимагає дерева мінімальної ваги, яке містить усі термінали (але може включати додаткові вершини) і мінімізує загальну вагу його ребер.

Проблема мінімального дерева Штейнера така: Знайдіть найкоротшу можливу мережу, що з’єднує набір точок на евклідовій площині. Якщо точки з'єднати безпосередньо одна з одною прямими відрізками, ми отримаємо мінімальне остовне дерево.

Вузлово-зважена проблема лісу Штейнера приймає як введіть неорієнтований граф із вартістю вузла та набором невпорядкованих пар {si,ti} вузлів. Мета полягає в тому, щоб знайти мережу з мінімальною вартістю, яка включає шлях між кожною заданою парою вузлів.

Дано граф G = (V,E) з коренем r ∈ V , додатними ємностями {c(e)|e ∈ E} та невід’ємними довжинами {`(e)|e ∈ E} мінімальна довжина Проблема дерева Штейнера з ємним (кореневим) ребром полягає в тому, щоб знайти дерево в G мінімальної загальної довжини з коренем у r, що охоплює дану підмножину T ⊂ V вершин і таке, що для кожного e ∈ E, …

Узагальнена проблема Штейнера (GSP) визначається наступним чином. Нам задано граф з невід’ємними вагами ребер і набором пар вершин. Алгоритм має побудувати підграф мінімальної ваги, щоб два вузли кожної пари з’єднувалися шляхом.