反馈顶点集

反馈顶点集（feedback vertex set）是从图中删除后使剩余图不含环的顶点集合。删除顶点时，其关联边也一起删除。无向图中剩余对象是森林；有向版本要求没有有向环，二者的环定义和算法不能混用。

两个三角形 $1-2-3-1$、$1-4-5-1$ 只共享顶点一。删去顶点一就同时破坏两个环，留下边 $23$ 与 $45$。原图有环，所以空集不可行，$\{1\}$ 因而是最小反馈顶点集。若先删顶点二，第二个三角形仍完整，说明删除数目与顶点位置同样重要。

共同顶点一次删除即可击中两个不同的环。

击中所有环与诱导森林

对有限无向简单图 $G=(V,E)$，$S\subseteq V$ 是反馈顶点集，当且仅当诱导子图 $G[V\setminus S]$ 不含环。等价地，$S$ 与原图每个简单环的顶点集合相交。证明：若有未被击中的环，它完整保留在剩余图；若剩余图含环，该环原来也存在且没有顶点在 $S$ 中。

这给出另一等价目标：寻找最大的诱导森林顶点集 $F$，再取 $S=V\setminus F$，最优大小满足 $min|S|=|V|-max|F|$。这里的“诱导”不能删除：在任意连通图中都能选生成树，但它通过删边获得，不能由此推出不必删除顶点。

反馈顶点集也可看作环顶点集合族的击中集，不过环的数量可能很大。树原本无环，反馈顶点集为空；这与要求每条边至少删一个端点的顶点覆盖不同，例如一条非空树边仍需被顶点覆盖。

小图的精确枚举

下面按删除数递增尝试所有顶点子集，用并查集检查保留边是否成环。输入 n 个顶点编号为 0,...,n-1 的无向简单图，边端点必须合法、无自环、无重复无向边；返回最小反馈顶点集，不改写输入。

Python 3

from itertools import combinations

def feedback_vertices_small(n, edges):
    edges = tuple(edges)
    if n < 0 or any(not (0 <= u < n and 0 <= v < n) or u == v
                     for u, v in edges):
        raise ValueError("invalid simple graph")
    if len({frozenset(e) for e in edges}) != len(edges):
        raise ValueError("duplicate undirected edge")
    def is_forest(removed):
        parent, size = list(range(n)), [1]*n
        def find(v):
            while parent[v] != v:
                v = parent[v]
            return v
        for u, v in edges:
            if u in removed or v in removed:
                continue
            a, b = find(u), find(v)
            if a == b:
                return False
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
        return True
    for count in range(n+1):
        for choice in combinations(range(n), count):
            removed = frozenset(choice)
            if is_forest(removed):
                return removed

edges = [(0,1),(1,2),(2,0),(0,3),(3,4),(4,0)]
assert feedback_vertices_small(5, edges) == frozenset({0})
assert feedback_vertices_small(3, [(0,1),(1,2)]) == frozenset()
assert feedback_vertices_small(0, []) == frozenset()
print(feedback_vertices_small(5, edges))

环检测的不变量是：已处理的保留边构成森林，且并查集的各组恰为它的连通分量。新边两端若已同组，原森林中已有一条连接路径，加边产生环；若不同组，合并它们不会产生环。所以判定器恰好识别森林。枚举按删除数递增，第一次可行前所有更小集合都已排除；全部删除总可行，故算法终止并最优。

按大小合并使查找树高度至多 ${\log }_{2}n$：一个元素的深度增加时，所在组大小至少翻倍。每个候选检测耗时 $O(n+m\log (n+1))$，至多 $2^n$ 个候选，总时间为 $O(2^n(n+m\log (n+1)))$；额外工作空间为 $O(n+m)$。这是小图核对方法，不是一般大图的高效求解器。

变式。 将两三角形改成顶点完全不相交的两个三角形。任意删除一个顶点至多破坏其中一个，所以至少删二；各删一顶点达到二。若改为只共享一条边，仍可删该边任一端点一次破坏两个环，但还应检查图中是否出现额外环；本例额外的四边环也经过这两个端点，故一次删除仍充分。

最小反馈顶点集问题一般计算困难，而仅检查某个给定集合是否可行可在线性图遍历时间内完成。给定答案与求出最优答案的代价不同。反馈边集改成删除边，在无向无权图中可以由生成森林直接求得，不能用本篇最小顶点数替代最小边数。