经典图论问题

5经典图论问题5.1一笔画问题5.2中国邮递员问题（CPP）规划模型：设ijx为经过边jivv的次数，则得如下模型。jivvijijxwmaxjiikvvivvkiijVvxx,jiijvvNx,15.3旅行推销员问题（TSP）分析：..ts算法一：象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。算法二：算法三：规划模型：先将一般加权连通图转化成一个等价的加权完全图，设当从iv到jv时，1ijx，否则，0ijx，则得如下模型。ninjijijxw11minnjijnix1,,1,1niijnjx1,,1,11,,2nkniikxxxkiiiiiik1,,,11132210ijx或1，jinji,,,1,5.4排课表问题问题一定理：最小边色数G等于最大顶点度数G。以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样（为最大度数），然后求一组完美匹配M，着同样颜色，然后从图中去掉M中的边,再求第二组完美匹配。。。。。。。。..ts问题二：基本思想是：由给定的教室数与总课时数确定教学时间长度（即匹配数--色数），在没有考虑教室数限制所计算的匹配数基础上，增加空匹配至时间长度个，然后调节匹配边差大于1的匹配，直到满足要求。