保持连通分量的有向图的最小边集
以下是完整的问题：
-
null
我的两个问题是：（1）在最小化SCCs之间的边之前的算法是正确的吗？（2）如何使SCC之间的边最小化。
对于(2)，我知道这相当于使DAG中的边数最小化。（将SCCs视为顶点）。但这似乎对我没有帮助。
共有1个答案
关于步骤2，最小化SCCs之间的边，您可以随机选择一个顶点，并运行DFS，只为每对（根、端）保留最长的路径，同时删除其他路径。将搜索到的所有顶点存储在列表L中。
选择另一个顶点，如果它存在于L中，跳到下一个顶点；如果没有，重复上述步骤。
-
考虑一个不连通的有向图的例子，其中顶点和边其中顶点是孤立的。 根据这里的答案：（对强连通图的最小加法），保证这个图所需的最小边数结果是3。 如何找到将这些边添加到哪里，即图中一条边的起始点和终止点？
-
对于算法的最终审查,出现了这样一个问题： 由于连通组件本质上是图中的一个图，这意味着子图中的所有顶点必须从较大的图中移除，同时保持内部连通性。我能理解这种直觉，但很难把它转化成一个公式。 到目前为止，我得出的结论如下： 对于连通分量n，每个图Gn具有相应的顶点集{Vn}，使得顶点集的内容在内部连接，而在外部保持不连接。 现在，每个{Vn}最多包含V*(V-1)条边。 如何用公式表示最大边数？
-
我在NetworkX中有一个有向无环简单图。 现在，对于每个边，该边都有一个“源”和一个“目标”。如果除了这个边之外，还有一条从“源”到“目标”的路径，那么我想删除这个边。 null > 节点为： 边缘是：
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
-
给定一个一般的无向图，如何在O(n+m)时间内打印出图的所有双连通分量？我知道Tarjan的算法，用于输出无向图的所有连接点，但我发现很难扩展该算法来打印双连接的组件。我试着搜索google，但我得到的所有结果都不能用于我的测试用例，因为它们错过了算法的边缘情况。 编辑：我已经成功地实现了Niklas提供的这个链接中描述的算法。现在我有一个不同的问题，我如何找出一个不含边的无向图的子图，如果删除它
-
给定一个带正权的无向图，有2种边：锁定边和未锁定边。确定给定边沿是锁定边沿还是未锁定边沿需要O(1)。 > 对于给定的两个顶点s，t和一个正数k=O(1)，我如何找到s和t之间最多包含k条锁定边的最短路径？ 对于给定的两个顶点s，t和一个正数k=O(1),我如何找到s和t之间恰好包含k条锁定边的最短路径？ 我不知道如何在这个图上运行Dijkstra算法来找到给定顶点之间的最短路径，以及如何将无向图