Я пытаюсь понять алгоритм, который находит края среза для графика.Вырезанное ребро - это ребро, которое делит связанный граф на несвязный граф, и ни одно из ребер, лежащих в цикле, не может быть отрезанным ребром.
Возможно, я понимаю алгоритм, но не уверен, как написать доказательство правильности.Я даю ссылку ниже, а также прилагаю изображение алгоритма для справки.
Используемый алгоритм выглядит следующим образом:
G - это граф со списком смежности g.visited массив заботится о том, посетили ли мы узел или нет.low - это массив, который отслеживает самый низкий идентификатор, который может быть достигнут из определенного узла.Массив bridges хранит все мосты.
function dfs(at, parent, bridges):
visited[at]=true
id=id+1
low[at]=ids[at]=id
for(to: g[at]):
if(to==parent) continue;
if(!visited[to]):
dfs(to,at,bridges)
low[at]=min(low[at],low[to])
if(ids[at]<low[to]
bridges(at,to)
else
// if we reach here means
// there is a cycle, so we just compare the id of the
// `to` and the `low` of `at`.
low[at]=min(low[at],ids[to])
Одна вещь, которую я заметил в своем исследовании в Интернете, состоит в том, что большинство алгоритмов графов доказано с использованием противоречия.Если я подхожу к своей проблеме аналогичным образом, я могу сказать: «Давайте предположим, что алгоритм не дает вам острых углов».Я не уверен, как мне доказать, что мое предположение неверно, учитывая алгоритм, упомянутый в видео. Алгоритм
https://youtu.be/aZXi1unBdJA