Минимальное остовное дерево, какие кромки необходимы / не нужны

Question

В графе для каждого ребра, как вы определяете, присутствует ли он во всех минимальных остовных деревьях, или только в некоторых из них, или ни в одном из них?

Предположим, что есть < 1000 вершин и < 100000 ребер, и нам нужно классифицировать все ребра.

Answer 1

Мы можем сделать следующее, чтобы определить, появляется ли ребро в любом из MST или нет. Допустим, у нас есть неориентированный граф, мы можем определить, появляется ли ребро во всем минимальном остовном дереве (MST). Для каждого ребра сделайте следующее: пусть u и v будут двумя вершинами ребра e. Запустите стандартную DFS из u вдоль ребер, которые не тяжелее, чем e, чтобы увидеть, можем ли мы достичь v. Если мы можем достичь v, то в некотором MST не содержится e. Если мы не можем достичь v, то каждый MST содержит e. Это происходит потому, что ребро появляется во всех MST тогда и только тогда, когда ребро не является самым тяжелым ребром в любом цикле.