边1代价顶点2代价的最小代价算法

Question

我正试图为以下情况想出一个算法：我想在一个无向图上运行一个最小代价算法。边有一个与之相关的代价，顶点有两个与之相关的代价。这就是它变得有点棘手的地方。我必须选择与顶点相关的2个成本中的一个。如果我选择cost1，顶点将属于类型1，如果我选择cost2，顶点将属于类型2。只有当顶点具有不同的类型时，它们才能被认为是由一条边连接的。大多数时候，为顶点选择成本最低的顶点是合乎逻辑的，但是根据与它相关联的边的成本，以及它的相邻顶点的类型，您更愿意为顶点选择成本最高的顶点，从而获得较小的总体成本。任何建议，如哪种算法或什么方法，我应该尝试应用，将非常感谢。

这里有一个链接到我正在尝试实现的一个简单示例。该解决方案的成本为57，这是该图可能的最低成本。

编辑：拼写。

Answer 1

你描述的问题可以简单地转化为最小割问题，然后用Stoer-Wagner算法求解。再创建两个顶点，每个顶点都有到所有其他顶点的边（彼此除外）。边代价取自相应顶点的代价1s；另一方面，从他们的成本。现在找到一个最小的削减；这将在两个新节点之间进行切割，并将原始顶点划分为type1和Type2。

编辑：如果（原始的）边成本与顶点成本相比足够高，那么您可能会在同一个分区中找到两个新的顶点。为了防止这种情况发生，向新顶点上添加的所有边（大于所有其他边的总和）添加一个很大的相等代价。