运筹学 北京邮电大学 课件ch7-1学习资料

运筹学

Operations

ResearchChapter7图与网络GraphandNetwork1.图的基本概念

BasicConceptsofGraph2.最小树问题MinimumSpanningTreeProblem3.最短路问题ShortestPathProblem

4.最大流问题MaximumFlowProblem4/8/2025ACBDCBA引例：哥尼斯堡七桥问题您能从A、B、C或D任意一点出发走遍7座桥并且每座桥只走一次最后回到原出发点吗？D4/8/2025图Ｇ可定义为点和边的集合，记作式中Ｖ是点的集合，Ｅ是边的集合。注意上面定义的图Ｇ区别于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连，如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网络图，记作Ｎ。图和网络分析的方法已广泛应用于物理、化学、控制论、信息论、计算机科学和经济管理等各个领域。4/8/2025v3e7e4e8e5e6e1e2e3v1v2v4v5例如图6－1，端点，关联边，相邻

若有边e可表示为e=[vi,vj],称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。例如图6－1，v2和v4是边e6的端点，反之边e6是点v2、v4的关联边。点v2、v4相邻；边e6与e5、e4j相邻。图6－1e2可记作：4/8/2025环，多重边，简单图

如果边e的两个端点相重，称该边为环。如图６－１中边e1为环。如果两个点之间多于一条，称为多重边，如图６－１中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5

次，奇点，偶点，孤立点

与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。图６－１中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。图的次一个图的次等于各点的次之和。4/8/2025

链、路、回路（圈）

图中有些点和边的交替序列对任意vi,t－1

和vit(2≤t≤k)均相邻，称μ从v0到vk的链。如果链中所有的顶点v0，v1，…，vk也不相同，这样的链称初等链（路）。如果链中各边e1,e2…,ek互不相同称为简单链。当v0与vk重合时称为回路（圈），如果边不重复称为简单回路（圈）v3e7e4e8e5e6e1e2e3v1v2v4v5图6－1中，μ1={v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v4}是一条链μ1中因顶点v3重复出现，不能称作路。4/8/2025是一条链也是一条路。是一条回路并且是简单回路。v3e7e4e8e5e6e1e2e3v1v2v4v5连通图若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。图6－1是连通图。μ3={v4,e7,v3,e3,v1,e2,v2,e6,v4}4/8/2025子图、支撑子图图G1={V1、E1}和图G2={V2，E2}如果称G1是G2的一个子图。若有则称G1是G2的一个支撑子图（部分图），图6-2（a）是图6-1的一个子图，图6-2（b）是图6-1的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。v3e7e6e1e2e3v1v2v4v5e4v3e8e5e6v2v4v5图6－2(a)v3e7e4e8e5e6e1e2e3v1v2v4v5图6－2(b)4/8/2025有向图如果图的每条边都有一个方向则称为有向图混合图

如何图G中部分边有方向则称为混合图①②③④⑤⑥有向图4/8/2025赋权图设图G＝（V，E），对G的每一条边(vi,vj)相应的有一条数w(vi,vj)(或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为赋权图。这里的权数可以是时间、费用、距离等，视不同背景代表不同的含义。①②③④⑤⑥910201571419256赋权图4/8/2025网络图在一个有向赋权图G中规定了一个起点（发点）和一个终点（收点），其余是中间点，这样的图称为网络。①②③④⑤⑥910201571419256⑦1130起点为v1终点为v7的一个网络图4/8/2025树、支撑树：无圈的连通图称为树；若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵支撑树。图6－2(a)、6－2(b)都不是树。想一想，为什么？图6－3(a)是一棵树，图6－3(b)是图6－1的一棵支撑树。v3e7e4e8e5e6e1e2e3v1v2v4v5v1v1图6－1图6－3(a)图6－3(b)v3e2e3v2v