资源描述：
《运筹学图论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹帷幄之中决胜千里之外图与网络分析GraphTheoryandNetworkAnalysis第八章7/29/2021图与网络分析图与网络的基本知识树和最小支撑树最短路问题最大流问题最小费用流问题中国邮路问题本章主要内容：7/29/2021§1图与网络的基本知识图论起源——哥尼斯堡七桥问题问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？结论：不能。每个结点关联的边数要均为偶数。BDACABCD一笔画问题7/29/2021环球旅行问题：7/29/2021环球旅行问题的解另一个著名的问题:中国邮路问题7/29/2021图
2、论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点(顶点)和边的集合，记作：其中:V——点集E——边集※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。7/29/2021(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与
3、几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。7/29/2021又如：我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。石家庄太原北京天津塘沽济南青岛徐州连云港南京上海郑州武汉重庆7/29/2021再如：有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用如下所示的有向图反
4、映出来v3v5v2v4v6v17/29/2021定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6,e7,e8}，边数：m(G)=
5、E
6、=m顶点数：n
7、(G)=
8、V
9、=n7/29/2021无向边与无向图：若图中任一条边的端点无序，即(vi,vj)与(vj,vi)是同一条边，则称它为无向边，此时图称为无向图。有向图：若图中边(vi,vj)的端点是有序的，则称它是有向边（或弧），vi与vj分别称为这条有向边的始点和终点，相应的图称为有向图。有向图无向图无向图,有向图7/29/2021环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。含多重边的图称为多重图。v3e7e4e8e5e6e1e2e3v1
10、v2v4v5简单图多重图环多重边7/29/2021完全图每一对顶点间都有边相连的无向简单图称为无向完全图；有向完全图是指每一对顶点间有且仅有一条有向边的简单图。完全图顶点数n与边数m间成立如下关系:m=n(n-1)/27/29/2021二部图（偶图）图G=(V,E)的点集V可以分为两个非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为二部图（偶图）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。7/29/2021
11、次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。7/29/2021v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3悬挂点孤立点悬挂边偶点奇点7/29/2021图中顶点次的性质定理1任何图中顶点次数的总和等于边数的2倍。定理2任何图中次为奇数的顶点必有偶数个。
12、定义在有向图中，以顶点v为始点的边数称为顶点v的出次，记为d+(v)；以v为终点
