简介:
Maximum Cut 问题,俗称最大割问题,NP-hard。给定一张,求一种分割方法,将所有顶点(Vertex)分割成两群,同时使得被切断的边(Edge)数量最大。...转化:
图片
此问题最大化形式为:
PS:参数(-2)可调节,只要将(0,0),(0,1)/(1,0),(1,1)分割开即可,并且使得(0,1)/(1,0)输出的值最大或者最小即可。...8), (1, 4), (1, 5), (1, 8), (2, 8), (2, 9), (3, 6), (3, 7), (4, 7), (5, 7), (6, 9)]
数目:13
参考文献:
最大割问题