我有一个强连接的有向图(即,对于图G中的每对节点(i,j),存在从i到j和j到i的路径).我希望从该图中找到一个强连通图,使得所有边的总和最小.
换句话说,我需要摆脱边缘,以便在移除它们之后,图形仍将是强连接的,并且边缘总和的成本最低.
我认为这是NP难题.我正在为一小组数据(如20个节点)寻找最佳解决方案,而不是近似.
编辑
更一般的描述:给定grap G(V,E)找到图G'(V,E'),使得如果在G中存在从v1到v2的路径,则在G中存在v1和v2之间的路径'和E'中每个ei的总和是最不可能的.所以它类似于找到最小等效图,只是在这里我们想要最小化边权重的总和而不是边的总和.
编辑:
到目前为止我的方法:我想过使用多次访问的TSP来解决它,但这是不正确的.我的目标是覆盖每个城市,但使用最低成本路径.所以,它更像是封面设置问题,我猜,但我不完全确定.我需要使用总成本最低的路径来覆盖每个城市,因此多次访问已访问过的路径不会增加成本.