图与网络的基本概念

2.1 无向图
一个无向图(undirected graph)G是由一个非空有限集合 G(V) 和 G(V) 中某些元素
的无序对集合 E(G) 构成的二元组,记为 G=(V(G),E(G)) 。其中
V(G)={image}称为图G的顶点集(vertex set)或节点集(node set),  V(G)中
的每一个元素 image称为该图的一个顶点(vertex)或节点(node);
image称为图G的边集(edge set), E(G) 中的每一个元素image (即 V(G )
中某两个元素 image 的无序对) 记为imageimage
被称为该图的一条从imageimage的边(edge)。
当边 image时,称 image
的端点,并称image相邻(adjacent);边image
为与顶点 image关联(incident)。如果某两条边至少有一个公共端点,则称这两条边在
图G中相邻。
边上赋权的无向图称为赋权无向图或无向网络(undirected network)。我们对图和
网络不作严格区分,因为任何图总是可以赋权的。

一个图称为有限图,如果它的顶点集和边集都有限。图G的顶点数用符号 | V| 或
ν(G) 表示,边数用 | E|或 ε(G) 表示。
当讨论的图只有一个时,总是用G来表示这个图。从而在图论符号中我们常略去
字母G,例如,分别用 E, V ,ν和ε代替V(G),E(G), ν(G) 和 ε(G) 。
端点重合为一点的边称为环(loop)。
一个图称为简单图(simple graph),如果它既没有环也没有两条边连接同一对顶点。
2.2  有向图
定义  一个有向图(directed graph或digraph)G是由一个非空有限集合V和V中
某些元素的有序对集合A构成的二元组,记为G=(V,A) 。其中

image
为图G的顶点集或节点集,  V中的每一个元素image称为该图的一个顶点
或节点;image称为图G的弧集(arc set),A中的每一个元素image (即V中
某两个元素image的有序对) 记为image,被称为该图
的一条从image的弧(arc)。
当弧 image 时,称image,并称弧image
出弧(outgoing arc),为image的入弧(incoming arc)。
对应于每个有向图D,可以在相同顶点集上作一个图G,使得对于D的每条弧,
G有一条有相同端点的边与之相对应。这个图称为D的基础图。反之,给定任意图G,
对于它的每个边,给其端点指定一个顺序,从而确定一条弧,由此得到一个有向图,这
样的有向图称为G的一个定向图。
以下若未指明“有向图”三字,“图”字皆指无向图。
2.3 完全图、二分图
每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n个顶点
的完全图记为 image
若V(G)=X U Y, X imageY=Φ, | X||Y | ≠ 0 (这里 | X| 表示集合X中的元素个
数),X中无相邻顶点对,Y中亦然,则称G为二分图(bipartite graph);特别地,若
image
2.4 子图
图H叫做图G的子图(subgraph),记作 H ⊂ G,如果 V(H)  ⊂ V(G),
E(H) ⊂ E(G)。若H是G的子图,则G称为H的母图
G的支撑子图(spanning subgraph,又成生成子图)是指满足 V(H) = V(G)的子
图H。
2.5 顶点的度
image,G中与v关联的边数(每个环算作两条边)称为v的度(degree),记
作 d(v) 。若 d(v) 是奇数,称v是奇顶点(odd point); d(v) 是偶数,称v是偶顶点(even
point)。关于顶点的度,我们有如下结果:
(i) image

(ii) 任意一个图的奇顶点的个数是偶数。

2.6 图与网络的数据结构

网络优化研究的是网络上的各种优化模型与。为了在计算机上实现网络优化的
,首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说,
的好坏与网络的具体表示方法,以及中间结果的操作是有关系的。这里我们介
绍计算机上用来描述图与网络的5种常用表示方法:邻接矩阵表示法、关联矩阵表示法、
弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中,我们首先假设
G=(V,A) 是一个简单有向图,|V |=n , |A |=m ,并假设V中的顶点用自然数 1,2,…,n
表示或编号,A中的弧用自然数 1,2,…,m 表示或编号。对于有多重边或无向网络的情
况,我们只是在讨论完简单有向图的表示方法之后,给出一些说明。
(i)邻接矩阵表示法
邻接矩阵表示法是将图以邻接矩阵(adjacency matrix)的形式存储在计算机中。图
G=(V,A) 的邻接矩阵是如下定义的:C是一个 n×n 的 0−1 矩阵,即
image
也就是说,如果两节点之间有一条弧,则邻接矩阵中对应的元素为1;否则为0。
可以看出,这种表示法非常简单、直接。但是,在邻接矩阵的所有image个元素中,只有m
个为非零元。如果网络比较稀疏,这种表示法浪费大量的存储空间,从而增加了在网络
中查找弧的

