反馈边集

反馈边集（feedback edge set）是删除后使图不含环的边集合。对有限无向无权图，最小反馈边集的大小等于边数减去生成森林的边数，可以直接求出。它与删除顶点的反馈顶点集具有不同的最优值与计算结构。

以共享顶点一的两个三角形 $123$、$145$ 为例，共六条边、五个顶点且连通。每个三角形至少需要删一条边，且它们没有共边，因此至少删二；删去 $31,51$ 后留下四条边的生成树，达到下界。尽管一个顶点就能破坏两个环，单条边在此做不到。

反馈边集是保留森林的补集；每条虚线分别破坏一个三角形。

边数公式的上界与达界

设 $G=(V,E)$ 是有限无向图，$n=|V|$、$m=|E|$，连通分量数为 $c$，包括孤立顶点。反馈边集 $D\subseteq E$ 满足 $(V,E\setminus D)$ 为森林，等价于与原图每个环至少共享一条边。

在原图第 $i$ 个连通分量的 $n_i$ 个顶点上，保留森林最多有 $n_i-1$ 条边，故总保留边数至多 $n-c$。于是 $$|D|\ge m-(n-c)=m-n+c.$$ 每个原图分量各取一棵生成树，恰保留 $\sum _i(n_i-1)=n-c$ 条边，其余边形成反馈边集，达到该界。因此 $$min|D|=m-n+c.$$ 这也就是图拟阵的边数减秩。原图不连通时必须保留 $c$，不能一律写成 $m-n+1$。

逐边建立森林

可从空森林出发逐条查看边：两端在不同分量就保留并合并；两端已经连通就把该边列入删除集。这里选择哪条环边删掉会改变返回的集合，却不改变无权最小大小。

以下实现接受顶点 0,...,n-1 和带顺序的无向边列表，返回要删除的边索引，不改写输入。允许自环、平行边：自环自动拒绝，平行边至多保留一条；边以索引区分，不合并重复端点。

Python 3

def feedback_edges(n, edges):
    edges = tuple(edges)
    if n < 0 or any(not (0 <= u < n and 0 <= v < n)
                     for u, v in edges):
        raise ValueError("invalid vertex")
    parent, size = list(range(n)), [1]*n
    def find(v):
        while parent[v] != v:
            v = parent[v]
        return v
    removed = []
    for i, (u, v) in enumerate(edges):
        a, b = find(u), find(v)
        if a == b:
            removed.append(i)
            continue
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return removed

edges = [(0,1),(1,2),(2,0),(0,3),(3,4),(4,0)]
assert feedback_edges(5, edges) == [2, 5]
assert feedback_edges(2, [(0,1),(0,1),(1,1)]) == [1, 2]
assert feedback_edges(0, []) == []
print(feedback_edges(5, edges))

不变量是保留边始终为森林，且并查集恰描述其分量。每条被拒绝的边在拒绝时已有两端路径，此后合并不会破坏连通，所以最终原图每条边两端都处于同一保留分量。原图任意路径上的顶点因此仍被保留森林连通，最终分量数恰为 $c$，保留边数恰 $n-c$。结合已证下界，返回的删除集最优。这既证明可行，也证明达到正确边数。

按大小合并使树高为 $O(\log (n+1))$，所以时间为 $O(n+m\log (n+1))$，含边列表和返回索引的空间为 $O(n+m)$；流式处理输入时工作空间可降为 $O(n)$，但仍需存储返回结果。

变式。 在一棵三顶点树旁增加一个孤立顶点，$n=4,m=2,c=2$，公式给出零；若误用 $m-n+1$ 会得到负一。再增加一个自环，$m$ 加一而分量数不变，必须且只须删除该自环。

若边具有删除代价，则最小边数不再代表最小总代价。非负代价下，最小代价删除集的补集可取最大权生成森林；随意按输入顺序保留边不保证最大权。例如三角形边代价为一、二、一百时，应删代价一的边，而不是可能最后读到的代价一百边。有向图中则需击中所有有向环，生成森林边数公式也不再适用。