图中的禁止路径
forbidden paths in a graph
我们提供了一个有向图（数据流图）。我们希望禁止数据到达图的某些节点，这意味着我们将禁止删除路径但必须保持图的连接。
我提出一个简单的例子来说明问题：
让我们看下图：
A------>B-------->C-------->D
我想禁止数据到达节点C，所以边B-C将被删除。同时我希望数据到达D。因此将创建一条来自B-D的新边。
上面的任务有高效的算法吗？
谢谢。
每个不允许到达的节点X都有i条入边和j条出边。当我们谈论数据流图时，X 之前的节点仅到达 X 之后的 j 个节点之一是不够的。您可以插入一个虚拟 (Steiner) 节点 X'，它除了没有被标记外没有任何功能X 在其中发送所有 i 条边并连接 j 条出边。否则，您可能必须连接 i 个传入边之一的每个节点，并将其连接到 X 的传出边引导的所有 j 个节点。 （否则数据流中断。）
修复一对一节点是一个常数时间操作，但是修复一个这样的节点 X 的所有关系需要 O(i*j) 时间，即它是事件边数的二次方。
来自 a、b 和 c 的数据流向 X，然后从那里流向 x、y 或 z。
因此，来自a的数据可以到达x、y和z。
要删除 a->X 的边，我们必须将 a 的边添加到从 X 可达的所有节点。由于我们必须对到达 X 的每条边执行此操作，因此我们得到二次复杂度。
编辑：（由于评论）对于两个禁止节点 X 和 Y，如果存在从 X 到 Y 的边，则可以保留这样的边。删除所有禁止节点（禁止节点除外）的所有边后，禁止节点可能形成大小 > 1 的连通分量。这不是问题，因为每个这样的连通分量仅包含禁止节点和边，并且无法从剩余的流程图。
在此之后，我们只删除从有效节点到禁止节点的边。为了满足需求，必须移除这些边缘。没有其他边被删除，因此这是满足请求的最小数量。 （我认为这里没有太多其他东西可以证明。）
我们提供了一个有向图（数据流图）。我们希望禁止数据到达图的某些节点，这意味着我们将禁止删除路径但必须保持图的连接。
我提出一个简单的例子来说明问题：
让我们看下图：
A------>B-------->C-------->D
我想禁止数据到达节点C，所以边B-C将被删除。同时我希望数据到达D。因此将创建一条来自B-D的新边。
上面的任务有高效的算法吗？
谢谢。
每个不允许到达的节点X都有i条入边和j条出边。当我们谈论数据流图时，X 之前的节点仅到达 X 之后的 j 个节点之一是不够的。您可以插入一个虚拟 (Steiner) 节点 X'，它除了没有被标记外没有任何功能X 在其中发送所有 i 条边并连接 j 条出边。否则，您可能必须连接 i 个传入边之一的每个节点，并将其连接到 X 的传出边引导的所有 j 个节点。 （否则数据流中断。）
修复一对一节点是一个常数时间操作，但是修复一个这样的节点 X 的所有关系需要 O(i*j) 时间，即它是事件边数的二次方。
来自 a、b 和 c 的数据流向 X，然后从那里流向 x、y 或 z。
因此，来自a的数据可以到达x、y和z。
要删除 a->X 的边，我们必须将 a 的边添加到从 X 可达的所有节点。由于我们必须对到达 X 的每条边执行此操作，因此我们得到二次复杂度。
编辑：（由于评论）对于两个禁止节点 X 和 Y，如果存在从 X 到 Y 的边，则可以保留这样的边。删除所有禁止节点（禁止节点除外）的所有边后，禁止节点可能形成大小 > 1 的连通分量。这不是问题，因为每个这样的连通分量仅包含禁止节点和边，并且无法从剩余的流程图。
在此之后，我们只删除从有效节点到禁止节点的边。为了满足需求，必须移除这些边缘。没有其他边被删除，因此这是满足请求的最小数量。 （我认为这里没有太多其他东西可以证明。）