Как можно удалить вершину из ориентированного графа без потери существующих путей?

Question

Я хотел бы удалить вершину (назовите ее B) из ориентированного графа, не теряя существующие пути между всеми остальными вершинами. Это означает, что если есть путь от некоторого узла A к какому-то узлу C, который включает в себя B, B должен быть удален, но C все еще должен быть доступен из A.

Допустим, мне нужно удалить вершину B в любом графе, а A и C - это любые узлы, связанные с B на графе. Запуск такого алгоритма достаточен для достижения результата?

1) если есть путь A -> B -> C, удалите ссылку A -> B и B -> C и добавьте ссылку A -> C

2) если есть путь A <- B <- C, удалите ссылку A <- B и B <- C и добавьте ссылку A <- C </p>

3) если есть ссылка A -> B или B -> A (которая не имеет ссылки на C, изображенную в случаях 1 и 2), удалите A -> B или B -> A

Answer 1

Вы подходите хорошо. По сути, если вы найдете всех соседей узла B и соедините их друг с другом (в ориентированном графе в направлении, которое имеет смысл), то вы можете быть уверены, что ни один путь не был потерян, удалив B.

Если есть какие-либо требования, такие как «создать как можно меньше нового соединения, имея все доступные узлы, как это было до удаления» ->, тогда решение может быть более трудным, например, имитировать удаление узла B и использование dijsktra из каждого соседа. узел, чтобы узнать, какой узел был потерян, и создает только ребра для узлов, которые были потеряны в процессе.