图经典运筹学幻灯片.ppt
图经典运筹学第1页，共43页，编辑于2022年，星期五歌尼斯堡七桥难题普莱格尔河第2页，共43页，编辑于2022年，星期五结论：不存在这样一种走法。用A、B表示两座小岛，C、D表示两岸，连线AB表示A、B之间有一座桥。问题简化为：ABCD在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点七桥问题的数学模型：第3页，共43页，编辑于2022年，星期五类似的问题：一笔画问题字的一笔画：如“中、日、口、串”等可一笔画而：“田、目”等不能一笔画图的一笔画：可一笔画不可一笔画第4页，共43页，编辑于2022年，星期五图论的应用范围：1、中国邮路问题：邮递员如何选择适当的投递路线，使每条街道至 少走过一次且所走的总路程最短？2、最短路问题：一个乡有9个自然村，其间道路如下图所示，要以村为中心 建有线广播网，如要求沿道路架设广播线，应如何架设使所用电线最短411524431235514211212312第5页，共43页，编辑于2022年，星期五已知一个地区的交通网络如下图所示，其中点代表居民小区，边表示公路，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？结论：把医院建在v6，可使离医院最远的小区居民就诊时所走的路程最近即求图的中心3、选址问题603015182515202030第6页，共43页，编辑于2022年，星期五例：在一个输油管道网中，最大流问题4、网络流问题：旅客流、车流、货物流26173224215344第7页，共43页，编辑于2022年，星期五5.1 图第8页，共43页，编辑于2022年，星期五-由若干个点和连接这些点的某些连 线所组成的图形vi图中的点，称为顶点。ei图中的连线，称为边。m(G)=|E|G的边数，简记为mn(G)=|V|G的顶点数，简记为n一、图的概念记V=vi，E=ei,G=（V，E）图G一个图代表具体事物代表事物之间的联系Gm=6,n=55.1 基本概念第9页，共43页，编辑于2022年，星期五有向图无向图边e=（vi,vj）有方向边e=（vi,vj）无方向此时（vi,vj）=（vj,vi）e4=（v3，v4）=（v4，v3）e4=（v3，v4）（v4，v3）e5=（v3，v4）=（v4，v3）此时（vi,vj）（vj,vi）vi为始点，vj为终点有向图无向图e5=（v4，v3）（v3，v4）第10页，共43页，编辑于2022年，星期五二、常用名词：1、端点和关联边：2、相邻点和相邻边：3、多重边与环：4、多重图和简单图：第11页，共43页，编辑于2022年，星期五5、次：6、悬挂点和悬挂边：7、孤立点：8、奇点与偶点：，G的边数m=6第12页，共43页，编辑于2022年，星期五定理1 在图G=(V,E)中，所有点的次之和是边数m 的两倍。证明：由于每条边均与两个顶点关联，因此在计算顶点的次时每条边都计算了两遍所以顶点次数的总和等于边 数的二倍。三、次的性质第13页，共43页，编辑于2022年，星期五定理5.2 在任何图G=(V,E)中，奇点的个数为偶数证明：（定理5.1）只有偶数个奇数相加才能得到偶数第14页，共43页，编辑于2022年，星期五简单链 链四、链：初等第15页，共43页，编辑于2022年，星期五圈或回路简单圈初等圈道路第16页，共43页，编辑于2022年，星期五连通图不连通图第17页，共43页，编辑于2022年，星期五六、赋权图（网络）对图G=（V，E），若对每一条边e，都有一个实数w(e)与之对应，e的权则称图G=（V，E）为赋权图，或网络权w(e)通常表示距离、费用、容量等如公路交通图：Vi表示 城市，ei表示公路w(ei）表示公路ei的长度如w(e2）=50：城市v2 到城市v3的距离是50公里第18页，共43页，编辑于2022年，星期五5.2 欧拉图与中国回路问题开链一笔画问题第19页，共43页，编辑于2022年，星期五圈存在欧拉回路：该图特点：该图不存在欧拉回路 欧拉图第20页，共43页，编辑于2022年，星期五定理5.3 无向连通图G为欧拉图的 充要条件是G中无奇点已知G=（V,E)为欧拉图，即存在一条欧拉回路C，C经过G的每一条边，由于G为连通图，所以G中的每个点至少在C中出现一次证明：必要性第21页，共43页，编辑于2022年，星期五充分性：若无向连通图G=(V,E)中无奇点，则G为欧拉图例：第22页，共43页，编辑于2022年，星期五第23页，共43页，编辑于2022年，星期五第24页，共43页，编辑于2022年，星期五例：判断下图是否为欧拉图，若是，求出欧拉回路定理5.3 无向连通图G为欧拉图的 充要条件是G中无奇点第25页，共43页，编辑于2022年，星期五定理5.3 无向连通图G为欧拉图的充要条件是G中无奇点推论 无向连通图G有欧拉道路的充要条件 是G中恰有两个奇点第26页，共43页，编辑于2022年，星期五一笔画问题：1、一个连通图的顶点都是偶点，没有奇点，则该图 可以一笔画出2、一个连通图的顶点恰有两个奇点，其余均为偶点，则从任一奇点出发，可以一笔画出该图，而终点 则是另一个奇点。（从任一点出发均可）3、一个连通图的顶点有两个以上的奇点，则该图 不能一笔画出第27页，共43页，编辑于2022年，星期五田日中白回不连通可一笔画可一笔画不可一笔画可一笔画可一笔画不可一笔画不可一笔画第28页，共43页，编辑于2022年，星期五二、中国邮路问题提出问题的人：管梅谷教授时间：1962年提出的问题：一个邮递员从邮局出发分送邮件，要走完他负责投递的所有街道，最后再返回邮局，应如何选择投递路线，才能使所走的路线最短？邮路问题的图论描述：取一无向赋权连通图G=（V，E）E中的每一条边对应一条街道每条边的非负权l(e)=街道的长度V中某一个顶点为邮局，其余为街道的交叉点在G上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小第29页，共43页，编辑于2022年，星期五1、若G中的顶点均为偶点，即G中存在欧拉回路，则该回路过每条边一次且仅一次，此回路即为所求的投递路线邮路问题的图论描述：在无向连通赋权G=（V，E）上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小2、G中有奇点：不存在欧拉回路投递路线：至少有一街道要重复走一次或多次第30页，共43页，编辑于2022年，星期五即不存在每条街道走一次且只走一次的投递路线分析：重复边结论：选择最佳投递路线=选择重复边的权和最小的路线111111111第31页，共43页，编辑于2022年，星期五111111111111111111第32页，共43页，编辑于2022年，星期五反之，对邮路图G，对该链上的每一条边增加一条重复边111111111111111111投递路线欧拉图第33页，共43页，编辑于2022年，星期五结论：对任意一个含奇点的邮路图G，由于奇点的个数为偶数个，把每两个配成一对，由于G为连通图，每对奇点之间至少存在一条链，对该条链上的每一条边增加一条重复边，可得一欧拉图，该欧拉图对应一条投递路线寻找最佳投递路线方法：在原邮路图上增加一些重复边得一个欧拉图，在所得欧拉图上找出一条欧拉回路。计算重复边的权和，重复边权和最小欧拉回路既为所求的最佳投递路线管梅谷奇偶点图上作业法第34页，共43页，编辑于2022年，星期五奇偶点图上作业法：例：求解右图所示的邮路问题第一步：确定一个初始可行方案方法：检查图G中是否有奇点无奇点：，找出一条以v1为起点的欧拉回路，该回路就是最佳投递路线有奇点：图G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边，得一个欧拉图G1，由G1所确定的欧拉回路即为一个可行方案v2，v8，v4，v6G中有奇点：取v2到v4的一条链：v2v1v6v7v8v9v4取v6到v8的一条链：v6v1v2v3v4v9v8G243469544354第35页，共43页，编辑于2022年，星期五G1显然G1不是最佳方案G1是欧拉图，第二步：调整可行方案，使重复边权和下降重复边权和=若图中某条边有两条或多于两条的重复边同时去掉偶数条，G2使图中每一条边最多有一条重复边G2的重复边权和=24346954435步骤1、可得到重复边权和较小的欧拉图4G22434695443545121第36页，共43页，编辑于2022年，星期五24346954435G2是欧拉图，重复边权和=21G242、使图中每个初等圈重复边的 权和不大于该圈权和的一半9个初等圈24346954435G24G3G3是欧拉图，重复边权和=17第37页，共43页，编辑于2022年，星期五G32434695443546（1）v1v2v5v6v1167（2）v6v5v8v7v61410（3）v2v3v4v5v2244（4）v5v4v9v8v516G3的初等圈权和重复边权和13（5）v1v2v5v8v7v6v124G4243469544354第38页，共43页，编辑于2022年，星期五G42434695443547（1）v1v2v5v6v1164（2）v6v5v8v7v6144（3）v2v3v4v5v2248（4）v5v4v9v8v516G4的初等圈权和重复边权和11（5）v1v2v5v8v7v6v124（6）v2v3v4v9v8v5v2324（8）v6v5v4v9v8v7v6（7）v1v2v3v4v5v6v12811224（9）v1v2v3v4v9v8v7v6v1367G4是最佳方案第39页，共43页，编辑于2022年，星期五奇偶点图上作业法：第一步：确定一个初始可行方案方法：检查图G中是否有奇点。无奇点：，找出一条以v0为起点的欧拉回路，该回路就是最佳投递路线有奇点：图G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边第二步：调整可行方案，使重复边权和下降1、使图中每一条边最多有一条重复边若图中某条边有两条或多于两条的重复边，同时去掉偶数条2、使图中每个初等圈重复边的权和该圈权和的一半若图中某初等圈重复边的权和大于该圈权和的一半去掉圈中的重复边同时将圈中没有重复边的边加上重复边第40页，共43页，编辑于2022年，星期五2326154231223261542312第41页，共43页，编辑于2022年，星期五最佳投递路线：v0v3v0V4v3v4v5v3v2v523261542312v1v2v1v4v1v0第42页，共43页，编辑于2022年，星期五期末考试论文题目：请用所学的运筹学方法解决一个你在工作、学习、生活中所遇到的实际问题。（40分）要求：1、字数不少于400字。2、不能采用课堂、作业、教材上的原题。（说明：若出现两篇完全相同的论文，每篇各得一半分）第43页，共43页，编辑于2022年，星期五
