测试人员的图论.ppt
第四章 测试人员的图论,东北大学软件学院,由安博测试空间技术中心http:/,图,东北大学软件学院,图(又叫做线性图)是一种由两个集合定义的抽象数学结构，即一个节点集合和一个构成节点之间连接的边集合。,定义 图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条边的图,节点的度,东北大学软件学院,定义 图中节点的度是以该节点作为端点的边的条数。我们把节点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)的关联矩阵是一种mn矩阵，其中第i行第j列的元素是1，当且仅当节点i是边j的一个端点，否则该元素是0。,相邻矩阵,东北大学软件学院,定义 拥有m个节点和n条边的图G=(V，E)的相邻矩阵是一种mm矩阵，其中第i行第j列的元素是1，当且仅当节点i和节点j之间存在一条边，否则该元素是0。,路径,东北大学软件学院,定义 路径是一系列的边，对于序列中的任何相邻边对偶ei、ej，边都拥有相同的(节点)端点。路径可以描述为一系列边，也可以描述为一系列节点。一般更常见的是节点序列。,连接性,东北大学软件学院,定义 节点ni和nj是被连接的，当且仅当它们都在同一条路径上。“连接性”是一种图的节点集合上的等价关系。为了说明这一点，可以再复习一遍定义等价关系的三个性质：1连接性是自反的，因为每个节点显然都在到其本身长度为0的路径上。2连接性是对称的，由于如果ni和nj在一条路径上，则nj和ni也在同一条路径上。3连接性是传递的。,组件,东北大学软件学院,定义 图的组件是相连节点的最大集合。等价类中的节点是图的组件。图4-1种的图有两个组件：n1，n2，n3，n4，n5，n6 n7,压缩图,东北大学软件学院,定义 给定图G=(V，E)，其压缩图通过用压缩节点替代每个组件构成。给定图的压缩图是惟一的。S1=n1，n2，n3，n4，n5，n6S2=n7,圈数,东北大学软件学院,定义 图G的圈数由V(G)=e n+p给出，其中：e是G中的边数。n是G中的节点数。p是G中的组件数。,有向图,东北大学软件学院,定义 有向图（或框图）D=(V，E)包含：一个节点的有限集合V=(n1，n2，nm)，一个边的集合E=是节点ni、njV的一个有序对偶。,有向图例子,东北大学软件学院,V=nl，n2，n3，n4，n5，n6，n7)E=e1，e2，e3，e4，e5=，,图4-2 一个有向图,外度和内度,东北大学软件学院,定义 有向图中节点的内度，是将该节点作为终止节点的不同边的条数。节点n的内度记做indeg(n)有向图中节点的外度，是将该节点作为开始节点的不同边的条数。节点n的外度记做outdeg(n)indeg(n1)=0 Outdeg(n1)=2 indeg(n2)=1 Outdeg(n2)=1 indeg(n3)=0 Outdeg(n3)=1 indeg(n4)=2 Outdeg(n4)=1 indeg(n5)=1 Outdeg(n5)=0 indeg(n6)=1 Outdeg(n6)=0 indeg(n7)=0 Outdeg(n7)=0,节点的类型,东北大学软件学院,定义 内度为0的节点是源节点。外度为0的节点是吸收节点。内度不为0，并且外度不为0的节点是传递节点。,有向图的相邻矩阵,东北大学软件学院,定义 有m个节点的有向图D=(V，E)的相邻矩阵是一种mm矩阵：A=(a(i，j)，其中a(i，j)是1，当且仅当从节点i到节点j有一条边，否则该元素为0。,路径和半路径,东北大学软件学院,定义(有向)路径是一系列边，使得对于该序列中的所有相邻边对偶ei,ej来说，第一条边的终止节点是第二条边的初始节点。环路是一个在同一个节点上开始和结束的有向路径。(有向)半路径是一系列边，使得对于该序列中至少有一个相邻边对偶ei,ej来说，第一条边的初始节点是第二条边的初始节点，或第一条边的终止节点是第二条边的终止节点。,可到达性矩阵,东北大学软件学院,定义 有m个节点的有向图D=(V，E)的可达性矩阵是一种mm矩阵R=(r(i,j)，其中r(i，j)是1，当且仅当从节点i到节点j有一条路径，否则该元素为0。有向图D的可到达性矩阵可以通过相邻矩阵A计算如下：R=I+A+A2+A3+Ak其中k是D最长路径的长度，I是单位矩阵。,图4-2的可到达性矩阵,东北大学软件学院,n-连接性,东北大学软件学院,定义 有向图中的两个节点ni和nj是：0-连接，当且仅当ni和nj之间没有路径。l-连接，当且仅当ni和nj之间有一条半路径，但是没有路径。2-连接，当且仅当从ni和nj之间有一条路径。3-连接，当且仅当从ni和nj有一条路径，并且从nj到ni有一条路径。,图4-2的连接性,东北大学软件学院,n1和n7是0连接。n2和n6是1连接。n1和n6是2连接。n3和n6是3连接。,强组件,东北大学软件学院,定义 有向图的强组件是3-连接节点的最大集合。,n1,n2,S1,n5,S2,e1,e2,e4,n7,用于测试的图,东北大学软件学院,程序图 有限状态机 Petri网 状态图,程序图,东北大学软件学院,定义 给定一个采用命令式程序设计语言编写的程序，其程序图是一种有向图，其中：1(传统定义)节点是程序语句，边表示控制流(从节点i到节点j有一条边，当且仅当对应节点j的语句可以立即在节点i对应的语句之后执行)。2(经过改进的定义)节点要么是整个语句，要么是语句的一部分，边表示控制流(从节点i到节点j有一条边，当且仅当对应节点j的语句或语句的一部分，可以立即在节点i对应的语句或语句的一部分之后执行)。,结构化程序设计构造的有向图,东北大学软件学院,串行,IF-Then,IF-Then-Else,条件,前测试环路,后测试环路,有限状态机,东北大学软件学院,有限状态机是一种有向图，其中状态是节点，转移是边。源状态和吸收状态是初始节点和终止节点，路径被建模为通路，等等。大多数有限状态机表示方法都要为边(转移)增加信息，以指示转移的原因和作为转移的结果要发生的行动。,用于PIN尝试的有限状态机,东北大学软件学院,Petri网,东北大学软件学院,定义 Petri网是一种双向有向图(P，T，In，Out)，其中，P和T是不相交的节点集合，In和Out是边集合，In PT，Out TP。,有标记的Petri网,东北大学软件学院,定义 有标记的Petri网是一种5元组(P，T，In，Out，M)，其中(P，T，In，Out)是一个Petri网，M是从地点到正整数的映射集合。,Petri网的标记元组是。,两个基本定义,东北大学软件学院,定义 转移可以在Petri网中发生，如果在其所有输入地点中至少有一个记号。,定义 当触发Petri网一个转移时，要从其每个输入地点删除一个记号，并在其每个删除地点增加一个记号。,两个基本定义,东北大学软件学院,M=，,事件驱动的Petri网,东北大学软件学院,定义 EDPN是一种多向图(P，D，S，In，Out)，包括三个节点集合P、D和S，以及两个映射集合In和Out。其中：P是端口事件的集合。D是数据地点的集合。S是转移的集合。In是(PD)S的有序对偶集合。Out是S(PD)的有序对偶集合。,EDPN图,东北大学软件学院,为EDPN做标记,东北大学软件学院,定义 EDPN(P，D，S，In，Out)的一个标记M，是p元组的一个序列M=，其中p=k+n，k和n是集合P和D中的元素个数，p元组中的个体项表示事件或数据地点中的记号个数。,EDPN图中的标记和转移,东北大学软件学院,标记：元组（p3,p4,d5,d6,d7）m1（0,0,1,0,0）m2（1,0,1,0,0）m3（0,0,0,1,0）m4（1,0,0,1,0）m5（0,0,0,0,1）m6（0,1,0,0,1）m7（0,0,0,0,1）,转移：元组 描述 m1 无 m2 s7 m3 无 m4 s8 m5 无 m6 s9 m7 无,状态图,东北大学软件学院,Harel使用与方法无关的术语“团点”表示状态图的基本构件块。团点可以像维恩图显示集合包含那样地包含其他团点。团点还可以像在有向图中连接节点一样地通过边连接其他团点。,A,D,B,C,状态图中得初始状态,东北大学软件学院,A,D,B,C,进入子状态的默认入口,东北大学软件学院,A,D,B,C,状态图中的并发状态,东北大学软件学院,A,EF,B,C,D,总结,东北大学软件学院,图 有向图 用于测试的图，包括程序图、有向状态机、Petri网、状态图。,
