Jos*_*hDG 16 algorithm graph-theory graph
我有这个问题.我有一个n个节点的图形,我想分成两个x节点子节点和nx个节点,这些节点受到剩余边数最大化(或最小化被切割边数)的约束.
不确定这是否有意义.不是图论人,但这是我问题的抽象版本.我应该看哪些算法可能对我有帮助？
这不是一个家庭作业问题.虽然我觉得有趣的问题!
我计划在C中实施
uty*_*uty 11
x = n - x的特殊情况称为最小二分问题,并且是NP难的.这也使你的问题也很难.维基百科关于图分区的文章中描述了几种启发式方法,包括局部搜索(例如,从随机剪切开始并重复交换减少剪切大小的顶点对)和频谱方法(例如,计算和阈值第二个特征向量) ).如果n很小,则整数编程也是可能的.
归档时间：
13 年，8 月 前
查看次数：
3848 次
最近记录：