测试人员的图论.pptx

图图东北大学软件学院东北大学软件学院图图(又又叫叫做做线线性性图图)是是一一种种由由两两个个集集合合定定义义的的抽抽象象数数学学结结构，即一个节点集合和一个构成节点之间连接的边集合。构，即一个节点集合和一个构成节点之间连接的边集合。定义定义 图图G=(VG=(V，E)E)由由节节点点的的有有限限(并并且且非非空空)集集合合V V和和节节点点无序对偶集合无序对偶集合E E组成。组成。V=nV=n1 1，n n2 2，n nm m)和和 E=eE=el l，e e2 2，e ep p 其中每条边其中每条边e ek k=(n=(ni i，n nj)j)，n ni i、n nj j V V。举例东北大学软件学院东北大学软件学院V=nV=nl l，n n2 2，n n3 3，n n4 4，n n5 5，n n6 6，n n7 7)E=eE=e1 1，e e2 2，e e3 3，e e4 4，e e5 5=(n=(nl l，n n2 2)，(n(nl l，n n4 4)，(n(n3 3，n n4 4)，(n(n2 2，n n5 5)，(n(n4 4，n n6 6)图图4-1 4-1 有有7 7个节点和个节点和5 5条边的图条边的图n1n2n4n3n5n6n7e1e2e3e4e5节点的度东北大学软件学院东北大学软件学院定义定义 图中节点的度是以该节点作为端点的边的条数。我们图中节点的度是以该节点作为端点的边的条数。我们把节点把节点n n的度记做的度记做deg(n)deg(n)。deg(ndeg(n1 1)=2)=2 deg(n deg(n2 2)=2)=2 deg(n deg(n3 3)=1)=1 deg(n deg(n4 4)=3)=3 deg(n deg(n5 5)=1)=1 deg(n deg(n6 6)=1)=1 deg(n deg(n7 7)=0)=0 关联矩阵关联矩阵东北大学软件学院东北大学软件学院定义定义 拥拥有有m m个个节节点点和和n n条条边边的的图图G=(VG=(V，E)E)的的关关联联矩矩阵阵是是一一种种mnmn矩矩阵阵，其其中中第第i i行行第第j j列列的的元元素素是是1 1，当当且且仅仅当当节节点点i i是是边边j j的一个端点，否则该元素是的一个端点，否则该元素是0 0。e1e2e3e4e5n111000n210010n300100n401101n500010n600001n700000相邻矩阵相邻矩阵东北大学软件学院东北大学软件学院定义定义 拥拥有有m个个节节点点和和n条条边边的的图图G=(V，E)的的相相邻邻矩矩阵阵是是一一种种mm矩矩阵阵，其其中中第第i行行第第j列列的的元元素素是是1，当当且且仅仅当当节节点点i和和节点节点j之间存在一条边，否则该元素是之间存在一条边，否则该元素是0。n1n2n3n4n5n6n7n10101000n21000100n30001000n41010010n50100000n60001000n70000000路径路径东北大学软件学院东北大学软件学院定义定义 路路径径是是一一系系列列的的边边，对对于于序序列列中中的的任任何何相相邻邻边边对对偶偶ei、ej，边都拥有相同的，边都拥有相同的(节点节点)端点。端点。路路径径可可以以描描述述为为一一系系列列边边，也也可可以以描描述述为为一一系系列列节节点点。一般更常见的是节点序列。一般更常见的是节点序列。路径节点序列边序列n1和n5之间n1，n2，n5e1，e4n6和n5之间n6，n4，n1，n2，n5e5，e2，e1，e4n3和n2之间n3，n4，n1，n5e3，e2，e1连接性连接性东北大学软件学院东北大学软件学院定义定义 节节点点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=e1，e2，ep，其其中中每每条条边边ek=是是节节点点ni、njV的的一一个个有有序序对偶。对偶。有向图例子有向图例子东北大学软件学院东北大学软件学院n1n2n4n3n5n6n7e1e2e3e4e5V=nV=nl l，n n2 2，n n3 3，n n4 4，n n5 5，n n6 6，n n7 7)E=eE=e1 1，e e2 2，e e3 3，e e4 4，e e5 5=n=，n，n，n，n 图图4-2 4-2 一个有向图一个有向图外度和内度外度和内度东北大学软件学院东北大学软件学院定义定义 有有向向图图中中节节点点的的内内度度，是是将将该该节节点点作作为为终终止止节节点点的的不不同边的条数。节点同边的条数。节点n n的内度记做的内度记做indeg(n)有有向向图图中中节节点点的的外外度度，是是将将该该节节点点作作为为开开始始节节点点的的不不同边的条数。节点同边的条数。节点n n的外度记做的外度记做outdeg(n)indeg(n indeg(n1 1)=0 Outdeg(n)=0 Outdeg(n1 1)=2)=2 indeg(n indeg(n2 2)=1 Outdeg(n)=1 Outdeg(n2 2)=1)=1 indeg(n indeg(n3 3)=0 Outdeg(n)=0 Outdeg(n3 3)=1)=1 indeg(n indeg(n4 4)=2 Outdeg(n)=2 Outdeg(n4 4)=1)=1 indeg(n indeg(n5 5)=1 Outdeg(n)=1 Outdeg(n5 5)=0)=0 indeg(n indeg(n6 6)=1 Outdeg(n)=1 Outdeg(n6 6)=0)=0 indeg(n indeg(n7 7)=0 Outdeg(n)=0 Outdeg(n7 7)=0)=0节点的类型节点的类型东北大学软件学院东北大学软件学院定义定义 内度为内度为0 0的节点是源节点。的节点是源节点。外度为外度为0 0的节点是吸收节点。的节点是吸收节点。内度不为内度不为0 0，并且外度不为，并且外度不为0 0的节点是传递节点。的节点是传递节点。有向图的相邻矩阵有向图的相邻矩阵东北大学软件学院东北大学软件学院 定义定义 有有m m个个节节点点的的有有向向图图D D=(V(V，E)E)的的相相邻邻矩矩阵阵是是一一种种mmmm矩矩阵阵：A A=(a(i(a(i，j)j)，其其中中a(ia(i，j)j)是是1 1，当当且且仅仅当从节点当从节点i i到节点到节点j j有一条边，否则该元素为有一条边，否则该元素为0 0。n1n2n3n4n5n6n7n10101000n20000100n30001000n40000010n50000000n60000000n70000000路径和半路径路径和半路径东北大学软件学院东北大学软件学院定义定义 (有有向向)路路径径是是一一系系列列边边，使使得得对对于于该该序序列列中中的的所所有有相相邻邻边边对对偶偶e ei i,e,ej j来来说说，第第一一条条边边的的终终止止节节点点是是第第二二条条边边的初始节点。的初始节点。环路是一个在同一个节点上开始和结束的有向路径。环路是一个在同一个节点上开始和结束的有向路径。(有有向向)半半路路径径是是一一系系列列边边，使使得得对对于于该该序序列列中中至至少少有有一一个个相相邻邻边边对对偶偶e ei i,e,ej j来来说说，第第一一条条边边的的初初始始节节点点是是第第二二条条边边的的初初始始节节点点，或或第第一一条条边边的的终终止止节节点点是是第第二二条条边边的终止节点。的终止节点。可到达性矩阵可到达性矩阵东北大学软件学院东北大学软件学院定义定义 有有m m个个节节点点的的有有向向图图D D=(V(V，E)E)的的可可达达性性矩矩阵阵是是一一种种mmmm矩矩阵阵R R=(r(i,j)(r(i,j)，其其中中r(ir(i，j)j)是是1 1，当当且且仅仅当当从从节点节点i i到节点到节点j j有一条路径，否则该元素为有一条路径，否则该元素为0 0。有有向向图图D D的的可可到到达达性性矩矩阵阵可可以以通通过过相相邻邻矩矩阵阵A A计计算算如如下：下：R R=I+A+AI+A+A2 2+A+A3 3+A+Ak k其中其中k k是是D D最长路径的长度，最长路径的长度，I I是单位矩阵。是单位矩阵。图图4-2的可到达性矩阵的可到达性矩阵东北大学软件学院东北大学软件学院n1n2n3n4n5n6n7n10101110n20000100n30001010n40000010n50000000n60000000n70000000n-连接性连接性东北大学软件学院东北大学软件学院定义定义 有向图中的两个节点有向图中的两个节点ni和和nj是：是：0-0-连接，当且仅当连接，当且仅当ni和和nj之间没有路径。之间没有路径。l-l-连连接接，当当且且仅仅当当ni和和nj之之间间有有一一条条半半路路径径，但但是是没没有路径。有路径。2-2-连接，当且仅当连接，当且仅当从从ni和和nj之间有一条路径。之间有一条路径。3-3-连连接接，当当且且仅仅当当从从ni和和nj有有一一条条路路径径，并并且且从从n nj j到到n ni i有一条路径。有一条路径。图图4-2的连接性的连接性东北大学软件学院东北大学软件学院n n1 1和和n n7 7是是0 0连接。连接。n n2 2和和n n6 6是是1 1连接。连接。n n1 1和和n n6 6是是2 2连接。连接。n n3 3和和n n6 6是是3 3连接。连接。n1n2n4n3n5n6n7e1e2e3e4e5强组件强组件东北大学软件学院东北大学软件学院定义定义 有向图的强组件是有向图的强组件是3 3-连接节点的最大集合。连接节点的最大集合。n1n2S1n5S2e1e2e4n4n3n6e3e5n7用于测试的图用于测试的图东北大学软件学院东北大学软件学院 程序图程序图 有限状态机有限状态机 Petri网网 状态图状态图程序图程序图东北大学软件学院东北大学软件学院定义定义 给给定定一一个个采采用用命命令令式式程程序序设设计计语语言言编编写写的的程程序序，其其程程序图是一种有向图，其中：序图是一种有向图，其中：1(传统定义传统定义)节节点点是是程程序序语语句句，边边表表示示控控制制流流(从从节节点点i到到节节点点j有有一一条条边边，当当且且仅仅当当对对应应节节点点j的的语语句句可可以以立立即即在在节节点点i对对应应的语句之后执行的语句之后执行)。2(经过改进的定义经过改进的定义)节节点点要要么么是是整整个个语语句句，要要么么是是语语句句的的一一部部分分，边边表表示示控控制制流流(从从节节点点i到到节节点点j有有一一条条边边，当当且且仅仅当当对对应应节节点点j的的语语句句或或语语句句的的一一部部分分，可可以以立立即即在在节节点点i对对应应的的语语句句或语句的一部分之或语句的一部分之后执行后执行)。结构化程序设计构造的有向图结构化程序设计构造的有向图东北大学软件学院东北大学软件学院串行IF-ThenIF-Then-Else条件前测试环路后测试环路有限状态机有限状态机东北大学软件学院东北大学软件学院有有限限状状态态机机是是一一种种有有向向图图，其其中中状状态态是是节节点点，转转移移是是边边。源源状状态态和和吸吸收收状状态态是是初初始始节节点点和和终终止止节节点点，路路径径被被建建模模为为通通路路，等等等等。大大多多数数有有限限状状态态机机表表示示方方法法都都要要为为边边(转转移移)增增加加信信息息，以以指指示示转转移移的的原原因因和和作作为为转转移移的的结结果果要发生的行动。要发生的行动。用于用于PIN尝试的有限状态机尝试的有限状态机东北大学软件学院东北大学软件学院Petri网网东北大学软件学院东北大学软件学院定义定义 Petri网网是是一一种种双双向向有有向向图图(P，T，In，Out)，其其中中，P和和T是不相交的节点集合，是不相交的节点集合，In和和Out是边集合，是边集合，In PT，Out TP。P1P5P2P3P4t1t2t3有标记的有标记的Petri网网东北大学软件学院东北大学软件学院定义定义 有有标标记记的的Petri网网是是一一种种5元元组组(P，T，In，Out，M)，其其中中(P，T，In，Out)是是一一个个Petri网网，M是是从从地地点点到到正整数的映射集合。正整数的映射集合。t1p1p5p2t3p4p3t2Petri网网的的标标记记元元组组是是。两个基本定义两个基本定义东北大学软件学院东北大学软件学院 定义定义 转转移移可可以以在在Petri网网中中发发生生，如如果果在在其其所所有有输输入入地地点点中中至少有一个记号。至少有一个记号。定义定义 当当触触发发Petri网网一一个个转转移移时时，要要从从其其每每个个输输入入地地点点删删除除一个记号，并在其每个删除地点增加一个记号。一个记号，并在其每个删除地点增加一个记号。两个基本定义两个基本定义东北大学软件学院东北大学软件学院t1p1p5p2t3p4p3t2t1p1p5p2t3p4p3t2M=，事件驱动的事件驱动的Petri网网 东北大学软件学院东北大学软件学院定义定义 EDPNEDPN是一种多向图是一种多向图(P(P，D D，S S，InIn，Out)Out)，包括三个节，包括三个节点集合点集合P P、D D和和S S，以及两个映射集合，以及两个映射集合InIn和和OutOut。其中：。其中：P P是端口事件的集合。是端口事件的集合。D D是数据地点的集合。是数据地点的集合。S S是转移的集合。是转移的集合。InIn是是(PD)S(PD)S的有序对偶集合。的有序对偶集合。OutOut是是S(PD)S(PD)的有序对偶集合。的有序对偶集合。EDPN图图 东北大学软件学院东北大学软件学院p3d5p4p3d6p4d7s7s8s10s9为为EDPN做标记做标记 东北大学软件学院东北大学软件学院定义定义 EDPN(PEDPN(P，D D，S S，InIn，Out)Out)的一个标记的一个标记M M，是，是p p元组的一元组的一个序列个序列M M=m，其中，其中p p=k+nk+n，k k和和n n是集合是集合P P和和D D中的中的元素个数，元素个数，p p元组中的个体项表示事件或数据地点中的记元组中的个体项表示事件或数据地点中的记号个数。号个数。EDPN图中的标记图中的标记和转移和转移东北大学软件学院东北大学软件学院p3d5p4p3d6p4d7s7s8s10s9标记：标记：元组元组 （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使使用用与与方方法法无无关关的的术术语语“团团点点”表表示示状状态态图图的的基基本本构构件件块块。团团点点可可以以像像维维恩恩图图显显示示集集合合包包含含那那样样地地包包含含其其他他团团点点。团团点点还还可可以以像像在在有有向向图图中中连连接接节节点点一一样样地地通通过边连接其他团点。过边连接其他团点。ADBC状态图中得初始状态状态图中得初始状态东北大学软件学院东北大学软件学院ADBC进入子状态的默认入口进入子状态的默认入口东北大学软件学院东北大学软件学院ADBC状态图中的并发状态状态图中的并发状态 东北大学软件学院东北大学软件学院AEFBCD总结总结 东北大学软件学院东北大学软件学院 图图 有向图有向图 用用于于测测试试的的图图，包包括括程程序序图图、有有向向状状态态机机、Petri网网、状态图。状态图。