1

给定一个通常包含许多奇数和偶数循环的无向加权图（或更大的不相交图的单个连通分量），我正在寻找算法来删除尽可能少的边数，以便生成一个或多个二分子图. 文献中是否有任何标准算法，例如存在最小切割等？

我试图解决的问题在现实世界中是这样的：在一个或两个时间段内向学生提供关于不同主题的每个大约 1 小时的演示。学生可以注册至少一个他们选择的演示文稿，或者两个，或三个（第 3 选择是一个替代方案，以防其他一个不会出现）。它们必须是不同的选择。如果给定演示文稿的注册人数少于三个，则不会给予。如果有 18 个或更多，它将在两个块中给出两次。我必须安排演示文稿，以便满足最大数量的注册。

在以下情况下，调度是微不足道的：

  1. 如果提供演示文稿，则始终可以满足仅一个演示文稿的注册（即注册数> = 3）；

  2. 如果至少其中一个被给予两次，那么两次给定演示文稿的注册总是令人满意的。

首先，汇总所有注册，以确定哪些注册一次，哪些注册两次。如果学生已报名参加其他报名人数太少的演示文稿，则选择替代演示文稿（如果它也将提供）。

归根结底，我得到了一个无向加权图，其中顶点是演示文稿，边代表已注册该演示文稿组合的学生，每个演示文稿只呈现一次。权重对应于独特演示组合的注册数量（从而避免平行边）。

如果顶点或表示的数量约为 20 或更少，我想出了一个在可接受的时间内完成的蛮力解决方案。但是，每个额外的顶点都会使该解决方案的运行时间加倍。在 28 岁左右之后，它迅速变得无法控制。

今年我们进行了 37 次演示，其中 30 次只进行了一次，因此最终出现在图表中。我现在正在尝试更大的图表如下：

  1. 找到所有分立元件并单独求解每个元件；
  2. 对于每个组件，递归地移除叶子节点和桥接边；
  3. 生成一棵生成树（我正在使用运行良好的 Kruskal 算法），保存删除的边缘；
  4. 通过一次将一个删除的边缘添加回树并剥离树的其余部分来生成基本循环集；
  5. 使用 Gibbs-Welch 算法，我从步骤 4 中获得的基本集合开始生成所有元素循环的完整集合；
  6. 统计每条边所属的奇偶周期数；
  7. 创建边的优先级队列（下面讨论排序）并从其连接的组件中连续删除每个边，直到结果组件是二分的。

我找不到优先级队列的排序，我可以证明其结果与使用蛮力方法获得的解决方案一样可接受（它可能是 NP-hard）。但是，我正在尝试这些方面的东西：

一种。如果边只属于奇循环，先去掉；

湾。如果边属于奇数多于偶数循环，则在任何其他属于偶数多于奇数的边之前将其删除；

C。应首先删除权重最小的边缘。

如果一条边同时属于奇数和偶数循环，则删除它会留下更大的奇数循环。这就是为什么我要这样订购它们。显然，边缘所属的奇数周期数越大，优先级越高，但前提是影响的偶数周期越少。

还有其他标准存在，但需要在图形问题之外考虑；例如，删除边缘有效地删除了其中一个演示文稿的注册，因此必须注意不要让注册的数量变得太少。

（编辑：也有可能将演示文稿分成两个几乎有足够注册的块，例如 15-16 而不是 18。但这意味着进行演示的人必须做两次，所以这是一个权衡。）

在此先感谢您的任何建议！

4

1 回答 1

1

这个问题等价于 NP-hard weighted max cut problem，它要求将顶点分成两部分，使得最大数量的边在两部分之间。

我认为解决诸如您所拥有的问题大小的最简单方法是将其表述为二次整数程序，然后应用现成的求解器。配方看起来像

maximize (1/2) sum_{ij} w_{ij} (1 - y_i y_j)
subject to
y_i in {±1} for all i

其中w_ij是无向边的权重，ij如果存在则为零（因此可以省略相应的变量及其约束）。

于 2017-02-28T14:03:06.227 回答