发布时间 : 星期六 文章经典图论问题更新完毕开始阅读b11de06cb84ae45c3b358c08
5经典图论问题
5.1 一笔画问题
5.2 中国邮递员问题(CPP)
规划模型:
设xij为经过边vivj的次数,则得如下模型。
maxij
xij?xki,vi?V vkvi??s.t. vivj??vv???wijijx
??1?xij?N,vivj??
5.3 旅行推销员问题(TSP)
分析:
算法一:象求最小生成树一样,从最小权边加边,顶点度数大于3以及形成小回路的边去掉。 算法二:
算法三:
规划模型:
先将一般加权连通图转化成一个等价的加权完全图,设当从vi到vj时,xij?1,否则,
xij?0,则得如下模型。
min??wijxij
i?1j?1nn s.t. ?xj?1nnij?1,i?1,?,n
?xi?1ij?1,j?1,?,n k?2,?,n?1
xi1i2?xi2i3???xiki1?k?1,i1,?,ik?1?n
xij?0或1,i,j?1,?,n,i?j
5.4 排课表问题 问题一
定理:最小边色数???G?等于最大顶点度数??G?。
以下加边循环算法为多项式时间算法:就是加边让每个顶点的度数一样(为最大度数),然后求一组完美匹配M,着同样颜色,然后从图中去掉M中的边,再求第二组完美匹配。。。。。。。。