有向图中指定可割边的必要割集求解：断开目标节点与源节点

问题说明 #

• 核心需求：在有向图中筛选出必须切断的蓝色边组合，使黄色目标节点与紫色源节点（节点0）完全断开连接，且仅允许操作标记为蓝色的边。
• 示例情况：
  • 节点2因与源节点通过黑色边直接连通，无法通过切断蓝色边实现隔离；
  • 节点3可通过切断[(1, 3), (4, 3), (5, 3)]或[(1, 3), (4, 3), (4, 5)]这类边集完成隔离。
• 问题与经典算法的差异：
  • 仅指定的蓝色边可被切断，而非所有边；
  • 存在非最小规模但不可简化的替代割集，超出常规最小割问题的范畴。
• 当前状态：已能枚举所有可实现隔离的割边组合，但需要进一步提炼出最小必要的割边条件（即无法再移除任何边的有效割集）。

现有实现代码 #

import networkx as nx
import matplotlib.pyplot as plt  # 补充缺失的导入，否则plt.show()会报错

G = nx.DiGraph()
for i in range(6):
    G.add_node(i)
G.add_edge(0, 1)
G.add_edge(1, 0)
G.add_edge(1, 2)
G.add_edge(3, 2, p=True)
G.add_edge(1, 3, p=True)
G.add_edge(3, 1, p=True)
G.add_edge(5, 3, p=True)
G.add_edge(3, 5, p=True)
G.add_edge(4, 3, p=True)
G.add_edge(3, 4, p=True)
G.add_edge(5, 4, p=True)
G.add_edge(4, 5, p=True)
G.add_edge(4, 0)
G.add_edge(0, 4)

node_colour = ["tab:purple", "lightgreen", "yellow", "yellow", "lightgreen", "lightgreen"]
cut = nx.get_edge_attributes(G, "p")
edge_colour = ["blue" if edge in cut.keys() else "black" for edge in G.edges]
nx.draw(
    G, with_labels=True, node_size=500, node_color=node_colour, edge_color=edge_colour
)
plt.show()

# 评估切断所有蓝色边后节点是否不可达
G2 = G.copy()
blue_edges = nx.get_edge_attributes(G2, "p").keys()
G2.remove_edges_from(blue_edges)
unreachable = []
for node in [2, 3]:
    try:
        nx.algorithms.shortest_path(G2, 0, node)
    except nx.NetworkXNoPath:
        unreachable.append(node)

内容的提问来源于stack exchange，提问作者base12