《经典图论问题.doc》由会员分享，可在线阅读，更多相关《经典图论问题.doc（6页珍藏版）》请在金锄头文库上搜索。
5经典图论问题5.1 一笔画问题5.2 中国邮递员问题（CPP）规划模型：设为经过边的次数，则得如下模型。 5.3 旅行推销员问题（TSP）分析：算法一：象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。算法二：算法三：规划模型：先将一般加权连通图转化成一个等价的加权完全图，设当从到时，否则，则得如下模型。 或1，5.4 排课表问题问题一定理：最小边色数等于最大顶点度数。以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样（为最大度数），然后求一组完美匹配M，着同样颜色，然后从图中去掉M中的边,再求第二组完美匹配。问题二：基本思想是：由给定的教室数与总课时数确定教学时间长度（即匹配数-色数），在没有考虑教室数限制所计算的匹配数基础上，增加空匹配至时间长度个，然后调节匹配边差大于1的匹配，直到满足要求。
