运筹学课件(1) 第6部分 图论——xs.ppt

《运筹学课件(1) 第6部分 图论——xs.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6部分图与网络分析6-1图的基本概念6-3最短路问题6-4最大流问题6-2树第6部分图与网络分析图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理

2、论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接。当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图6.1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点

3、。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。哥尼斯堡七桥问题ABCD现名加里宁格勒普雷格尔河系欧拉——中华一笔画问题回路问题ABCD新河旧河大河哥尼斯堡——18世纪为东普鲁士首府Ⅱ战后划归苏联充要条件：图中无奇点日常生活中，随处可见图的例子（1）地图上的铁路网（中学课本中）（旅游各个城市如何最快或路线最短）；例6-1:图6.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管

4、道图，民用航空线图等等。太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京图6.2（2）球队比赛（学校组织篮球或足球比赛，表示球队之间的比赛关系）；例6-2：有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来。v1v3v2v4v6v5图6.3（3）药品存放；（4）互相握手；（5）研究生选课或考试安排。从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生

5、活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。几种药品，有些药品不可以放在同一个仓库中，把药品用点表示，不能放在一起的药品之间用直线连起来一、图1、图：由点及点之间的连线（不带箭头或带箭头）所组成。2、无向图：由点及不带箭头的连线构成，记作G（V，E）V：点的集合，V={v1,v2,…,vn}E：边的集合，E={eij}vi，vj之间

6、的边记为e=［vi，vj］或［vj，vi］3、有向图：由点及带箭头的连线构成，记作D（V，A）V：点的集合，V={v1,v2,…,vn}A：弧的集合，A={aij}vi，vj之间的弧记为a=（vi，vj），而不能记作（vj，vi），4、点数：记为p（G）或p（D）边数：记为q（G）或q（D）vi称为a的始点，vj称为a的终点a2v3v1v2v4v5v6v7a1a8a4a5a6a9a7a10a3a11图6.4二、无向图的相关概念1、端点：对于边e=［vi，vj］∈E，vi，vj是e的端点关联边：e是vi，vj的关联边相邻：vi，vj是相邻的。2、环：

7、两个端点相同的边称为环多重边：两个端点之间有多于一条的边，称这些边为多重边简单图：一个无环，无多重边的图，称为简单图多重图：一个无环，但允许有多重边的图3、次：以v为端点的边的个数，称为v的次，记作d(v)悬挂点：次为1的点悬挂边：悬挂点的关联边孤立点：次为零的点奇点：次为奇数的点偶点：次为偶数的点e2v2e1v1v4e5e3e6e4e7v5e8v3图6.5v6二、无向图的相关概念4、有关次的两个定理（1）图G（V，E）中，所有点的次之和是边数的两倍，即（2）任一个图，奇点的个数为偶数。V1，V2分别为G中奇点和偶点的集合e2v2e1v1v4e5e

8、3e6e4e7v5e8v3图6.4二、无向图的相关概念5、链：对于图G（V，E），一个点边的交错序列（t=1，2，……，k