Извлечение подграфа по узлам
Я пытаюсь найти подходы для извлечения подграфа на основе узлов. У нас есть большой граф (направленный или нет), и у нас есть список узлов, которые мы хотим извлечь из графов, но мы хотим извлечь также промежуточные узлы...
Когда мы смотрим на извлечение подграфа на основе 2 узлов, проблема очень проста... мы можем выбрать между извлечением всех промежуточных узлов во всех просто путях между этими 2 узлами или только промежуточных узлов из кратчайшего пути...
но что, если нужно извлечь более двух узлов... Как можно справиться с этой проблемой?
Я изо всех сил пытаюсь найти какие-либо публикации о такой проблеме... вероятно, потому что я не знаю, как ее точное название. (если это действительно появляется в проблемах теории графов)
1 ответ
Как прокомментировал Ян, вопрос не является конкретной целью.
Если вы хотите минимизировать вес дерева, то проблема называется обобщенным деревом Штейнера.
Если вам нужен любой тип связующего дерева между этими узлами, вы можете создать минимальное связующее дерево на графе с набором узлов, которые вы хотите соединить, и ребрами, которые соединяют каждую пару узлов с кратчайшим путем между ними. Это полный график, который дорого создавать. Я думаю, что можно ускорить его, распространяясь от каждого узла одновременно, и когда два "пузырька" касаются в первый раз, создают путь (один и тот же кратчайший) между этими двумя точками. Постепенно все узлы будут связаны. Вероятно, некоторые пути перекрываются, что может быть использовано для сокращения дерева.