图论与网络规划课件.ppt

《图论与网络规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章图论与网络优化1图的基本概念2最小树问题3最短路问题4网络最大流问题5最小费用最大流问题一些问题图论中著名问题.1736年，图论的创始人Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文.例：七桥问题ABCD问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。例：四色猜想能否用四种颜色给地图染色，使相邻的国家有不同的颜色。点：国家；边：两个国家有公共边界。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。公元1852年，格里斯发现无论多么复杂的地图，只要用四

2、种颜色就能将相邻的区域区分开来，这就是所谓“四色猜想”。直到公元1976年，才由美国数学家同时操作三台超大型汁算机作了近200亿个逻辑判断，花费1200个机时，才取得了“四色猜想”的证明。例：Hamilton图游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。公元1859年，哈密尔顿(Hamilton)在给朋友格拉伍斯（Grares）的信中提出了这个游戏。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。例：中国邮路问题一个邮递员送信，要走完他所负责的

3、全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。点：路口；边：两路口之间道路，第i条道路长ei。1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。例：有甲、乙、丙、丁、戊五个球队，各队之间比赛情况如表：点：球队；连线：两个球队之间比赛过，如甲胜乙，用v1v2表示。v1v2v3v4v5点：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路口之间道路、两国边界、两球队比赛及结果)。对称关系：桥、道路、边界；用

4、不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。图：点及边（或弧）组成。实际生活中，人们经常用“图”来表示一些对象以及这些对象之间的特定关系。如公路或铁路交通图、管网图、通讯联络图等。对所要研究的问题确定具体对象及这些对象间的性质关系，并用图的形式表示出来，这就是对所研究原问题建立的模型。图是反映对象之间关系的一种工具。这里所研究的图与平面几何中的图不同。这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。是组合意义下的图。图的理论和方法，就是从形

5、形色色的具体的图以及与它们相关的实际问题中，抽象出共同性的东西，找出其规律、性质、方法，再应用到解决实际问题中去。图论(GraphTheory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。随着电子计算机的蓬勃发展，图论不仅得到了迅速发展，而且应用非常广泛。它直观清晰，使用方便，易于掌握。应用领域：物理学、化学、控制论、信息论、管理科学、通信系统、交通运输系统、建筑、计算机科学、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。网络规划是图论与线性规划的交叉学科,具有广泛的应用背景，比如，最短路问题

6、、最小树问题、最大流问题、最优匹配问题等.10.1图的基本概念一个图(Graph)定义为三元有序组G=(V(G),E(G),G)，V(G)是图的顶点集合，E(G)是图的边集合，G称为顶点与边之间的关联函数。V(G)中的元素vi称为顶点,E(G)中的元素ek称为边.一个图习惯记作G=(V,E).当V,E为有限集合时，G称为有限图，否则，称为无限图.我们只讨论有限图.一、基本概念１.图设G是一个图，G=(V(G),E(G))，则称e连接u和v，称u和v是e的端点.若称端点u，v与边e是关联的，称两个顶点u，v是邻接（相邻）的.两条边e,e1

7、有公共端点v，则称e,e1相邻.一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质.uvewe1设G是一个图，G的几何实现其中：例说明一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点,图形的线为边.图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。在一个图的几何实现中，两条边的交点可能不是图

8、的顶点。例如有时也用m(G)=

9、E

10、表示图G中的边数，用n(G)=

11、V

12、表示图G中的顶点个数，简记为m,n.图G中的点数记为p(G)，边数记为q(G).在不引起混淆的情况下，简记