image

图2  有向图

例7  对于图2所示的有向图,可以用邻接矩阵表示为

image

 

image(无向图实例)

 

同样,对于网络中的权,也可以用类似邻接矩阵的 n×n 矩阵表示。只是此时一条
弧所对应的元素不再是1,而是相应的权而已。如果网络中每条弧赋有多种权,则可以
用多个矩阵表示这些权。
(ii)关联矩阵表示法
关联矩阵表示法是将图以关联矩阵(incidence matrix)的形式存储在计算机中.图
G=(V,A) 的关联矩阵B是如下定义的:B是一个 n×m 的矩阵,即

image

image

 

也就是说,在关联矩阵中,每行对应于图的一个节点,每列对应于图的一条弧。如
果一个节点是一条弧的起点,则关联矩阵中对应的元素为1;如果一个节点是一条弧的
终点,则关联矩阵中对应的元素为−1 ;如果一个节点与一条弧不关联,则关联矩阵中
对应的元素为0。对于简单图,关联矩阵每列只含有两个非零元(一个 +1 ,一个 −1 )。
可以看出,这种表示法也非常简单、直接。但是,在关联矩阵的所有nm个元素中,只
有2m 个为非零元。如果网络比较稀疏,这种表示法也会浪费大量的存储空间。但由于
关联矩阵有许多特别重要的理论性质,因此它在网络优化中是非常重要的概念。

例8  对于例7所示的图,如果关联矩阵中每列对应弧的顺序为(1,2),(1,3),(2,4),
(3,2),(4,3),(4,5),(5,3)和(5,4),则关联矩阵表示为

image

同样,对于网络中的权,也可以通过对关联矩阵的扩展来表示。例如,如果网络中
每条弧有一个权,我们可以把关联矩阵增加一行,把每一条弧所对应的权存储在增加的
行中。如果网络中每条弧赋有多个权,我们可以把关联矩阵增加相应的行数,把每一条
弧所对应的权存储在增加的行中。
(iii)弧表表示法
弧表表示法将图以弧表(arc list)的形式存储在计算机中。所谓图的弧表,也就是
图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点,共需2m 个存
储单元,因此当网络比较稀疏时比较方便。此外,对于网络图中每条弧上的权,也要对
应地用额外的存储单元表示。例如,例7所示的图,假设弧(1,2),(1,3),(2,4),(3,2),
(4,3),(4,5),(5,3)和(5,4)上的权分别为8,9,6,4,0,3,6和7,则弧表表示如表1
所示。

image

 

为了便于检索,一般按照起点、终点的字典序顺序存储弧表,如上面的弧表就是按
照这样的顺序存储的。
(iv)邻接表表示法
邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的
邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它的邻接表就是它的所
有出弧。邻接表表示法就是对图的每个节点,用一个单向链表列出从该节点出发的所有
弧,链表中每个单元对应于一条出弧。为了记录弧上的权,链表中每个单元除列出弧的
另一个端点外,还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数
组表示。例如,例7所示的图,邻接表表示为

image

这是一个5维指针数组,每一维(上面表示法中的每一行)对应于一个节点的邻接
表,如第1行对应于第1个节点的邻接表(即第1个节点的所有出弧)。每个指针单元
的第1个数据域表示弧的另一个端点(弧的头),后面的数据域表示对应弧上的权。如
第1行中的“2”表示弧的另一个端点为2(即弧为(1,2)),“8”表示对应弧(1,2)上的
权为8;“3”表示弧的另一个端点为3(即弧为(1,3)),“9”表示对应弧(1,3)上的权
为9。又如,第5行说明节点5出发的弧有(5,3)、(5,4),他们对应的权分别为6和7。
对于有向图  G= (V,A),一般用 A(i) 表示节点i的邻接表,即节点i的所有出弧构
成的集合或链表(实际上只需要列出弧的另一个端点,即弧的头)。例如上面例子,
A(1)={2,3}, A(5)={3,4}等。
(v)星形表示法
星形(star)表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点,
它也是记录从该节点出发的所有弧,但它不是采用单向链表而是采用一个单一的数组表
示。也就是说,在该数组中首先存放从节点1出发的所有弧,然后接着存放从节点2
出发的所有孤,依此类推,最后存放从节点n出发的所有孤。对每条弧,要依次存放其
起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号,
只是从同一节点出发的弧的顺序可以任意排列。此外,为了能够快速检索从每个节点出
发的所有弧,我们一般还用一个数组记录每个节点出发的弧的起始地址(即弧的编号)。
在这种表示法中,可以快速检索从每个节点出发的所有弧,这种星形表示法称为前向星
形(forward star)表示法。
例如,在例7所示的图中,仍然假设弧(1,2),(l,3),(2,4),(3,2),(4,3),(4,5),
(5,3)和(5,4)上的权分别为8,9,6,4,0,3,6和7。此时该网络图可以用前向
星形表示法表示为表2和表3 。

