第6章图的基本概念

运筹帷幄之中决胜千里之外图与网络分析GraphTheoryandNetworkAnalysis第六章图与网络分析图与网络的基本知识中国邮路问题最短路问题最大流问题本章主要内容：图的基本知识图论起源——哥尼斯堡七桥问题问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？结论：不能。每个结点关联的边数要均为偶数。BDACABCD一笔画问题图的基本知识环球旅行问题：图的基本知识环球旅行问题的解另一个著名的问题:中国邮路问题图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点(顶点)和边的集合，记作：其中:V——点集E——边集※

图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。图的基本知识(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。图的基本知识定义:图中的点用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)=|E|=m顶点数：n(G)=|V|=n无向边与无向图：若图中任一条边的端点无序，即(vi,vj)与(vj,vi)是同一条边，则称它为无向边，此时图称为无向图。有向图：若图中边(vi,vj)的端点是有序的，则称它是有向边（或弧），vi与vj分别称为这条有向边的始点和终点，相应的图称为有向图。有向图无向图图的基本知识无向图,有向图

环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。含多重边的图称为多重图。v3e7e4e8e5e6e1e2e3v1v2v4v5简单图多重图图的基本知识环多重边

完全图图的基本知识每一对顶点间都有边相连的无向简单图称为无向完全图；有向完全图是指每一对顶点间有且仅有一条有向边的简单图。完全图顶点数n与边数m间成立如下关系:m=n(n-1)/2

二部图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为二部图（偶图）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。图的基本知识

度，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的度（也叫做次），记作d(vi)。右图中d(v1)=4,d(v3)=5,d(v5)=1。度数为奇数的点称作奇点，度数为偶数的点称作偶点，度数为1的点称为悬挂点，度数为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的度:

一个图的度等于各点的度数之和，且图的基本知识图的基本知识v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3悬挂点孤立点悬挂边偶点奇点图的基本知识图中顶点度的性质定理1任何图中顶点度数的总和等于边数的2倍，即定理2任何图中度数为奇数的顶点必有偶数个。定义

在有向图中，以顶点v为始点的边数称为顶点v的出度，记为d+(v)；以v为终点的边数称为v的入度，记为

d-(v)。顶点v的出度与入度的和称为点v的度。

子图，生成子图(支撑子图)v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（图G）图的基本知识定义

图G=(V,E),若E'是E的子集，若V'是V的子集，且E'中的边仅与V'中的顶点相关联，则称G'=(V',E')为图G的一个子图，特别地，若V'=V,则称G'为G的一个生成子图（支撑子图）。

网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权，赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥910201571419256图的基本知识

路径，圈，连通图定义

无向图中一个点、边交错的序列，序列中的第一个和最后一个元素都是点，若其中每条边以序列中位于它之前和之后的点为端点，则称这个点边序列为图中连接其第一个点与最后一个点的链（途径）。链中所含的边数称为链长。图的基本知识链，但只是迹而非路迹：没有重复边；路径：既无重复边也无重复点。对有向图可类似定义链（各边方向一致）。路径，圈，连通图定义

若在无向图中，一条链的第一个点与最后一个点重合，则称这条链为闭链。只有重复点而无重复边的闭链为闭迹（或回路），既无重复点又无重复边的闭链为圈。图的基本知识圈闭链图的基本知识链（途径,walk）闭链迹（trail）闭迹（回路）路径（path）圈有向图：道路(边的方向一致)

连通图图的基本知识定义

一个图中任意两点间至少有一条链相连（或等价的说有一条路相连），则称此图为连通图。任何一个不连通图总可以分为若干个连通子图，每个连通子图称为原图的一个分图（连通分支）。连通图非连通图图的基本知识图的矩阵表示：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵 对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中图的基本知识v5v1v2v3v4v64332256437例6.1下图所表示的图可以构造邻接矩阵A如下对于赋权图G=(V,E)，其中边有权,构造矩阵B=(bij)nn

其中：图的基本知识2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有nm矩阵M=(mij)nm，其中:3.权矩阵图的基本知识101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例6.2下图所表示的图可以构造邻接矩阵M如下:M=（mij）=图的基本知识v5v1v2v3v4v64332256437例6.3下图所表示的图可以构造权矩阵B如下:欧拉回路定义

连通图G中，若存在一条迹，经过每边一次且仅一次，则称这条道路为欧拉迹。若存在一条回路经过每边一次也仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图（E图）。欧拉回路推论1无向连通图G为欧拉图，当且仅当G的边集可以划分为若干个圈。推论2无向连通图G中有欧拉迹，当且仅当G中恰好有两个奇点。定理3无向连通图G是欧拉图，当且仅当G中无奇点。图的同构图的同构例：例：图的同构例：图的同构有向图例：abcde2(a)1(b)3(d)4(c)5(e)图的同构例：(1)画出4个顶点3条边的所有可能非同构的无向简单图。(2)画出3个顶点2条边的所有可能非同构的有向简单图。•

(1)(2)图的同构中国邮路问题一个邮递员，负责某一地区的信件投递，他每天要走邮局出发，走遍该地区所有街道，再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？用图论的语言描述就是：给定一个连通图G，每边有非负权l(e)，要求一条闭链过每边至少一次，且满足总权最小。中国邮路问题解法（1）若G是欧拉图，则按欧拉回路走，就是满足要求的经过每边至少一次且总权最小的走法。abcdef若G中有奇点，则G不是欧拉图，因此要连续地走过每边至少一次，则必然有某些边不止一次走过。这相当于在G中添加一些重复的边，使得到的新图G*没有奇点且满足总路程最短。中国邮路问题解法（2）abcdefabcdef对增加了重复边后得到的新图G*，很明显其总权的大小取决于增加的重复边权的大小。因此中国邮路问题转化为如下问题：在连通图G=(V,E)中，求一个边的集合E1E，将E1中所有边都变成重复边得到新图G*，使得G*中无奇点，且最小中国邮路问题解法（3）上述问题的解决依赖于以下结果：定理4已知图G*=G+E1无奇点，则最小的充分必要条件为：（1）每条边最多重复一次；（2）对图G中的每个圈来说，重复边的长度不超过圈长的一半。中国邮路问题解法（4）下面直观地说明，若定理5的条件不成立，则可以得到总权比E1的更小的重复边集。122254122254重复两次或以上的去掉其中两条将原来的重复边变成非重复边，原来的非重复边变成重复边中国邮路问题解法（5）解法第一步：确定初始可行方案。若图中没有奇点，则它已经是欧拉图，按欧拉回路走即可。否则，若有奇点，奇点必有偶数个，将奇点两两配对，然后找出每对奇点间的一条道路，将此道路中的每条边都变成重复边。524363459444l12+2l23+2l36+l89+2l78+l69+l14+2l47=51中国邮路问题解法（6）524363459444第二步：调整可行方案。使重复边最多重复一次524363459444l12+l69+l14+l98=21中国邮路问题解法（7）524363459444第三步：检查图中每个圈是否满足定理条件（2），若不满足则进行调整。524363459444524363459444第三步要求检查每个圈，这一步可能是相当繁琐的。例如上例中的图就包括下图所示的圈。中国邮路问题解法（8）

“巧渡河”问题问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能架船。图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。起始状态是“人狼羊菜”，结束状态是“空”。问题的解：找到一条从起始状态到结束状态的