图与网络分析课件.pptVIP

第一节图的基本概念与模型近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。K?nigsberg桥对应的图

一、图基本概念例1、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。V5ee54e6V4V1ee73e1V2e2V3

例2某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况可以用点V,V,……V分别代表这八128种药品，若药品Vi和药品Vj是不能存放在同一个库房的，则在V和V之间连一条线。ijV?V32??V4?V5?V6?V1?·V8?V7

一般地，当用图论研究一个实际问题时，常以顶点（Vertex）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线称为边（Edge），目的是为了解决某个极值问题。图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];图的表示方法：

运筹学中研究的图具有下列特征:强调点与点之间的关联关系，不讲究图的比例大小与形状；每条边上赋有一个权；建立网络模型，求最大值或最小值。

下图可以提出很多极值问题274231866731356316647

二、关于图的另外一些名称和术语：端点,关联边,相邻e1v1e3若有边e可表示为e=[v,v]，称v和vijije2e4e5e7是边e的端点，反之称边e为点v或vjiv2v3e8的关联边。若点v、v与同一条边关ij联，称点v和v相邻；若边e和e具e6ijij有公共的端点，称边e和e相邻。ijv4v5

e1环,多重边,简单图v1e3e2如果边e的两个端点相重，称该边为e4v2v3环。如右图中边e为环。如果两个点1e5之间多于一条，称为多重边，如右图ee6中的e和e，对无环、无多重边的图8e745称作简单图。v4v5

e1次，奇点，偶点，孤立点v1e3e2e与某一个点v相关联的边的数目称为4iv2v3e8点v的次（也叫做度），记作d(v)。iie5右图中d(v)＝４,d(v)=5,d(v)=1。次135e6为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。e7v4v5图的次:一个图的次等于各点的次之和。

定理1任何图中，顶点次数之和等于所有边数的2倍。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：2m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。

链，圈，连通图e1图中某些点和边的交替序列，若其v1e3e2中各边互不相同，且对任意v和vite4e5e7i,t-1均相邻称为链。用μ表示：v2v3e6e8起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。vv45

e1子图，部分图(支撑子图)v1e3e2图G={V、E}和图G={V，E}如果有e4e5111222v称G是G的一个子图。v2312若有，则称G是G的一12e6e8v5个部分图(支撑子图)。v1e7ee23e4e4v2v3e8v2v3e8v4e5（G图）e6e6e7v4v5v4v5(b)(a)

网络（赋权图）赋权图）:权可以代表距离、费用、通过能力(容量)等等。无向网络:端点无序的赋权图称为.有向网络:端点有序的赋权图称为。②15⑤⑥7149④10①6192025③

图的矩阵描述：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有n?n阶方矩阵A=(a)，其中ijn?n

图的基本概念与模型例6.2下图所表示的图可以构造邻接矩阵A如下v1v242367v63v34352v4v5

2.权矩阵对于赋权图G=(V,E),其中边有权,构造矩阵B=(b)ijn?n其中：

例6.4下图所表示的图可以构造权矩阵B如下:v1v242367v63v34352v4v5

简单图环顶点数p边数q重合端点矩阵表示A邻接矩阵B关联矩阵多重边G=(V,E)边e=[u,v]含平行边多重图点的次子图01奇数偶数点边关系子生图成子孤悬奇偶立挂点点点点各种链的概念图

欧拉图与中国邮路问题欧拉图哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