Как разделить граф на Python, используя Gurobi?

Question

Я работаю над проблемой разбиения графа, где я хочу разделить следующий график на две зоны с целью разрезания минимального количества линий.

Вот математика, стоящая за ним:

Двоичные переменные ??, которые примут значение 1, когда вершина ? включена в подмножество ?, ив противном случае значение 0 (т. е. ? входит в подмножество ?).Двоичные переменные ??? моделируют случай, когда ребра попадают в разные подмножества, т. Е. ??? = 1, если конечные точки ребра {?, ?} пересекают ? и ?, в противном случае ??? = 0.

Спасибо

Answer 1

@ Сагник Пожалуйста, используйте это исследование: https://doi.org/10.1109/IPDPSW.2018.00053 Кирмани и Маддури.Для достижения разбиения вам необходимо вычислить нормализованную матрицу степеней для графа.Второй собственный вектор, также называемый вектором поля, даст искомый раздел.Могу я спросить, насколько велик твой график?