经典图论问题.doc

《经典图论问题.doc》由会员分享，可在线阅读，更多相关《经典图论问题.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5经典图论问题5.1 一笔画问题一笔画算法即是从起点a开场选择关联边第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过向前延伸，如果到达终点b，得到ab迹，判断路上的的边数是否为图的总边数，是就终止，否那么选择迹上某个关联边没有用完的顶点v，用同样方式再搜索vv的闭迹，添加到ab迹上，即得到av-vb迹，如果这个迹的边数还没有到达总边数，那么再选择迹上某个关联边没有用完的顶点。逐步扩展即可。二、弗罗莱Fleury算法 任取v0V(G)，令P0=v0；设Pi=v0e1v1e2ei vi已经行遍，按下面方法从中选取ei+1：aei+1与vi相关联；b除非无别的边可供行遍，否那么ei+1不应该

2、为Gi=G-e1,e2, , ei中的桥所谓桥是一条删除后使连通图不再连通的边；c当b不能再进展时，算法停顿。5.2 中国邮递员问题CPP规划模型：设为经过边的次数，那么得如下模型。5.3 旅行推销员问题TSP，货郎担问题NPC问题定义：包含图G的所有定点的路圈称为哈密顿路圈，含有哈密顿圈得图称为哈密顿图。分析：从一个哈密顿圈出发，算法一：哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。算法二：算法三：Step1：取权数最小的四条边，权与29，不合理v4度数为3但为下界，分两枝保存或去掉v1，v4例如：设

3、旅行推销员的矩阵为Step2：去掉v1，v4后取权最小的四条边规划模型：先将一般加权连通图转化成一个等价的加权完全图，设当从到时，否那么，那么得如下模型。 不含子巡回或1，不含子巡回的约束也可以用如下条件表示：5.4 排课表问题问题一边色数:给图的边着色，相邻边着不同的颜色，那么每条边都着上颜色而且最少的颜色数称为边色数，对于排课表问题来说，一种颜色表示可以在同一时间段同时上课的情况。定理：最小边色数等于最大顶点度数。以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样为最大度数，然后求一组完美匹配M，着同样颜色，然后从图中去掉M中的边,再求第二组完美匹配。问题二：根本思想是：由给定

4、的教室数与总课时数确定教学时间长度即匹配数-色数，在没有考虑教室数限制所计算的匹配数根底上，增加空匹配至时间长度个，然后调节匹配边差大于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对于任意的两点,假设有共同语言,就在它们

5、之间连一条无向边,可得边集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)是不允

6、许的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的.以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.根据此图便可找到渡河方法.问题转化为求一点到另一点的路。放置机器人有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，假设它们之间没有墙，那么它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。模型一以空地为顶点，有冲突的空地间连边，问题转化为最大独立点集。模型二我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“

7、块。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。同样，把竖直方向的块也编上号。把每个横向块看作X部的点，竖向块看作Y部的点，假设两个块有公共的空地，那么在它们之间连边。于是，问题转化为二部图的最大匹配问题。比拟前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二那么充分抓住了问题的内在联系，巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二那么保存了原型中“棋盘这个重要的性质。由此可见，对要素的选取，是图论建模中至关重

8、要的一步。打猎猎人要在n*n的格子里打鸟，他可以在某一行中打一枪，这样此行中的所有鸟都被打掉，也可以在某一列中打，这样此列中的所有鸟都打掉。问至少打几枪，才能打光所有的鸟？建图：二分图的X部为每一行，Y部为每一列，如果(i,j)有一只鸟，那么连接X部的i与Y部的j。该二分图的最大匹配数那么是最少要打的枪数。设备更新问题某企业使用一台设备,每年年初,企业都要作出决定,如果继续使用旧的,要付维修费；假设购置一台新设备,要付购置费. 试制定一个5年更新方案,使总支出最少. 设备在每年年初的购置费分别为11,11, 12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18.第 46 页