У меня сильно связный граф. Я хочу удалить лезвие и проверить, остается ли он прочно связанным. Поскольку я беру N = Общее количество узлов в графе равным 10, и большинство графов, которые мне интересны, имеют более 25 ребер, его трудно проверить, используя одно за другим, удаляя ребро.
Как решить эту проблему ? Спасибо.
Если удаляемое ребро (u -> v), граф останется связанным, если вы сможете найти путь от u до v. Вы можете использовать любой алгоритм поиска пути, чтобы проверить это.
Другой вариант - каждый раз запускать алгоритм проверки подключения с нуля; на самом деле не имеет значения, как вы это делаете, потому что график очень маленький.
Для более крупного графа существуют специальные структуры данных, разработанные для решения этой проблемы. Это называется «Динамическое подключение»: https://en.wikipedia.org/wiki/Dynamic_connectivity
[EDIT: DFS быстрее, чем Dijkstra, просто проверяет подключение, спасибо Йоргену Фогу]
Если удаляемое ребро uv, проверьте (например, с помощью DFS), остался ли путь u -> ...-> v. Если так, то граф все еще сильно связан, если был раньше. Если нет, то это явно больше не сильно связано.
Идея состоит в том, что любой путь между двумя вершинами x и y, который ранее использовал ребро uv, можно отредактировать, чтобы использовать новый путь u -> ...-> v. Простая замена ребра uv этим новым путем может привести к тому, что некоторые вершины будут посещены более одного раза, но в этом случае путь содержит один или несколько направленных циклов, которые можно удалить, пока оставшийся путь не посетит каждую вершину не более одного раза.
