第三部分图与网络分析 图与网络分析部分内容框架 图 图与网络的基本概念 连通图 图的矩阵表示 树与最小树 最短路问题 图论在网络分析的应用 最大流问题 最小费用最大流问题 第四章图与网络分析 §1.图与网络的基本概念 、图及其分类 本章研究的图与平面几何中的图不同,我们只关心图中有多少个点, 点与点之间有无线连接,至于连线的方式是直线还是曲线,点与点的相对 位置如何,都是无关紧要的。下面介绍有关图的基本概念 1图,图是点和线所组成的图形,即图是一个有序二元组(VE),记为 G=(V,E),其中V={v,v;v}是p个点的集合,E={ene,e}是q条边的 集合。V中的元素v称为顶点,E中的元素ek称为边。 如图1所示:
20 第三部分 图与网络分析 图与网络分析部分内容框架 图与网络的基本概念 图 连通图 图的矩阵表示 树与最小树 最短路问题 图论在网络分析的应用 最大流问题 最小费用最大流问题 第四章 图与网络分析 §1. 图与网络的基本概念 一、图及其分类 本章研究的图与平面几何中的图不同，我们只关心图中有多少个点， 点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对 位置如何，都是无关紧要的。下面介绍有关图的基本概念。 1.图，图是点和线所组成的图形，即图是一个有序二元组(V,E)，记为 G=(V,E)，其中 V={v1,v2,…vp}是 p 个点的集合，E={e1,e2,…eq}是 q 条边的 集合。V 中的元素 vi 称为顶点，E 中的元素 ek 称为边。 如图 1 所示： 图 与 网 络 分 析
V3 图1 V=(v1, V2, V3, V4, V5, E(el, e2, e3, e4, es, e6) 其中el={v,vn},e2={v,v2},e3={v,w3} e4={v3,v4},es= 对于边(vy),则称vv两点相邻,也称v,v为边(vv)的端点 若两条边有一个公共端点u,则称这两边是相邻的,也称这两边为点u 的关联边 若两端之间多于一条边的,称为多重边。如图1中的e4、es 若一条边的两个端点相同,则称此为环(自回路)。如图1中的el 2简单图与多重图,不含环和多重边的图称为简单图,含有多重边的 图称为多重图。上图就是一个多重图。 3.无向图与有向图。G=(VE)中,若所有的边均有 ek=(vv)=(Vy,V)k=1,2…q,则称G为无向图,记为G=(V,E)。若图中边(v,v) 的端点是有序的,即表示以v为始点v为终点。则称该图为有向图,记为 D=(V,A)。在有向图中,把边称为弧。因此,A表示G中弧的集合 4图的同构
21 图 1 V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6} 其中 e1={v1,v1},e2={v1,v2},e3={v1,v3} e4={v3,v4},e5={v3,v4},e6={v1,v4} 对于边(vi,vj)，则称 vi,vj 两点相邻，也称 vi,vj 为边(vi,vj)的端点。 若两条边有一个公共端点 u，则称这两边是相邻的，也称这两边为点 u 的关联边。 若两端之间多于一条边的，称为多重边。如图 1 中的 e4、e5。 若一条边的两个端点相同，则称此为环（自回路）。如图 1 中的 e1。 2.简单图与多重图，不含环和多重边的图称为简单图，含有多重边的 图称为多重图。上图就是一个多重图。 3. 无向图与有向图。 G=(V,E) 中 ， 若 所 有 的 边 均 有 ek=(vi,vj)=(vj,vi),k=1,2,…q，则称 G 为无向图，记为 G=(V,E)。若图中边(vi,vj) 的端点是有序的，即表示以 vi 为始点 vj 为终点。则称该图为有向图，记为 D=(V,A)。在有向图中，把边称为弧。因此，A 表示 G 中弧的集合。 4.图的同构。 v1 v4 v2 v3 (a) (b) e1 V1 e3 e4 e5 e6 V3 V5 V2 e2 V4
上面图(a)与图(b)初看起来似乎是不同的两个图,如果我们正确的确定 它们顶点之间的对应关系: Vb V3 Vd. v4 那么,它们边与边间的对应关系就有: (V1,v2H(Vc, Vb), (V1, V3)-(Vc, Va)(v1, v4(Vc, va) (v2, v3)-(Vb, Vd), (v3, v4)--(Vd, va) 从以上分析可以得出:图(a)和图(b实质上是一个图,只不过表现的形 式不同。 设图G=(VE)与G=(V,E),若它们的顶点存在一一对应,且保持同样 相邻关系,则称G和G'同构,记为G≡G。 5顶点的次。以点ⅴ为端点的边数称为点v的次,记为d(v)。图1中 d(v2)=1,d(v3)=3d(v1)=5。 次数为1的点称为悬挂点,连结悬挂点的边称为悬挂边 次数为0的点称为孤立点,如图1中的点vs 次为奇数的点称为奇点,次为偶数的点称为偶点。 在任何图中,顶点的次数与边数有如下性质: (1)∑d()=2q(其中p为G中顶点数,q为边数) 2)次为奇数的顶点必为偶数个 在有向图D=(VA)中,以v为始点的边数称为点v的出次,记为dt(v) 以v为终点的边数称为点v的入次,记为d(v)。显然d(v)=dt(v)+d(v) 且∑d(v,)=∑d(m,) 5网络。在实际问题中,只用图来描述所研究对象之间的关系往往是 不够的。与图联系在一起,通常还有与点或边有关的某些数量指标,通常 称之为“权”。权可以表示为:距离、费用、通过能力(数量)等。称含 有数量指标的赋权图为网络。与无向图和有向图相对应,网络可分为无向
22 上面图(a)与图(b)初看起来似乎是不同的两个图，如果我们正确的确定 它们顶点之间的对应关系： v1 vc,v2 vb,v3 vd,v4 va 那么，它们边与边间的对应关系就有： (v1,v2) (vc,vb),(v1,v3) (vc,vd)(v1,v4) (vc,va), (v2,v3) (vb,vd),(v3,v4) (vd,va)。 从以上分析可以得出：图(a)和图(b)实质上是一个图，只不过表现的形 式不同。 设图 G=(V,E)与 G=(V,E)，若它们的顶点存在一一对应，且保持同样 相邻关系，则称 G 和 G同构，记为 G G。 5.顶点的次。以点 v 为端点的边数称为点 v 的次，记为 d(v)。图 1 中， d(v2)=1,d(v3)=3,d(v1)=5。 次数为 1 的点称为悬挂点，连结悬挂点的边称为悬挂边。 次数为 0 的点称为孤立点，如图 1 中的点 v5。 次为奇数的点称为奇点，次为偶数的点称为偶点。 在任何图中，顶点的次数与边数有如下性质： (1) = = p i d vi q 1 ( ) 2 （其中 p 为 G 中顶点数，q 为边数） (2)次为奇数的顶点必为偶数个。 在有向图 D=(V,A)中，以 vi 为始点的边数称为点 vi 的出次，记为 d + (vi), 以 vi 为终点的边数称为点 vi 的入次，记为 d - (vi)。显然 d(vi)=d+ (vi)+d- (vi)。 且 + − = i i i i d (v ) d (v )。 5.网络。在实际问题中，只用图来描述所研究对象之间的关系往往是 不够的。与图联系在一起，通常还有与点或边有关的某些数量指标，通常 称之为“权”。权可以表示为：距离、费用、通过能力（数量）等。称含 有数量指标的赋权图为网络。与无向图和有向图相对应，网络可分为无向
网络和有向网络,分别记为G=(VE,W)和D=(V,A,W) 、连通图 1链。在无向图G=(VE),称一个点和边交替的序列{v,eiva,en vi,v}为连接ⅶi和ⅶt的一条链。简记为{vi,vn,…wn}。其中 el=(Vk,vk+1)k=1,2,…t-1。 点边序列中只有重复的点而无重复边者称为简单链。 点边序列中没有重复的点和重复边者称为初等链。 e10 图3 图4 如图3中:S1={V,5,V1,s,V4,V3}是一条连结v6和v3简单链。 S2={v6,Vs,V1,V4v3}是一条条连结v6和v3的初等链 首尾相接的链称为圈。 2路。在有向图D=(V,A)中,称链{v,v;v}为一条从ⅶ到v的路。 若v=V,则称之为回路。 在图4中S1={V6,Vs,V1,sV4,}是一条从v6和v3的路 S2={v1,V2,V4,vsvn}是一条回路。 3.连通图。如果一个图中任意两点间至少有一条链相连,则称此图为 连通图。 任何一个连通图都可以分为若干个连通子图,每个连通子图称为由原 图的分图。图5中的(b)就是(a)的三个分图
23 网络和有向网络，分别记为 G=(V,E,W)和 D=(V,A,W)。 二、连通图 1.链。在无向图 G=(V,E)，称一个点和边交替的序列{vi1,ei1,vi2,ei2,… vit-1,vit} 为连接 vi1 和 vit 的一条链。简记为 {vi1,vi2, … vit} 。其中 eik=(vik,vik+1),k=1,2,…t-1。 点边序列中只有重复的点而无重复边者称为简单链。 点边序列中没有重复的点和重复边者称为初等链。 v1 v2 v1 v2 v5 v4 v5 v4 图 3 图 4 如图 3 中：S1={v6,v5,v1,v5,v4,v3}是一条连结 v6和 v3简单链。 S2={v6,v5,v1,v4,v3}是一条条连结 v6和 v3的初等链。 首尾相接的链称为圈。 2.路。在有向图 D=(V,A)中，称链{vi1,vi2,…vit}为一条从 vi1 到 vit 的路。 若 vi1=vit，则称之为回路。 在图 4 中 S1={v6,v5,v1,v5,v4,v3}是一条从 v6和 v3的路。 S2={v1,v2,v4,v5,v1}是一条回路。 3.连通图。如果一个图中任意两点间至少有一条链相连，则称此图为 连通图。 任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原 图的分图。图 5 中的(b)就是(a)的三个分图。 v v3 v6 3 v6 e3 e2 e1 e3 e2 e1 e11 e10 e7 e e9 10 e9 e7 e6 e4 e8 e6 e8 e4 e5 e5
图5 图6 三、图的矩阵表示 用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表 示方法有多种,这里介绍其中两种常用矩阵。 1权矩阵。网络G=(VE,W),其边(v)的权重为W,构造矩阵 A=(an)hxm,其中 W(v,")∈ ∞其它 称矩阵A为网络G的权矩阵。其中主对角线上的元素a均为零。 如图6的权矩阵为 A 9034 3085 60 2邻接矩阵。对于图G=(VE)构造一个矩阵A=(a)hm, 其中 (v,")∈E 0其它 则称矩阵A为图G的邻接矩阵。当G为无向图时邻接矩阵为对称的
24 (a) (b) 图 5 图 6 三、图的矩阵表示 用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表 示方法有多种，这里介绍其中两种常用矩阵。 1.权矩阵。网络 G=(V,E,W)，其边(vi,vj)的权重为 Wij，构造矩阵 A=(aij)nxn，其中 = 其它 W v v E a ij i j ij ( , ) 称矩阵 A 为网络 G 的权矩阵。其中主对角线上的元素 aij 均为零。 如图 6 的权矩阵为 = 7 5 6 0 4 4 8 0 6 2 3 0 8 5 9 0 3 4 0 9 2 4 7 A 2.邻接矩阵。对于图 G=(V,E)构造一个矩阵 A=(aij)nxn， 其中 = 0 其它 1 (v ,v ) E a i j ij 则称矩阵 A 为图 G 的邻接矩阵。当 G 为无向图时,邻接矩阵为对称的。 v1 v6 v5 v4 v3 v2 v1 v6 v5 v3 v4 v1 v1 v2 v3 v4 v5 2 4 3 5 7 6 9 8 4 。 。 。 。 。 。 。 。 。 。 。 。 v2