Optimize connection between nodes in a graph [dupl

问题:

This question already has an answer here:

• Connect nodes to maximize total edge weight 5 answers

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

A set of colored nodes are given.

A set of rules are given about the cost contribution from the nodes.

Ex.

• If a red node is not connected, cost is 100

• If a red node connects to red node, cost is 10

• If a red node connects to a blue node, cost is 20

• Any node can have only 4 connections at max.

The problem is to optimize the connections (vertices) such that the total cost is minimized and the final graph obeys the rules.

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

( Please let me know if any of the tags should be removed. )

回答1:

1) In the case that the numbers of red and blue nodes are balanced, the optimal solution is a chain with alternating colours.

2) If you deviate from balance, you will want to connect your surplus nodes to nodes of the opposite colour with free slots.

3) If no 'free' slots are available, you will want to add the remaining nodes in subgraphs that are tree-like.

EDIT:

This solution only applies to the original formulation of the question, which indicated the existence of only 2 colours.