《运筹学》课程教学课件（PPT讲稿）图与网络分析 Graph Theory and Network Analysis

图的基本概念与模型 Page 21 图的矩阵描述： 如何在计算机中存储一个图呢？现在已有很多存储的方法， 但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示 也根据所关心的问题不同而有： 邻接矩阵、关联矩阵、权矩阵等。 1.邻接矩阵 对于图G=(V,E),|VFn,|E=m,有n×n阶方矩阵 A=(a)nxm,其中 当且仅档与v之间有关联边时

图的基本概念与模型 Page 21 图的矩阵描述： 如何在计算机中存储一个图呢？现在已有很多存储的方法， 但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示 也根据所关心的问题不同而有： 邻接矩阵、关联矩阵、权矩阵等。 1. 邻接矩阵 对于图G=（V，E），| V |=n， | E |=m，有nn阶方矩阵 A=(aij) nn，其中    = 其 它 当且仅档 与 之间有关联边时 0 1 vi vj aij

图的基本概念与模型 Page 22 例6.2下图所表示的图可以构造邻接矩阵A如下 4 V2 3 3 VI V2 V3 V Vs Vo y「0101111 y2101100 VE V y3010101 A6= 111010 y100101 vL101010

图的基本概念与模型 Page 22 v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 1 1 6 5 4 3 2 1 6 6 1 2 3 4 5 6                      = v v v v v v A v v v v v v 例6.2 下图所表示的图可以构造邻接矩阵A如下

图的基本概念与模型 Page 23 2.关联矩阵 对于图G-(V,E),|V=n,|E=m,有mxn阶矩阵M=(m)mxm, 其中： 2当且仅当，是边e的两个端点 m,=1当且仅当v,是边e的一个端点 0其他 3.权矩阵 对于赋权图G=(V,E),其中边(y,y,有权w,构造矩阵B-(b)xm 其中： Wij (y,y)∈E 10 (v,v)E

Page 23 对于赋权图G=(V,E), 其中边 有权 , 构造矩阵B=(bij) nn 其中： 图的基本概念与模型 2. 关联矩阵 对于图G=(V,E), | V |=n, | E |=m, 有mn阶矩阵M=(mij) mn， 其中:      = 其他 当且仅当 是边 的一个端点 当且仅当 是边 的两个端点 0 1 v e 2 v e i j i j mij 3. 权矩阵 ( , ) i j v v wi j       = v v E w v v E b i j i j i j i j 0 ( , ) ( , )

图的基本概念与模型 Page 24 例6.3下图所表示的图可以构造邻接矩阵M如下： es el e2 e3 e4 e5 e6 e7 e8 e9 e10 ell e12 e V8v11010000000900 v211001000000 0 v301000111000 0 v400000 0 0 0 10 0 M=(m)=v5 0011 1 0 0 000 0 0000 0 0 0 0 1 1 0 0 v70000 00 0 0 0 1 1 v80001001100 0 0

图的基本概念与模型 Page 24 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 v1 v2 v3 v4 v5 v6 v7 v8 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1 v2 v3 v5 v8 v7 e1 e2 e3 e6 e4 e5 e7 e9 e12 e10 e11 e8 v4 v6 例6.3 下图所表示的图可以构造邻接矩阵M如下: M=（mij）=

图的基本概念与模型 Page 25 例6.4下图所表示的图可以构造权矩阵B如下： 3 [040643 V2 402700 2 020503 B= 675020 400203 L303030

图的基本概念与模型 Page 25 1 2 3 4 5 6 6 5 4 3 2 1 3 0 3 0 3 0 4 0 0 2 0 3 6 7 5 0 2 0 0 2 0 5 0 3 4 0 2 7 0 0 0 4 0 6 4 3 v v v v v v v v v v v v B                     v = 5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 例6.4 下图所表示的图可以构造权矩阵B如下: