运筹说 第74期 | 图与网络分析基本知识梳理

第一节 图与网络的基本知识

一、图与网络的基本概念

运筹学中所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。总之，这里所讲的图是反映对象之间关系的一种工具。图的理论和方法，就是从形形色色的具体的图以及与它们相关的实际问题中，抽象出共同性的东西，找出其规律、性质、方法，再应用到要解决的实际问题中去。

1.图

定义1：一个图是由点集 和 中元素的无序对的一个集合 所构成的二元组，记为 ， 中元素 叫做顶点， 中的元素 叫做边。

当 为有限集合时， 称为有限图，否则，则称为无限图。

例1?在图1中，V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5}。

其中：e1=（v1,v1）?e2=（v1,v2）?e3=（v1,v3）?

e4=（v2,v3）?e5=（v2,v3）?e6=（v3,v4）

图1

2.图论中常用术语

（1）相邻与关联

定义2：两个点u,v属于V，如果边(u,v)属于E，则称u,v两点相邻。u,v称为边(u,v)的端点。

定义3：两条边ei,ej属于E，如果它们有一个公共端点u，则称ei,ej相邻。边ei,ej称为点u的关联边。

（2）简单图与多重图

定义4：含环和多重边的图称为简单图，含有多重边的图称为多重图。有向图中两点之间有不同方向的两条边，不是多重边，如图2中（a）、（b）均为简单图，（c）、（d）为多重图。

图2

（3）次与悬挂点、孤立点

定义5：以点v为端点的边数叫作点v的次（degree），记作deg(v)，简记为d(v)。

定义6：次为1的点称为悬挂点，连接悬挂点的边称为悬挂边。

定义7：次为零的点称为孤立点。

（4）奇点与偶点

定义8：次为奇数的点称为奇点；次为偶数的点称为偶点。

定理1：任何图中，顶点次数的总和等于边数的2倍。

定理2：任何图中，次为奇数的顶点必为偶数个。

有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示，以vi为终点的边数称为点vi的入次，用d-(vi)表示。vi点的出次与入次之和就是该点的次。容易证明有向图中，所有顶点的入次之和等于所有顶点的出次之和。

（5）链与圈

定义9：无向图G=(V,E)，若图G中某些点与边的交替序列可以排成(vi0,ei1,vi1,ei2,…,vi(k-1),eik,vik)的形式，且eit=(vi(t-1),vit?)(t=1,2,3,…,k)，则称这个点边序列为连接vi0与vik的一条链，链长为k。

点边列中没有重复的点和重复边者为初等链。

图3

在图3中，S={v6,e6,v5,e7,v1,e8,v5,e7,v1,e9,v4,e4,v3}为一条连接v6，v3的链。S1={v6,e6,v5,e5,v4,e4,v3}为初等链。

定义10：无向图G中，连接vi0与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中既无重复点也无重复边者为初等圈。

图4

如图4中{v1,e7,v5,e8,v1,e9,v4,e10,v2,e2,v1}为一个圈。

对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向。而当链（圈）上的边方向相同时，称为道路（回路）。

图4中,S={v6,e6,v5,e8,v1,e9,v4,e10,v2,e3,v3}为一条链。

S1={v6,e6,v5,e7,v1,e9,v4,e4,v3}为一条道路。

S2={v1,e2,v2,e2,v1,v4,e5,v5,e8,v1}为一个圈。

S3={v1,e2,v2,e10,v4,e5,v5,e7,v1}为一个回路。

（6）子图与支撑子图

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

如图5，（b）、（c）均为（a）的子图。

图5

（7）割集

定义12：给定图G=(V,E)，点的子集S∈v，T∈V，定义G中边的集合[S,T]G={uv|u∈s, v∈t}为一个割集。

（8）图

在实际问题中，往往只用图来描述所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，我们常称之为“权”，权可以代表如距离、费用、通过能力（容量）等。这种点或边带有某种数量指标的图称为网络（赋权图）。

3.图的矩阵表示

用矩阵表示图对研究图的性质及应用常常是比较方便的，图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵、割集矩阵等，这里只介绍其中两种常用矩阵—权矩阵、邻接矩阵。

定义13：网络（赋权图）G=(V,E)，其边(vi,vj)有权ωij，构造矩阵A=(aij)n×n，其中：

称矩阵A为网络G的权矩阵。

定义14：对于图G=(V,E)，|V|=n，构造一个矩阵A=(aij)n×n，其中：

则称矩阵A为图的邻接矩阵。

例2：对图6所表示的图构造其权矩阵（见A1）和邻接矩阵（见A2）如下：

图6

当G为无向图时，邻接矩阵为对称矩阵。

4.图的同构

定义15：设图G=(V,E)与G'= (V',E')，若它们的点之间存在一一对应，并且保持同样的相邻关系，则称G与G'同构。

二、最小树问题

树是图论中结构最简单但又十分重要的图，在自然科学和社会科学的许多领域都有着广泛的应用。

例3：乒乓球单打比赛抽签后，可用图来表示选手间相遇情况，如图7所示。

1.树的概念和性质

定义16：连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。

定理3：图T=(V,E)，|V|=n，|E|=m，则下列关于树的说法是等价的。

• T是一个树。

• T无圈，且m=n-1。

• T连通，且m=n-1

• T无圈，但每加一新边即得唯一一个圈。

• T连通，但任舍去一边就不连通。

• T中任意两点，有唯一链相连。

2.图的支撑树

定义17：图G的生成子图是一棵树，则称该树为G的支撑树（生成树），或简称为图G的树。

图G中属于生成树的边称为树枝，不在生成树中的边称为弦。如图8，（b）为（a）图的生成树，边e1，e2，e3，e7，e8，e9为树枝，e4，e5，e6为弦。

图8

定理4：图G=(V,E)有生成树的充分必要条件为G是连通图。

找图中支撑树的方法可分为两种：避圈法和破圈法

按照边的选法不同，避圈法找图中生成树的方法可分为两种：

（1）深探法

步骤如下：（用标号法）

①在点集V中任取一点v，给v以标号0。

②若某点u已得标号i，检查一端点为u的各边，另一端点是否均已标号。

若有(u,ω)边之ω未标号，则给ω以标号i+1，记下边(u,ω)。令ω代u，重复②。

若这样的边的另一端点均已有标号，就退到标号为i-1的r点，以r代u，重复②。直到全部点都得到标号为止。

我们用一个例子来帮助大家理解标号法的过程。

例4：请使用标号法，获得图9的生成树。

图9

图10即为标号过程，粗线边即为生成树，最终得到生成树如图11所示，图11也显示了标号过程。

图10

图11

（2）广探法

步骤如下：

①在点集V中任取一点v，给v以标号0。

②令所有标号为i的点集为Vi，检查[Vi,V\Vi?]中的边端点是否均已标号。对所有未标号之点均标以i+1，记下这些边。

③对标号i+1的点重复步骤②，直到全部点得到标号为止。

使用广探法来求解例4，图12（a）中粗线边就是用广探法生成的树，也可以表示为图12的（b）。

图12

显然，图的生成树不唯一。

相对于避圈法，还有一种求生成树的方法叫破圈法。这种方法是在图G中任意取一个圈，从圈上任意舍弃一条边，将这个圈破掉。重复这个步骤直到图G中没有圈为止。

3.最小支撑树问题

定义18：连通图G=(V,E)，每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为这个支撑树的权。具有最小权的生成树称为最小支撑树（最小生成树）简称最小树。

许多网络问题都可以归结为最小树问题。例如，交通系统中设计长度最小的公路网把若干城市联系起来；通信系统中用最小成本把计算机系统和设备连接到局域网等等。下面介绍最小树的两种算法：

（1）Kruskal算法

这个方法类似于生成树的“避圈法”，基本步骤如下：

每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够条n-1边为止。

下面小编用一个例子来阐述一下Kruskal算法。

例5：一个乡有9个自然村，其间道路及各道路长度如下图13（a）所示，各边上的数字表示距离，问如何架设电线做到村村通电又能使用线最短。

解：先将上图（a）中边按大小顺序由小到大排列：

(v0,v2)=1? ?(v2,v3)=1? ?(v3,v4)=1? ?(v1,v8)=1? ?(v0,v1)=2? (v0,v6)=2? ?(v5,v6)=2? ?(v0,v3)=3? ?(v6,v7)=3? ?(v0,v4)=4? (v0,v5)=4? ?(v0,v8)=4? ?(v1,v2)=4? ?(v0,v7)=5? ?(v7,v8)=5??(v4,v5)=5

然后按照边的排列顺序，取定

e1=(v0,v2)? ?e2=(v2,v3)? ?e3=(v3,v4)? ?e4=(v1,v8)? ?e5=(v0,v1)? ?e6=(v0,v6)? ??e7=(v5,v6)

由于下一个未选边中的最小权边(v0,v3)与已选边e1，e2构成圈，所以排除。选e8=(v6,v7)。得到图（b）就是图G的一棵最小树，它的权是13。

图13

（2）破圈法

基本步骤：

①从图G中任选一棵树T1。

②加上一条弦e1，T1+e1中立即生成一个圈。去掉此圈中最大权边，得到新树T2。以T2代T1，重复②再检查剩余的弦，直到全部弦检查完毕为止。

破圈法的根据为下述定理。

定理5：图G的生成树T为最小树，当且仅当对任一弦e来说，e是T+e中与之对应的圈μe中的最大权边。

仍用上述例题，先求出图G的一棵生成树如下图14（a）所示，加以弦(v1,v2)，得圈{v1?v2?v0?v1}，去掉最大权边(v1,v2)；再加上弦(v2,v3)，得圈{v2?v3?v0?v2}，去掉最大权边(v0,v3)，…，直到全部弦均已试过，下图（b）即为所求。

图14

以上就是图与网络分析基本知识梳理的全部内容了，通过本节学习大家是否对本章节有了一个初步的认识呢？下一次小编将带大家学习第八章的经典问题——最短路问题，敬请关注！