Как сказать, если край находится на некотором пути

Question

Учитывая неориентированный граф G = V, E, 2 вершины: х, у и ребро е,

Я хотел бы, чтобы проверить, есть ли путь от й к y, которое содержит заданное ребро e.

Что я думал: Решите это, определив сетевой поток, где x и y являются источником и потоком, и проверьте, является ли поток в e более чем 0, это означает, что существует путь. НО есть 2 проблемы:

1. я не знаю, как направить к краям
2. Что бы способность каждого ребра?

Так что я предполагаю, что это неправильный подход ... Если кто-то может дать представление, было бы здорово.

Answer 1

Один из подходов может быть следующее:

1. Удалить ребро е = (U, V) от E (G).
2. Если любой путь xy содержит e, то путь будет либо одной из двух следующих форм: (1) x * -> u -> v * -> y или (2) x * -> v -> u * -> y, где * -> означает достижимый. Используйте этот факт, чтобы проверить, действительно ли выполняется один из следующих случаев: 2.1. x достижима из u и y достижима с v. 2.2. x достижима из v, а y достижима из u. Мы можем использовать BFS для поиска достижимости.