Нахождение, если граф все еще сильно связан после удаления ребра

Question

Сильно связанный орграф - это ориентированный граф, в котором для каждых двух вершин ? и ? существует направленный путь от ? до ? и прямой путь от ? к ?.Пусть ? = (?, ?) - сильно связный орграф, а ? = (?, ?) ∈ ? - ребро в графе.Разработайте эффективный алгоритм, который решает, является ли граф without ′ = (?, ? ∖ {?}) графом без ребра strongly сильно связным.Объясните его правильность и проанализируйте время его выполнения.

Итак, я выполнил BFS и суммировал метки, один раз на исходном графике из ?, а затем снова в G 'без ребра (снова из ?), а затем: если вторая сумма (в G ') <исходная сумма (в G), то график не сильно связан. </p>

PS это вопрос моего экзамена, который я получил только 3/13 баллов, и я'мне интересно, если я должен подать апелляцию ..

Answer 1

Как указывает Sneftel, метки расстояния могут только увеличиваться.Если u больше не имеет пути к v, то я думаю, что метка v будет бесконечной, поэтому сумма меток изменится с конечной на бесконечную.Тем не менее, сумма может увеличиться без потери сильной связи графа, например,

u<----->v
 \     /|
  \|  /
    w

, где метка v увеличивается с 1 до 2 из-за косвенного пути через w.

Answer 2

Поскольку граф G сильно связан, G ' сильно связан тогда и только тогда, когда существует путь от u до v (этот путь заменит ребро e ).

Вы можете использовать любой алгоритм поиска пути для решения этой проблемы.