文档介绍：第四章测试人员的图论
东北大学软件学院
由安博测试空间技术中心
图
东北大学软件学院
图(又叫做线性图)是一种由两个集合定义的抽象数学结构,即一个节点集合和一个构成节点之间连接的边集合。
定义
图G=(V,E)由节点的有限(并且非空)集合V和节点无序对偶集合E组成。
V={n1,n2,…,nm) 和
E={el,e2,…,ep}
其中每条边ek=(ni,nj), ni、nj ∈V。
举例
东北大学软件学院
V={nl,n2,n3,n4,n5,n6,n7)
E={e1,e2,e3,e4,e5}={(nl,n2),(nl,n4),(n3, n4),(n2,n5),(n4,n6)}
图4-1 有7个节点和5条边的图
n1
n2
n4
n3
n5
n6
n7
e1
e2
e3
e4
e5
节点的度
东北大学软件学院
定义
图中节点的度是以该节点作为端点的边的条数。我们把节点n的度记做deg(n)。
deg(n1) = 2
deg(n2) = 2
deg(n3) = 1
deg(n4) = 3
deg(n5) = 1
deg(n6) = 1
deg(n7) = 0
关联矩阵
东北大学软件学院
定义
拥有m个节点和n条边的图G=(V,E)的关联矩阵是一种m×n矩阵,其中第i行第j列的元素是1,当且仅当节点i是边j的一个端点,否则该元素是0。
e1
e2
e3
e4
e5
n1
1
1
0
0
0
n2
1
0
0
1
0
n3
0
0
1
0
0
n4
0
1
1
0
1
n5
0
0
0
1
0
n6
0
0
0
0
1
n7
0
0
0
0
0
相邻矩阵
东北大学软件学院
定义
拥有m个节点和n条边的图G=(V,E)的相邻矩阵是一种m×m矩阵,其中第i行第j列的元素是1,当且仅当节点i和节点j之间存在一条边,否则该元素是0。
n1
n2
n3
n4
n5
n6
n7
n1
0
1
0
1
0
0
0
n2
1
0
0
0
1
0
0
n3
0
0
0
1
0
0
0
n4
1
0
1
0
0
1
0
n5
0
1
0
0
0
0
0
n6
0
0
0
1
0
0
0
n7
0
0
0
0
0
0
0
路径
东北大学软件学院
定义
路径是一系列的边,对于序列中的任何相邻边对偶ei、ej,边都拥有相同的(节点)端点。
路径可以描述为一系列边,也可以描述为一系列节点。一般更常见的是节点序列。
路径
节点序列
边序列
n1和n5之间
n1, n2, n5
e1, e4
n6和n5之间
n6, n4, n1, n2, n5
e5, e2 ,e1, e4
n3和n2之间
n3, n4, n1 , n5
e3, e2 , e1
连接性
东北大学软件学院
定义
节点ni和nj是被连接的,当且仅当它们都在同一条路径上。
“连接性”是一种图的节点集合上的等价关系。为了说明这一点,可以再复习一遍定义等价关系的三个性质:
,因为每个节点显然都在到其本身长度为0的路径上。
,由于如果ni和nj在一条路径上,则nj和ni也在同一条路径上。
。
组件
东北大学软件学院
定义
图的组件是相连节点的最大集合。
等价类中的节点是图的组件。图4-1种的图有两个组件:
{n1, n2, n3, n4, n5, n6}
{n7}
压缩图
东北大学软件学院
定义
给定图G = (V,E),其压缩图通过用压缩节点替代每个组件构成。
给定图的压缩图是惟一的。
S1 = {n1,n2,n3,n4,n5,n6}
S2 = {n7}