发布时间 : 星期一 文章经典图论问题更新完毕开始阅读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中的边,再求第二组完美匹配。。。。。。。。