《运筹学图与网络分析.ppt

第 八 章图 与 网 络 分 析 图的基本概念 最小树问题 中国邮路问题 网络最短路问题 网络最大流问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 几个图论问题 哥尼斯堡七空桥 中国邮路问题 球队间比赛问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 哥尼斯堡七空桥 哥尼斯堡七座桥问题是200年前数学家欧拉所研究的问题之一。 哥尼斯堡现名加里宁格勒，城中有小岛，周围有七座桥架立在波列格尔河上。 欧拉想：在城中散步时，能否每座桥只走一次，走遍所有的七座桥。 一笔画问题 图1 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 中国邮路问题 我国数学家管梅谷教授1962年首次提出，并给出了它的解法(奇偶点图上作业法)。 邮递员在送报刊信件时，从邮局出发，一般地每次都要走遍所负责的全部街道，任务完成后返回邮局。那么邮递员应该选择哪一条路线才能以尽可能少的路程走完所有的街道呢？ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 有A、B、C、D、E五支球队，他们之间的比赛情况可以用图表示出来。已知A队和其他各队都比赛过一次，B队和A、C队比赛过，D队和E、C队比赛过，E队和A、D队比赛过。 图2 图3 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 如果在比赛中： A胜E， B胜C， A胜D， C胜A， E胜D， A胜B， 注：本章所研究的图与平面几何中的图不 同，这里我们只关心图有几个点，点与点 之间有无连线，两条线有无公共顶点，点 与线是否有关联，至于连线的方式是直线 还是曲线，点与点的相对位置如何都是无 关紧要的。 图4 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 图的基本概念 若点与点之间的连线没有方向，称为边，由此构成的图为无向图。记为: G=（V，E）其中V是G的点的集合，E为G的边的集合，连接Vi，Vj的边记为[Vi，Vj]或[Vj，Vi] v1 v2 v3 v4 v5 v6 e2 e4 e5 e6 e7 e8 e1 e3 e9 e10 图是由点和点与点之间的连线组成。 若点与点之间的连线有方向，称为弧，由此构成的图为有向图。记为: D=（V，A），其中V是G的点的集合，A为G的弧的集合，一条方向为从Vi指向Vj的弧记为(Vi，Vj) v1 v3 v4 v5 v6 e2 e4 e5 e6 e7 e8 e1 e3 v2 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 相邻点：两点之间的边属于E 相邻边：如果两条边有一个公共端点 环：边的两个端点相同 多重边(平行边)：两个点之间有多于一条边(弧) 多重图: 无环但允许有多重边的图 简单图：无环且无多重边的图 注:在有向图中，如果两点之间有不同方向的两条弧，不是多重边 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 端点的次d(v)：点 v 作为端点的边的个数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的边， 孤立点：d(