我不知道该用什么术语来搜索(我已经搜索过“映射算法”和“一对一算法”),我想不出一个更简单(更规范)的公式。
我有两套,比如说
A B C D E
和
L M N O P
给我一张一对多的地图。
A --> L, M, N, P
B --> M
C --> M, N, O
D --> N
E --> O, L
什么是最简单和/或最快的算法,它可以告诉地图的一个一对一的“子集”是否可以覆盖所有的项目?例如,上面确实存在这样一个“子集”:
A --> P
B --> M
C --> O
D --> N
E --> L
我不需要知道子集映射
给定一个参数k,我试图从有向图中删除k个边,这样最大流就会尽可能地减少。这个图有一个源和一个接收器t,每个边的容量是一个。图可能包含循环,也可能不包含循环。
我建议的解决方案是首先对图执行拓扑排序,使用“宽恕”循环的算法--也许是通过忽略将我们带回源的边缘。然后(假设k >= 1):
i = 0
for each vertex u order by topological(u)
for each edge (u, v) order by topological(v) descending
if topological(v) > topological(u) th
除了edge的功能之外,我还在尝试实现顶点容量的最大流。我在wiki中发现了一个新的图G,其中每个顶点对应于v_in和v_out,并对边进行了适当的更改。
我最初的实现做了一些其他的事情,我想知道它是否错误。
在最初的fulkerson检查路径的步骤中,它增加了路径相对于这条路径中最小容量的边缘的流量(我们不能超过这一点)。如果我也在这条路径中找到了最小的顶点容量,那么会怎样呢? --这些量之间的最大值(max(b(v)) and max(b(e)) for v and e in path p) --将定义可以通过该路径的最大流,不是吗?复杂性保持不变。
如果有一定数量的节点与边缘连接(如与街道交叉),且每个节点的值为0到3,则边的值为0。
现在我想写一个算法,它将节点的值分配给值边,所以在算法终止后,所有节点的值都是0,而所有的边都是<= 1。
例如,给定此图表:
我想制作这个:
。
我的解决方案:
我已经定义了数据类型-十字路口和Street:
public class Crossing{
int value;
}
public class Street{
int value;
Crossing A, B;
}
该算法迭代交叉路口并将值分配给街道(注意,交叉口只能将其值分配给相邻的街道)。
v
我正在尝试确定最佳的算法来解决一个分配课程的要求。要求有一定数量的学分,才能被视为满足。课程有很多学分,当被录取的时候。因此,数据结构看起来类似于:
export class Course {
constructor(public id:number,
public credits:number) {
}
}
export class Requirement {
constructor(public id:number,
public name:string,
public credits:nu
我知道这个问题在这里已经讨论过不止一次了。但是,我需要在运行时间为|V| x |E|的有向图中找到顶点不相交路径的最大数量K。
我知道将每个顶点转换为v_in,v_out,然后从v_in到v_out添加容量为1的边,并为每一对顶点(u,v)添加容量为1的边从u_out到v_in的算法,然后计算此网络中的最大流量。然而,在我的计算之后,这个算法对于最大流量需要O(E)预处理+ O(VE^2)或O(V^2E)。我做错了什么吗?
使用write_dimacs python库的方法有问题:
由于一些我不明白的原因,当我尝试使用它时,我得到了错误:KeyError: 'Attribute does not exist' (参见下面的完整输出)。
下面是一个在我的系统上重现错误的示例代码片段(mac x 10.10.5,python 3.5.1,python-igraph-0.7.1.post6):
from igraph import *
g = Graph.Read_Edgelist("graph3.txt")
print(g)
# This works fine
g.write_a
我需要用这样的方式划分一个图,即节点X和节点Y不再连通。另外,移除的边的权重之和必须是最低的。
例如:
3 1 2
X ----- Z ----- W ----- Y
应成为:
3 2
X ----- Z W ----- Y
我首先认为我可以用一个循环来计算X和Y之间的最短路径,并去掉最便宜的边,直到没有更多的路径为止。然而,经过思考,我意识到这种方法并非在所有情况下都有效。
维基百科的搜索给我带来了Kernighan-Lin和Fiduccia-Mattheyses算法,但它们似乎是为了解决其他分区问题。
有标准的