图与网络分析剖析课件.ppt

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

1、运筹学OPERATIONSRESEARCH2021/9/81§1．图的基本概念与模型§2．树图和图的最小部分树§3．最短路问题§4．网络的最大流第六章图与网络分析（图论）GraphTheoryandNetworkAnalysis2021/9/82图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。对于科学研究、市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解

2、决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。引言2021/9/83图论起源于一些游戏，最有代表性的是所谓的“七桥问题”，即一笔画问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。2021/9/84BACD当地的居民热衷于这样一个问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。大家

3、都没有成功，但不知道为什么。哥尼斯堡的七桥问题2021/9/85为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。这就是著名的Euler问题。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出。（每个结点关联的边数要均为偶数）。欧拉的论文题目是“依据几何位置的解题方法”，欧拉被公认为图论的创始人。这就是古典图论中的第一个著名问题。BACD2021/9/86ACDB简捷表示事物之间的本质联系，归纳事物之间的一般

4、规律。2021/9/871857年，英国数学家哈密尔顿发明了一种游戏：给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（注意：并不要求经过每条边，要求经过每一顶点）。也称旅行者“环球旅行问题”或哈密尔顿（Hamilton）回路。哈密尔顿（Hamilton）回路2021/9/88环球旅行问题：2021/9/892021/9/8102021/9/8112021/9/8122021/9/8132021/9/8142021/9/8152021/9/8162021/9/8172

5、021/9/8182021/9/8192021/9/8202021/9/8212021/9/8222021/9/8232021/9/8242021/9/8252021/9/826环球旅行问题的另一解2021/9/827注意：欧拉回路：经过边一次，没有说顶点；（顶点没有要求，但可以理解为：顶点可以多次，而且必须经过每一个顶点，因为经过边必须经过顶点）哈密尔顿回路：经过顶点一次，没有说边。（边没有要求，不过可以理解为：边经过一次或者可以不经过）2021/9/828情侣问题：已知有M个男士，N个女士。每个男（女）士都对一些女（男）士倾慕，现问在这群人士中如何搭配，使

6、较多的有情人终成眷属。城市交通改善问题：随着私家车的不断出现，城市交通状况越来越拥挤，虽然城市在不断改善，但堵车现象仍然越来越多，出行难已成为一个社会问题。假设你是该城市的交通局长，在投资最少（或有限）的条件下应采用何种方法使交通状况得到好转。（交通网络不做大的变化）（应从交通瓶颈入手）另外，这一时期，还有许多，诸如迷宫问题、博弈问题、棋盘上马的行走路线等问题，吸引了许多学者，这些看起来无足轻重的游戏引出了许多有实际意义的新问题，开辟了新的学科。2021/9/829在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例：

7、有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。v3v1v2v4v6v52021/9/830§6.1图的基本概念与模型图（graph）是由一些结点或顶点（nodesorvertices）以及连接点的边（edges）构成。记做G={V,E}，其中V是顶点的集合，E是边的集合。一、基本概念给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图），记作N。2021/9/831图中的点用v表

8、示，边用e表示，对每条边可用它所联结的