随机方法在图分割及相关优化问题中理论与算法应用研究

本项目拟利用条件期望，浓缩法,对称及非对称局部引理，随机矩阵等随机方法结合组合分析讨论简单图,超图中带有不平衡参数的明智二（多）分割问题的组合性质和上下界。.并拟利用随机超平面扰动算法，随机选取法，组合分析结合Matlab编程推广和改进赋权图中不平衡二（多）分割相关问题的近似算法。并将结论和方法应用到目录分割及其变形，设备随机排序及其变形等相关组合优化问题。

图中的拓扑结构对组合网络的性能, 系统可靠性和费用都有重大影响. 而利用图中拓扑结构来制定的策略需要考虑很多不确定因素, 从而减少很多资源和费用等方面的损失, 所以随机方法更加符合网络拓扑结构讨论的发展趋势. 本项目主要是利用随机方法与组合图论经典分析方法结合讨论与图分割相关的几类优化问题的理论与算法应用研究. 这些与图的分割相关的优化问题大多数是NP完备的, 包括图中的明智分割问题; 范德瓦尔登函数问题; 随机图中分割匹配问题; 超图中独立数问题; 边染色图中是否可以分割出彩虹短圈问题; 及利用鞅方法讨论不含某种限制结构的分割极值问题. 我们都利用随机技巧改进前人结果, 解决文献中提出的问题.并且我们也针对与经济现象相关的图分割问题进行算法设计, 包括商品目录分割问题, 有资金约束的随机厌恶式选址问题, 及网络中分工与合作进化问题. 这些研究成果丰富和完善了随机方法在图中优化问题的应用研究.