有谁知道以下问题的算法:
给定无向连通图,找到可以切割2个不同边的方式的数量,使得图变得断开.
我认为问题的一部分(我知道算法)是计算可以切割1行的方式的数量,以便它变得断开.然后计算这些如何可以与其它线路进行分组得到值(M-K)*K + K*(K-1)/2,M=无.边缘,K=没有.1个边缘切割.
我不知道该怎么做的部分是寻找其他方式的数量削减2线,例如在一个只具有周期图形1 - 2 - 3 - 1边缘的任意组合切割线进行的有效方式图断开.
我编写了程序中找到所有1个边缘切口的部分,然后通过删除这些边缘将图形拆分为双连通分量.我尝试为第二部分写一些东西,为此制作了两个版本,但没有一个在每次测试中得到正确的答案.
关于本次作业问题的其他信息:*该方案应在与上述限制任何图表运行最大2秒*的边的数目是<100000*顶点的数目是<2000*可以有2个顶点之间的多个边.
我可以在O(N + M)中完成第一部分.我猜第二部分的复杂性应该是最大O(N*M).
您正在寻找包含两条边的所有边切口.仅当图形最多为2边连接时才存在这种边缘切割.
论文" 用于发现无取向图的所有最小的边缘切口高效算法由Karzanov和吉莫弗耶夫"包含用于计算图的所有最小的边缘切口的算法.从简单的角度来看,在我看来,似乎该算法也可用于查找具有指定边数(例如,2条边)的切割.算法的复杂度为O(lambda ^ 2),其中lambda是所需切割中的边数(在您的情况下为2),n是顶点数.
| 归档时间： |
|
| 查看次数： |
803 次 |
| 最近记录： |