Я хотел бы знать, есть ли алгоритм, который вычисляет минимальное остовное дерево (оптимальное ветвление) в ориентированном графе с учетом набора корневых вершин между всеми этими корневыми вершинами, но не только одной корневой вершиной и всеми другими вершинами в графе .
Дан набор корневых вершин [1,4,6] и граф G, подобный изображенному на следующем рисунке:
... алгоритм должен вернуть что-то вроде зеленого подграфика на том же изображении.
Я бы хотел получить такой MST, который соединяет все корневые вершины, предоставленные алгоритму. Я склонен думать, что результатом потенциального алгоритма является подграф графа G, который содержит все корневые вершины и некоторые другие вершины из G.
Примечания:
- Я знаю, что для ориентированного графа нет MST, но есть Chu –Алгоритм Лю / Эдмондса.
- Я предполагаю, что результат такого алгоритма (если это действительно возможно) вернет оптимальное ветвление, которое включает некоторые вершины графа вместе со всеми корневыми вершинами.
