经典图论问题(共6页).doc

精选优质文档-倾情为你奉上5经典图论问题5.1 一笔画问题5.2 中国邮递员问题（CPP）规划模型：设为经过边的次数，则得如下模型。 5.3 旅行推销员问题（TSP）分析：算法一：象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。算法二：算法三：规划模型：先将一般加权连通图转化成一个等价的加权完全图，设当从到时，否则，则得如下模型。 或1，5.4 排课表问题问题一定理：最小边色数等于最大顶点度数。以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样（为最大度数），然后求一组完美匹配M，着同样颜色，然后从图中去掉M中的边,再求第二组完美匹配。