《运筹学教程》胡云权第五版第五章图与网络分析

《《运筹学教程》胡云权第五版第五章图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图论与网络分析图的基本概念最小支撑树问题最短路径问题学习目标ABCDACBD图论起源——哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？图的基本概念哈密尔顿回路问题：环球旅行遊戏欧拉回路：每边经过一次且仅一次的回路哈密尔顿回路：每个点经过一次且仅一次的回路问题：游戏者从任一城市出发，寻找一条可经过每个城市一次且仅一次，在回到原出发点的路?图的基本概念123456789101112131415161718192

2、0定义1：由点和边组成，记作G=(V，E)，其中V={v1，v2，……，vn}为结点的集合，E={e1，e2，……，em}为边的集合。点表示研究对象边表示表示研究对象之间的特定关系1.图图的基本概念注意：上面定义的图Ｇ区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。V、E为有限集合，则为有限图，反之无限图。v3e7e4e8e5e6e1e2e3v1v2v4v5【例】图5－1，边e=[vi，vj]，称vi和vj是边e的端点，vi和vj

3、两点相邻；边ex和ey有公共端点vi，称边ex和ey相邻，边ex和ey为点vi的关联边；v2和v4是边e6的端点，点v2、v4相邻。e6与e7共用顶点v4，e6与e7相邻，e6和e7为点v4的关联边。图5－1e6可记作：图的基本概念端点，相邻，关联边图的基本概念v3e7e4e8e5e6e1e2e3v1v2v4v5图5－1环，多重边，简单图一条边的两个端点相同，称此边为环，e1；两个点之间多于一条，称为多重边，e4和e52、图的分类定义2：无环、无多重边的图称作简单图。含有多重边的图为多重图。图无向图，

4、记作G=(V，E)有向图，记作D=(V，A)例1：哥尼斯堡桥问题的图为一个无向图。有向图的边称为弧。例2：五个球队的比赛情况，v1v2表示v1胜v2。v1v2v3v4v52、图的分类图的基本概念图的基本概念定义3：每一对顶点间都有边相连的无向简单图，称为完全图。有n个顶点的无向完全图记为Kn。2、图的分类定义4：图G=(V,E)的点集V可分为两个非空子集X、Y，即X∪Y=V，X∩Y=∅，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图（偶图），有时记作G=(X,Y,E)。图

5、的基本概念3、顶点的次定义5：以点v为端点的边数叫点v的次（degree），记作deg(v)或d(v)。v3e7e4e8e5e6e1e2e3v1v2v4v5图5－1图5-1中，d(v1)＝４，d(v3)=5，d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。次为1的点称作悬挂点，连接悬挂点的边为悬挂边。图的次：各点的次之和。有向图中顶点的次？定理1：任何图中，顶点次数的总和等于边数的2倍。定理2：任何图中，次为奇数的顶点为偶数个。4、子图、支撑子图图G=(V,E)和G’

6、=(V’,E’)，若V’V，E‘E，则称G’为G的子图。特别地，若V=V‘且E’E，则称G'为G的支撑子图。G2为G1的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2图的基本概念5、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。55.5v1v2v3v4v53.57.5423图的基本概念v1v2v3v4v56、链与路、圈与回路链点边交错的序列圈起点=终点的链路点弧交错的序列回路起点=终点的路v1v2v3v4v5无向图：有向图：图的基本概念没有重复点

7、和重复边的链为初等链。初等圈7、连通图定义10：任意两点之间至少存在一条链的图称为连通图，否则称为不连通图。G1G2G1为不连通图，G2为连通图例：图的基本概念图的基本概念8、图的矩阵表示定义11：网络G=(V,E)，边（vi，vj）有权wij，构造矩阵A=(aij)n×n，其中：则称矩阵A为网络G的权矩阵。（vi，vj）∈E其他图的基本概念8、图的矩阵表示定义12：图G=(V,E)，

8、V

9、=n，构造一个矩阵A=(aij)n×n，其中：则称矩阵A为图G的邻接矩阵。（vi，vj）∈E其他树支撑树最小支撑

10、树【例】今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531最小支撑树问题1、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。3、边数=顶点数–1。1、树连通且无圈的无向图(A)(B)(C)树的性质：判断下面图形哪