表2  节点对应的出弧的起始地址编号数组

image

 

表3  记录弧信息的数组

image

在数组point中,其元素个数比图的节点数多1(即 1 + n ),且一定有 point(1)=1 ,
point(n+1)=m+1 。对于节点i,其对应的出弧存放在弧信息数组的位置区间为
[point(i),point(i+1)-1] ,
如果 point(i) = point(i+1),则节点i没有出弧。这种表示法与弧表表示法也非常相

似,“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中,
弧被编号后有序存放,并增加一个数组(point)记录每个节点出发的弧的起始编号。
前向星形表示法有利于快速检索每个节点的所有出弧,但不能快速检索每个节点的
所有入弧。为了能够快速检索每个节点的所有入孤,可以采用反向星形(reverse star)
表示法:首先存放进入节点1的所有孤,然后接着存放进入节点2的所有弧,依此类推,
最后存放进入节点n的所有孤。对每条弧,仍然依次存放其起点、终点、权的数值等有
关信息。同样,为了能够快速检索从每个节点的所有入弧,我们一般还用一个数组记录
每个节点的入孤的起始地址(即弧的编号)。例如,例7所示的图,可以用反向星形表
示法表示为表4和表5。

image

如果既希望快速检索每个节点的所有出弧,也希望快速检索每个节点的所有入弧,
则可以综合采用前向和反向星形表示法。当然,将孤信息存放两次是没有必要的,可以
只用一个数组(trace)记录一条弧在两种表示法中的对应关系即可。例如,可以在采用
前向星形表示法的基础上,加上上面介绍的rpoint数组和如下的trace数组即可。这相
当于一种紧凑的双向星形表示法,如表6所示。

image

对于网络图的表示法,我们作如下说明:
①  星形表示法和邻接表表示法在实际实现中都是经常采用的。星形表示法的
优点是占用的存储空间较少,并且对那些不提供指针类型的语言(如FORTRAN语言
等)也容易实现。邻接表表示法对那些提供指针类型的语言(如等)是方便的,
且增加或删除一条弧所需的计算工作量很少,而这一操作在星形表示法中所需的计算工
作量较大(需要花费 O(m) 的计算)。有关“计算”的观念是网络优化中需要
考虑的一个关键因素。
②  当网络不是简单图,而是具有平行弧(即多重弧)时,显然此时邻接矩阵表示
法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。
③  上述方法可以很方便地推广到可以处理无向图的情形,但由于无向图中边没有
方向,因此可能需要做一些自然的修改。例如,可以在计算机中只存储邻接矩阵的一半
信息(如上三角部分),因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素
0和+1 ,而不含有 −1 ,因为此时不区分边的起点和终点。又如,在邻接表和星形表示
法中,每条边会被存储两次,而且反向星形表示显然是没有必要的,等等。

 

2.7  轨与连通
image

image

若道路W的边互不相同,则W称为迹(trail)。若道路W的顶点互不相同,则W称
为轨(path)。
称一条道路是闭的,如果它有正的长且起点和终点相同。起点和终点重合的轨叫做
圈(cycle)。
若图G的两个顶点 v u, 间存在道路,则称u和v连通(connected)。 u,v 间的最短轨
的长叫做 u,v 间的距离。记作 d(u,v) 。若图G的任二顶点均连通,则称G是连通图。
显然有:
(i) 图P是一条轨的充要条件是P是连通的,且有两个一度的顶点,其余顶点的度
为2;
(ii) 图C是一个圈的充要条件是C是各顶点的度均为2的连通图。

声明: 除非转自他站(如有侵权,请联系处理)外,本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明:转自《图与网络的基本概念
本文地址:https://www.zhiletu.com/archives-6858.html
关注公众号:智乐兔

赞赏

wechat pay微信赞赏alipay pay支付宝赞赏

上一篇
下一篇

相关文章

在线留言

你必须 登录后 才能留言!

在线客服
在线客服 X

售前: 点击这里给我发消息
售后: 点击这里给我发消息

智乐兔官微