Опишите алгоритм, чтобы определить, возможны ли такие же времена обнаружения / окончания в новом прогоне DFS с новым фронтом

Question

Вам предоставляется ориентированный граф G = (V,E) и лес DFS с временем обнаружения / завершения каждой вершины после запуска DFS. Предположим, что новое ребро e теперь добавлено к G. С учетом того, что старое время обнаружения и окончания доступно на O(1), опишите эффективный алгоритм, чтобы определить, возможны ли такие же времена обнаружения / завершения в новом запуске DFS на G'=(V,E+e).

Во-первых, я думаю, что если e соединит 2 ранее не связанных компонента, то это будет невозможно, поскольку время обнаружения любой вершины в компоненте, обнаруженной после первой, будет позже, чем время окончания первый компонент, который больше не может иметь место.
Далее, я думаю, что если вершина u, в которую входит e, обнаруживается версией v, из которой e выходит, то время открытия / окончания sh некоторой вершины должен измениться. Не уверен, как это доказать, хотя. Поэтому я думаю, что v и u должны быть в одном и том же дереве, а это ud

Если это правильно, Я думаю, что вы можете проверить, существует ли вершина w, такая, что dw O(V) времени. Но у меня такое чувство, что я не на правильном пути.

Answer 1

Для простоты обращения к элементам, включенным в постановку задачи, давайте предположим, что ребро помечено как e, и что оно соединяет две вершины u и v. Я буду ссылаться на время открытия и окончания sh любой вершины w как w.d и w.f соответственно.

Существует четыре возможных случая синхронизации с точки зрения обнаружения и завершения sh раз u и v. Я считаю, что ответ будет ясен, если каждый такой случай будет рассмотрен отдельно.

Сначала давайте рассмотрим случай, когда u.d < v.d < v.f < u.f. Этот порядок может иметь место, если v является дочерним или косвенным потомком u в исходном графе G. В этом случае, в зависимости от того, как вы храните и перемещаетесь по структуре графа, добавление e может привести к тому же обнаружению и к финишу sh раз. Другими словами, DFS все еще может сначала использовать старые ребра, и в итоге получит такое же обнаружение / fini sh раз. e будет затем обрабатываться только как дополнительный обратный или передний фронт, который не влияет на результирующее обнаружение / фини sh раз.

Во втором случае u.d < u.f < v.d < v.f. В этой настройке после добавления e к исходному графику, так как u будет иметь v в качестве прямого потомка, из-за исчерпывающей стратегии первоочередной обработки потомков алгоритма DFS, v.d и v.f значения будут обновлены, чтобы неизбежно стать меньше, чем u.f. В этом случае невозможно сохранить начальные значения discovery / fini sh, и они будут изменены независимо от того, находятся ли они в одном подключенном компоненте.

Третий и четвертый случаи - это отражение первых двух, с u с и v с поменялись местами. (т. е. v.d < u.d < u.f < v.f и v.d < v.f < u.d < u.f) Вы можете расширить объяснение для первых двух случаев, чтобы охватить их.

После этого рассмотрения искомый алгоритм довольно тривиально построить. У вас есть открытие и финиш sh раз, доступные вам в O(1), и кажется, что вы также знаете вершины u и v, соединенные e. Вы можете просто проверить начальное обнаружение и конечное время sh для u и v. Если они соответствуют первому или третьему случаю, тогда обнаружение / окончание sh раз после добавления e может оставаться прежним. Если они соответствуют второму или четвертому случаю, то время непременно изменится после второго запуска DFS.

Поскольку вы выполняете постоянное количество проверок независимо от размера графика, алгоритм будет принимать O(1) время и использование O(1) дополнительное место.