连接节点以最大程度地增加边缘总重量 [英] Connect nodes to maximize total edge weight

问题描述

我正在研究一个可以简化为以下图优化问题的问题.

I am working on a problem which could be reduced to a graph optimization problem as below.

• 给出了一组彩色节点.它们都是未连接的，即图中没有边.

• A set of colored nodes is given. They are all unconnected i.e. there is no edge in the graph.

要在节点之间插入边.

一个节点最多只能有4条边.

A node can have only 4 edges at max.

一个表提供了从边缘贡献利润的规则.

A table provides rules for profit contribution from the edges.

例如

• 一条连接红色和红色的边:利润为10

• An edge connecting red to red: profit is 10

一条连接红色和蓝色的边:利润为20

An edge connecting red to blue: profit is 20

节点总数约为100.

颜色的总数通常约为20到30，但可以高达50.相应地，利润(边)表将是一长串，但不会列出所有可能的组合.表中未指定的边的利润假定为零.

The total number of colors is typically around 20 to 30, but it can go as high as 50. Correspondingly the table for profit(edge) would be a long list but it won't list all possible combinations. The profit for edges not specified in the table is assumed zero.

问题是要优化连接(边)，以使总利润最大化.

The problem is to optimize the connections (edges) such that the total profit is maximized.

我想知道这个问题(也许以其他方式)是否已知.如果是这样，请提供任何可能有帮助的指针.谢谢.

I am wondering if this problem, maybe in some other way, is known. If so, please provide any pointers that might be of help. Thanks.

推荐答案

您可以将其转换为寻找最大成本的完美匹配的问题，这可以在多项式时间内解决(例如

You can convert this to a problem of finding a perfect matching of maximum cost, which can be solved in polynomial time (e.g. using a variant of the Blossom algorithm )

转换是将度为d的每个节点拆分为d个左节点和d-4个右节点.

The conversion is to split each node of degree d into d left nodes and d-4 right nodes.

对于原始图中的每对顶点u，v，在未连接的顶点u左节点和未连接的顶点v左节点之间添加一条边，其权重等于将u和v合并的利润.

For each pair of vertices u,v in the original graph, add an edge between an unconnected vertex u left node and an unconnected vertex v left node of weight equivalent to the profit of joining u and v.

接下来，在每对左右节点之间(对于同一顶点)添加额外的边(权重为0).

Next add extra edges (of weight 0) between every pair of left and right nodes (for the same vertex).

现在在此新图中构造最大权重完美匹配.

Now construct the max weight perfect matching in this new graph.

要点是，多余的边缘会用完所有剩余的左节点(除4个以外).这意味着每个顶点只能从四个获利边缘中获利.

The point is that the extra edges use up all but 4 of the left nodes. This means that each vertex can only make profit from 4 of the profitable edges.

假设我们有7个有色节点的问题.我已经绘制了扩展图的与单个绿色节点和单个红色节点的部分相对应的部分.

Suppose we have a problem with 7 coloured nodes. I have drawn the section of the expanded graph that corresponds to the part for a single green node and a single red node.

请注意，左侧有6个绿色节点，比有色节点总数少1个.有2个右边的绿色节点，比左边的节点数少四个.有一个弯曲的边连接一个greenleft节点和一个红色的left节点.如果以完美匹配选择此弯曲边缘，则意味着应该将红色节点连接到绿色节点.

Note that there are 6 left green nodes, one less than the total number of coloured nodes. There are 2 right green nodes, four less than the number of left nodes. There is a single curved edge joining a greenleft node and a red left node. If this curved edge is chosen in the perfect matching it means that the red node should be joined to the green node.

这篇关于连接节点以最大程度地增加边缘总重量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！