5经典图论问题.doc

.5经典图论问题5.1 一笔画问题一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到ab迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索vv的闭迹，添加到ab迹上，即得到av-vb迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。逐步扩展即可。二、弗罗莱（Fleury）算法 任取v0V(G)，令P0=v0；设Pi=v0e1v1e2ei vi已经行遍，按下面方法从中选取ei+1：（a）ei+1与vi相关联；（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-e1,e2, , ei中的桥（所谓桥是一条删除后使连通图不再连通的边）；（c）当（b）不能再进行时，算法停止。5.2 中国邮递员问题（CPP）规划模型：设为经过边的次数，则得如下模型。 5.3 旅行推销员问题（TSP，货郎担问题）（NPC问题）定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。分析：从一个哈密顿圈出发，算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2）象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。算法二：算法三：Step1：取权数最小的四条边，权和29，不合理（v4度数为3）但为下界，分两枝保留或去掉（v1，v4）示例：设旅行推销员的矩阵为Step2：去掉（v1，v4）后取权最小的四条边规划模型：先将一般加权连通图转化成一个等价的加权完全图，设当从到时，否则，则得如下模型。 不含子巡回或1，不含子巡回的约束也可以用如下条件表示：5.4 排课表问题问题一边色数:给图的边着色，相邻边着不同的颜色，则每条边都着上颜色而且最少的颜色数称为边色数，对于排课表问题来说，一种颜色表示可以在同一时间段同时上课的情况。定理：最小边色数等于最大顶点度数。以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样（为最大度数），然后求一组完美匹配M，着同样颜色，然后从图中去掉M中的边,再求第二组完美匹配。问题二：基本思想是：由给定的教室数与总课时数确定教学时间长度（即匹配数-色数），在没有考虑教室数限制所计算的匹配数基础上，增加空匹配至时间长度个，然后调节匹配边差大于1的匹配，直到满足要求。5.5 几个小问题会议安排问题例如: 举行一个国际会议,有A, B, C, D, E,F,G 7个人。已知下列事实:A 会讲英语; B 会讲英语和汉语;C 会讲英语、意大利语和俄语;D 会讲日语和汉语;E 会讲德语和意大利语;F 会讲法语、日语和俄语;G 会讲法语和德语。试问这7个人应如何排座位, 才能使每个人都能和他身边的人交谈?解答：那么我们用结点来代表人,于是结点集合V=A,B,C,D,E,F,G对于任意的两点,若有共同语言,就在它们之间连一条无向边,可得边集E,图G=(V,E), 如下图: 问题转化为在图中找到一条哈密顿回路的问题(哈密顿回路即是通过每个结点一次且仅一次的回路)。而A-B-D-F-G-E-C-A 即是图中的一条哈密顿回路。照这个顺序排座位就可以解决问题了。过河问题一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24 =16 种状态.在河东岸的状态类似记作.由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的.以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.根据此图便可找到渡河方法.问题转化为求一点到另一点的路。放置机器人有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。 模型一以空地为顶点，有冲突的空地间连边，问题转化为最大独立点集。模型二我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。同样，把竖直方向的块也编上号。把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化为二部图的最大匹配问题。比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，对要素的选取，是图论建模中至关重要的一步。打猎猎人要在n*n的格子里打鸟，他可以在某一行中打一枪，这样此行中的所有鸟都被打掉，也可以在某一列中打，这样此列中的所有鸟都打掉。问至少打几枪，才能打光所有的鸟？建图：二分图的X部为每一行，Y部为每一列，如果(i,j)有一只鸟，那么连接X部的i与Y部的j。该二分图的最大匹配数则是最少要打的枪数。设备更新问题某企业使用一台设备,每年年初,企业都