运输配送图与网络分析（1）ppt课件

图与网络分析F问题提出应用：生产组织，邮递员问题，通讯网络等。哥尼斯堡七桥问题ABC DF哥尼斯堡七桥问题在图中找一条经过每边一次且仅一次的路 欧拉回路。 ADBC由点和边组成F“环球旅行 ”问题在图中找一条经过每个点一次且仅一次的路 哈密尔顿回路。F“中国邮路问题 ”在图中找一条经过每边的最短路 类似带权的欧拉回路。F“货郎担问题 ”在图中找一条经过每个点一次且仅一次的最短路 带权的哈密尔顿回路。在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例 1:图 1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。一、图与网络的基本知识太原重庆 武汉 南京徐州 连云港上海郑州石家庄 塘沽青岛济南天津北京图 1例 2:有六支球队进行足球比赛，我们分别用点 v1v 6表示这六支球队。它们之间的比赛情况，也可以用图反映出来，已知 v1队战胜 v2队， v2队战胜 v3队， v3队战胜 v5队，如此等等。这个胜负情况，可以用图 2所示的有向图反映出来。v3v1v2 v4v6v5图 2一、图与网络的基本知识1.图的基本概念例 1: 铁路交通图例 2: 球队比赛图F点 : 表示研究对象 .F连线：表示两个对象之间的某种特定关系。F关系的对称性：两对象之间的关系可互换。F边：不带箭头的联线，表示对称关系。F弧：带箭头的联线，表示不对称关系。F无向图：简称图，由点和边组成。表示为： G=（ V， E）V-点集合 E-边集合例：右图V=v1， v2， v3， v4E=e1， e2， ,e7e1=v1,v2e2=v1,v2,e7=v4,v4F 有向图：由点和弧组成。表示为： D=（ V， A）V-点集合 A-弧集合F点数 : p(G) 或 p(D)F边数 : q(G)F弧数 :q(D) v1v2 v3v4v5例：右图V=v1， v2,v5A=a1， a2,a7a1=v1,v5,a2=v5,v4,a7=v1,v4无向图的有关概念F端点 : e=u,vE, 则 u,v是 e的端点 , 称 u,v相邻 .F关联边 : e是点 u,v的关联边 .F环 : 若 u=v, e是环 .F多重边 : 两点之间多于一条边 .F简单图 : 无环 ,无多重边的图 .F多重图 : 无环 ,允许有多重边的图 .F次 : 以点 v为端点的边的个数称为 v的次 . 表示为 : d(v)F悬挂点 : 次为 1的点 .F悬挂边 : 悬挂点的关联边 .F孤立点 : 次为 0的点 .F奇点 : 次为奇数的点 .F偶点 : 次为偶数的点 .孤立点悬挂边F定理 1: 图 G=(V,E)中 ,所有点的次之和是边数的两倍 , 即 :F定理 2: 任意一图中 , 奇点的个数为偶数 .证明 :设 V1-奇点的集合 ,V2-偶点的集合偶数 偶数偶数一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是 树 。树在自然科学和社会科学 ,特别是在计算机科学领域中有广泛的应用。例：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。第二节 树v6v3v4v2v5v1 六个城市的一个电话网就作成一个图。这个图必须是连通图。这个图必须是无圈的。图是一个不含圈的连通图，代表了一个电话线网。再比如，乒乓球单打比赛抽签后的对阵形式以及企业的组织结构图等。A B C D E F G H总经理市场总监常务副总经理学术总监市场总学术总教质部研发部人事部第二节 树二、图的生成（支撑）树定义 15 设图 K=(V,E )是图 G=(V,E)的一生成（支撑）子图 ,如果图 K=(V,E )是一个树 ,那么称 K是 G的一个生成树。G中属于生成树的边称为树枝，不在生成树上的边称为弦。例如 ,图 3b 是图 3a 的一个生成树。 图 3v6v5v2v3v4v1av6v5v2v3v4v1b显然，如果图 K=( V, E )是图 G=(V, E)的一个 生成 树，那么 K 的边数是 n(G)-1， G中不属于 生成 树 K的边数是 m(G)-n(G)+1。第二节 树图的生成树的求法 1：定理 7充分性的证明，提供了一个寻找连通图 生成 树的方法 ,叫做 “ 破圈法 ” 。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个 生成 树。例 :用破圈法求下图的一个 生成 树。V5V4V2V3V1e6e5e4e3e2e1 e7e8第二节 树圈 (v1,v2,v3,v1)去 e3 ；圈 ( v1,v2,v4,v3,v1 )去 e4 ；圈 ( v3,v4 v5,v3 )去 e6 ；圈 ( v1,v2,v5,v4,v3,v1 )去 e7； 得到生成树，如图所示。v2e1e2 e5e8v1v3v4图 8-12V5V4V2V3V1e6e5e4e3e2e1 e7e8第二节 树三、最小生成树问题定义 16 连通图 G =（ V， E）， 每条边上有非负权 L(e)。 一棵生成树所有树枝上权的总和，称为这个 生成树的权 。具有最小权的生成树称为 最小生成树 （最小支撑树），简称最小树。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度、费用、流量等等。如前所述，在已知的几个城市之间联结电话线网，要求总长度最短或总建设费用最少，这个问题的解决可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。第二节 树求最小生成树的常用方法有 破圈法 ： 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； 去掉该圈中权数最大的边； 反复重复 两步，直到得到最小生成树。例 5 某六个城市之间的道路网如图4a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。v6v5v2v3v4图 4av1627535441第二节 树解：这个问题就是求赋权图的最小支撑树。用破圈法求解。v3v2v1v4v6v553142图 8.13bv6v5v2v3v4图 8.13av1627535441第二节 树课堂练习第二节 树主页主页小岛 A 小岛 B欧拉 （ Leonhard Euler 公元 1707-1783年） 判断下列图形能否一笔画图 1图 5图 4图 3图 2不连通的图形不能一笔画 连通的图形 有可能 一笔画 观察下列图形，完成统计表 图 7图 5图 1图 8图 6图 4图 3图 2可以一笔画的图形 不能一笔画的图形 图 形序号奇点个数 偶点个数图 形序号奇点个数 偶点个数不连通的图形不能一笔画 连通的图形 有可能一笔画 全都是偶点的连通图可以一笔画 奇点个数超过两个的连通图形不能一笔画 画时以任一点为起点，最后仍回到该点 画时以一个奇点为起点，另一个奇点为终点有两个奇点的连通图可以一笔画 你能笔尖不离纸，一笔画出图中的每个图形吗？ 判断下列图形能否一笔画图 5图 4图 3图 2 图 6图 1下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入口应