时间戳

首页 > 解决方案 > 如何使用 Gurobi 在 Python 中对图形进行分区？

gurobi - 如何使用 Gurobi 在 Python 中对图形进行分区？

问题描述

我正在研究一个图形分区问题，我想将下面的图形分成两个区域，目的是减少最少的线数。

这是它背后的数学：

二进制变量，当顶点包含在子集中时取值为 1，否则取值为 0（即，包含在子集中）。二元变量模拟边缘与不同子集相关的情况，即，如果边缘 {, } 的端点交叉，则 = 1，否则 = 0。

谢谢

标签： gurobi

解决方案

@Sagnik 请使用这项研究： Kirmani 和 Madduri 的https://doi.org/10.1109/IPDPSW.2018.00053。要实现分区，您需要计算图的度归一化矩阵。第二个特征向量，也称为外场向量，将给出您正在寻找的分区。请问你的图有多大？

推荐阅读