《运输配送图与网络分析（1）ppt课件》由会员分享，可在线阅读，更多相关《运输配送图与网络分析（1）ppt课件（39页珍藏版）》请在金锄头文库上搜索。
1、图与网络分析,问题提出 应用：生产组织，邮递员问题，通讯网络等。 哥尼斯堡七桥问题,哥尼斯堡七桥问题 在图中找一条经过每边一次且仅一次的路欧拉回路。,由点和边组成,“环球旅行”问题 在图中找一条经过每个点一次且仅一次的路哈密尔顿回路。,“中国邮路问题” 在图中找一条经过每边的最短路类似带权的欧拉回路。,“货郎担问题” 在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例1:图1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。,一
2、、图与网络的基本知识,例2:有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队。它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图2所示的有向图反映出来。,一、图与网络的基本知识,1.图的基本概念,例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关系。 关系的对称性：两对象之间的关系可互换。,边：不带箭头的联线，表示对称关系。 弧：带箭头的联线，表示不对称关系。 无向图：简称图，由点和边组成。 表示为： G=（V，E） V-点集合 E-边集合 例：右图,V=
3、v1，v2，v3，v4 E=e1，e2，,e7 e1=v1,v2e2=v1,v2, ,e7=v4,v4,有向图：由点和弧组成。表示为： D=（V，A） V-点集合 A-弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数:q(D),例：右图 V=v1，v2,v5 A=a1，a2,a7 a1=v1,v5,a2=v5,v4,a7=v1,v4,无向图的有关概念,端点: e=u,vE, 则u,v是e的端点, 称u,v相邻. 关联边: e是点u,v的关联边. 环: 若u=v, e是环. 多重边: 两点之间多于一条边. 简单图: 无环,无多重边的图. 多重图: 无环,允许有多重边的图.,次: 以
4、点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点. 奇点: 次为奇数的点. 偶点: 次为偶数的点.,孤立点,悬挂边,定理1: 图G=(V,E)中,所有点的次之和是边数的两倍, 即:,定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1-奇点的集合, V2-偶点的集合,偶数,偶数,偶数,一、树及其性质 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。树在自然科学和社会科学,特别是在计算机科学领域中有广泛的应用。 例：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电
5、话线的总长度最短。,第二节 树,六个城市的一个电话网就作成一个图。 这个图必须是连通图。 这个图必须是无圈的。 图是一个不含圈的连通图，代表了一个电话线网。,再比如，乒乓球单打比赛抽签后的对阵形式以及企业的组织结构图等。,第二节 树,二、图的生成（支撑）树 定义15 设图K=(V,E)是图G=(V,E)的一生成（支撑）子图,如果图K=(V,E)是一个树,那么称K是G的一个生成树。 G中属于生成树的边称为树枝，不在生成树上的边称为弦。例如,图3b 是图3a 的一个生成树。,显然，如果图K=( V, E )是图G=(V, E)的一个生成树，那么K 的边数是n(G)-1，G中不属于生成树K的边数是m
6、(G)-n(G)+1。,第二节 树,图的生成树的求法1： 定理7充分性的证明，提供了一个寻找连通图生成树的方法,叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个生成树。 例:用破圈法求下图的一个生成树。,第二节 树,圈(v1,v2,v3,v1)去e3 ； 圈( v1,v2,v4,v3,v1 )去e4 ； 圈( v3,v4 v5,v3 )去e6 ； 圈( v1,v2,v5,v4,v3,v1 )去e7； 得到生成树，如图所示。,第二节 树,三、最小生成树问题 定义16 连通图G =（V，E），每条边上有非负权L(e)。一棵生成树所有树枝上
7、权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树（最小支撑树），简称最小树。 这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度、费用、流量等等。 如前所述，在已知的几个城市之间联结电话线网，要求总长度最短或总建设费用最少，这个问题的解决可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。,第二节 树,求最小生成树的常用方法有破圈法： 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； 去掉该圈中权数最大的边； 反复重复 两步，直到得到最小生成树。,例5 某六个城市之间的道路网如图4a所示，要求沿着
8、已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。,第二节 树,解：这个问题就是求赋权图的最小支撑树。用破圈法求解。,第二节 树,课堂练习,第二节 树,主页,小岛A,小岛B,欧拉,（Leonhard Euler 公元1707-1783年）,判断下列图形能否一笔画,不连通的图形不能一笔画,连通的图形有可能一笔画,观察下列图形，完成统计表,图6,可以一笔画的图形,不能一笔画的图形,不连通的图形不能一笔画,连通的图形有可能一笔画,全都是偶点的连通图可以一笔画,奇点个数超过两个的连通图形不能一笔画,画时以任一点为起点，最后仍回到该点,画时以一个奇点为起点，另一个奇点为终点,有两个奇点的连通
9、图可以一笔画,你能笔尖不离纸，一笔画出图中的每个图形吗？,判断下列图形能否一笔画,图2,下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入口应设在哪儿？,甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C）。如果要选择最短的线路，谁先回到邮局？,主页,二、 奇偶点图上作业法 （1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。 （2）如果边e=（u,v）上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部
10、都是偶顶点。 （3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。,判定标准1: 在最优邮递路线上，图中的每一条边至多有一条重复边。 判定标准2 : 在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。,图1,求解步骤： 1、在线性图中，添加弧（即双线条），使得到的新图上没有奇点，如图2所示。 （注意：如果邮递员走遍所有的路段，则路线图上所有的点都必须变成偶点，每一个点至少有一进一出。）,图2,2、调整添弧，使每个圈的添弧总长度不大于圈总长度的一半。,图3,总长度为6，而添弧总长度为5，所以去掉原来的添弧B-H,H-I和C-I,在该圈未添弧的路段B-C上添弧。,总长度为8，而添弧总长度为5，所以去掉原来的添弧I-K,I-M,在该圈未添弧的路段K-N,M-N上添弧。,图4,图5,3、最优解：在图5中，所有的圈的添弧部分的长度都不超过整圈长度的一半，所以它构成一个最优解。,设L点为邮局，则可以一笔画出邮递员送信的最短路径如图6所示。,图6,课堂作业：求解下图所示网络的中国邮路问题，图中数字为该边的长。,
