Что такое самое широкое дерево Штейнера (WST)

Question

Недавно я прочитал некоторые статьи об алгоритмах многоадресной маршрутизации. Например, Дерево кратчайшего пути (SPT), Дерево Штейнера (ST), Дерево самого короткого пути (WSPT) и так далее.Легко определить самый широкий путь, но меня смущает, что такое самое широкое дерево Штейнера (WSPT) и как мы определяем самое широкое дерево.

Answer 1

В настройке графа дерево Штейнера по отношению к набору терминальных вершин является подграфом, который (1) является деревом (2), соединяющим каждую пару терминальных вершин. самое широкое дерево Штейнера емкостного графа максимизирует минимальную ребристую емкость в дереве.