删除边以消除两个节点之间除一条无循环路径之外的所有路径

Question

我有一个有n 个节点的连通无向图。给定两个节点，我想找到必须删除的最小边数，以确保这两个节点之间只有一条无循环路径。

例如，如果这是图表：

1------------2------------5
|                         | 
|                         | 
3-------------------------4

那么给定节点1和5，答案将是1：只需删除（例如）节点 3 和节点 4 之间的边。

暴力方法是，对于边集的每个子集，尝试删除这些边并测试两个感兴趣的节点之间是否存在唯一的无循环路径。

有更有效的方法吗？（我用谷歌搜索过，但没有找到任何相关内容。）

---

（亲爱的 cryptomanic，我添加这些示例是为了帮助讨论确切的要求；请编辑此部分并指出这些解决方案中哪些是有效的。m69）

输入图：（从X到Y）

          O---O---O---O       O
         /     \ /     \     / \
O---O---X       O       Y---O---O
         \             /
          O---O---O---O
             / \       \
            O---O       O

解决方案A：（X和Y之间没有循环）

          O---O---O---O       O
         /       /     \     / \
O---O---X       O       Y---O---O
                       /
          O---O---O---O
             / \       \
            O---O       O

解决方案 B：（X 和 Y 之间没有旁路）

          O---O---O---O       O
         /             \     / \
O---O---X       O       Y---O---O
                       /
          O---O---O---O
             / \       \
            O---O       O

解决方案C：（没有循环连接到X和Y）

          O---O---O---O       O
         /       /     \       \
O---O---X       O       Y---O---O
                       /
          O---O---O   O
             / \       \
            O---O       O

方案D：（完全隔离X到Y的路径）

          O---O---O---O       O
         /             \     / \
O---O   X       O       Y   O---O

          O---O---O---O
             / \       \
            O---O       O

解决方案E：（P只能使用一次，因此PQRP不是替代路径的一部分）

          O---O---O---O       O
               \ /           / \
O---O---X       O       Y   O---O
         \             /
          O---P---O---O
             / \       \
            Q---R       O

方案F：

          O---O---O---O       O
               \ /     \     / \
O---O---X       O       Y---O---O
         \             /
          O---O---O---O
             / \       \
            O---O       O