Точки сочленения и мосты на графике

Question

Сегодня я узнал о точках сочленения и мостах на графике (в основном неориентированный).

Текст где я прочитал (книга Стивенса-Халим) говорит

Когда мы находимся в вершине u и v является его соседом, а затем, если dfs_low(v) >= dfs_num(u) то u является разрезом вершина.

Принимая во внимание,

условие становится dfs_low(v) > dfs_num(u) при проверке мостов.

Но я не могу понять, почему равенство ушло от второго случая (в мостах). Пожалуйста, помогите мне с этим.

PS: dfs_num(i) номера вершин, как показано в dfs.

dfs_low(i) указывает наименьшую пронумерованную вершину, достижимую от i, отличную от ее родительской.

Answer 1

Предположим, что в рассматриваемой ситуации u является точкой сочленения, но u-v не является мостом. Тогда будет существовать путь от v до u, кроме как через ссылку u-v; следовательно, DFS, которая переходит от бикондексового компонента, содержащего u к содержащему v, в конечном итоге снова достигает u, обеспечивая равенство в dfs_low(v) >= dfs_num(u). (Большая часть неравенства возникает из-за того, что u является точкой сочленения, поэтому путь из v не может попасть в нижние нумерованные вершины без прохождения через u, а DFS не прослеживает такие пути.)

Но если uv также является мостом, другого пути между v и u не будет, чем через мост uv. Таким образом, DFS никогда не достигнет u снова; и все значения dfs_num после достижения значения DFS v будут строго больше dfs_num(u).