寻找算法：生成二分图的最小割
Looking for algorithms: Minimum cut to produce bipartite graph
给定一个无向加权图（或一个更大的不相交图的单个连接组件），它通常包含许多奇数和偶数循环，我正在寻找算法来删除尽可能少的边，以便生成一个或多个二部子图。文献中是否有任何标准算法，例如存在最小割等？
我试图解决的问题在现实世界中看起来是这样的：
在一到两个时间段内，针对不同科目向学生进行大约 1 小时的演讲。学生可以报名参加至少一个他们选择的演示文稿，或者两个或三个（第三个选择是一个替代方案，以防其他一个不被演示）。它们必须是所有不同的选择。如果给定演示的注册人数少于三个，则不会提供。如果有 18 个或更多，则将在两个块中给出两次。我必须安排演示文稿，以满足最大注册人数。
在以下情况下，安排是微不足道的：
如果给出演示文稿，则始终可以满足仅注册一个演示文稿（即注册>=3）；
两个给定的演示文稿的注册总是令人满意的，如果其中至少一个被给出两次。
首先，汇总所有注册以确定哪些已提供一次，哪些已提供两次。如果学生报名参加的演示文稿其他报名人数太少，则选择替代演示文稿（如果还会提供）。
一天结束时，我得到一个无向加权图，其中顶点是演示文稿，边代表已注册该演示文稿组合的学生，每个演示文稿仅展示一次。权重对应于演示文稿的独特组合的注册数量（从而避免平行边）。
如果顶点或表示的数量大约为 20 或更少，我想出了一个蛮力解决方案，该解决方案在可接受的时间内完成。但是，每个额外的顶点都会使该解决方案的运行时间加倍。 28岁左右后，很快就变得难以控制了。
今年我们有 37 个演示文稿，其中 30 个只给出了一次，因此最终出现在图表中。我现在正在为更大的图表尝试如下：
- 找到所有分立元件并分别求解每个元件；
- 对于每个组件，递归地删除叶节点和桥边；
- 生成一棵生成树（我用的是Kruskal算法，效果很好），保存去掉的边；
- 通过一次将一条移除的边添加回树中并剥离树的其余部分来生成基本循环集；
- 使用 Gibbs-Welch 算法，我生成了所有元素循环的完整集合，从第 4 步中获得的基本集合开始；
- 统计每条边所属的奇偶循环数；
- 创建边的优先级队列（排序在下面讨论）并从其连接的组件中连续删除每条边，直到生成的组件是二分的。
我找不到可以证明其结果与使用蛮力方法（可能是 NP-hard）获得的解决方案一样可接受的优先级队列的排序。但是，我正在尝试以下方法：
一个。如果边只属于奇数圈，先去掉；
b。如果该边属于奇数多于偶数循环，则在任何其他属于偶数循环多于奇数的边之前将其删除；
c。应首先删除权重最小的边。
如果一条边同时属于奇环和偶环，删除它会留下更大的奇环。这就是为什么我要这样订购它们。显然，一条边所属的奇数圈数越大，优先级越高，但前提是影响的偶数圈数越少。
还有其他标准存在但需要在图形问题之外考虑；例如，删除一条边会有效地删除其中一个演示文稿的注册人数，因此必须密切注意不要让注册人数变得太少。
(编辑：也有可能将演示文稿分成两个部分，这两个部分的注册人数几乎足够，例如 15-16 人而不是 18 人。但这意味着无论谁进行演示，都必须做两次，所以这是一个权衡。）
提前感谢您的任何建议！
这个问题等同于 NP-hard 加权 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 如果存在则为零（因此可以省略相应的变量及其约束）。
给定一个无向加权图（或一个更大的不相交图的单个连接组件），它通常包含许多奇数和偶数循环，我正在寻找算法来删除尽可能少的边，以便生成一个或多个二部子图。文献中是否有任何标准算法，例如存在最小割等？
我试图解决的问题在现实世界中看起来是这样的： 在一到两个时间段内，针对不同科目向学生进行大约 1 小时的演讲。学生可以报名参加至少一个他们选择的演示文稿，或者两个或三个（第三个选择是一个替代方案，以防其他一个不被演示）。它们必须是所有不同的选择。如果给定演示的注册人数少于三个，则不会提供。如果有 18 个或更多，则将在两个块中给出两次。我必须安排演示文稿，以满足最大注册人数。
在以下情况下，安排是微不足道的：
如果给出演示文稿，则始终可以满足仅注册一个演示文稿（即注册>=3）；
两个给定的演示文稿的注册总是令人满意的，如果其中至少一个被给出两次。
首先，汇总所有注册以确定哪些已提供一次，哪些已提供两次。如果学生报名参加的演示文稿其他报名人数太少，则选择替代演示文稿（如果还会提供）。
一天结束时，我得到一个无向加权图，其中顶点是演示文稿，边代表已注册该演示文稿组合的学生，每个演示文稿仅展示一次。权重对应于演示文稿的独特组合的注册数量（从而避免平行边）。
如果顶点或表示的数量大约为 20 或更少，我想出了一个蛮力解决方案，该解决方案在可接受的时间内完成。但是，每个额外的顶点都会使该解决方案的运行时间加倍。 28岁左右后，很快就变得难以控制了。
今年我们有 37 个演示文稿，其中 30 个只给出了一次，因此最终出现在图表中。我现在正在为更大的图表尝试如下：
- 找到所有分立元件并分别求解每个元件；
- 对于每个组件，递归地删除叶节点和桥边；
- 生成一棵生成树（我用的是Kruskal算法，效果很好），保存去掉的边；
- 通过一次将一条移除的边添加回树中并剥离树的其余部分来生成基本循环集；
- 使用 Gibbs-Welch 算法，我生成了所有元素循环的完整集合，从第 4 步中获得的基本集合开始；
- 统计每条边所属的奇偶循环数；
- 创建边的优先级队列（排序在下面讨论）并从其连接的组件中连续删除每条边，直到生成的组件是二分的。
我找不到可以证明其结果与使用蛮力方法（可能是 NP-hard）获得的解决方案一样可接受的优先级队列的排序。但是，我正在尝试以下方法：
一个。如果边只属于奇数圈，先去掉；
b。如果该边属于奇数多于偶数循环，则在任何其他属于偶数循环多于奇数的边之前将其删除；
c。应首先删除权重最小的边。
如果一条边同时属于奇环和偶环，删除它会留下更大的奇环。这就是为什么我要这样订购它们。显然，一条边所属的奇数圈数越大，优先级越高，但前提是影响的偶数圈数越少。
还有其他标准存在但需要在图形问题之外考虑；例如，删除一条边会有效地删除其中一个演示文稿的注册人数，因此必须密切注意不要让注册人数变得太少。
(编辑：也有可能将演示文稿分成两个部分，这两个部分的注册人数几乎足够，例如 15-16 人而不是 18 人。但这意味着无论谁进行演示，都必须做两次，所以这是一个权衡。）
提前感谢您的任何建议！
这个问题等同于 NP-hard 加权 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 如果存在则为零（因此可以省略相应的变量及其约束）。