测试人员的图论-Read.PPT

第四章 测试人员的图论 图 举例 节点的度 关联矩阵 相邻矩阵 路径 连接性 组件 压缩图 圈数 有向图 有向图例子 外度和内度 节点的类型 有向图的相邻矩阵 路径和半路径 可到达性矩阵 图4-2的可到达性矩阵 n-连接性 图4-2的连接性 强组件 用于测试的图 程序图 结构化程序设计构造的有向图 有限状态机 用于PIN尝试的有限状态机 Petri网 有标记的Petri网 两个基本定义 两个基本定义 事件驱动的Petri网 EDPN图 为EDPN做标记 EDPN图中的标记和转移 状态图 状态图中得初始状态 进入子状态的默认入口 状态图中的并发状态 总结 东北大学软件学院 定义 EDPN是一种多向图(P，D，S，In，Out)，包括三个节点集合P、D和S，以及两个映射集合In和Out。其中： P是端口事件的集合。 D是数据地点的集合。 S是转移的集合。 In是(P∪D)×S的有序对偶集合。 Out是S×(P∪D)的有序对偶集合。 东北大学软件学院 p3 d5 p4 p3 d6 p4 d7 s7 s8 s10 s9 东北大学软件学院 定义 EDPN(P，D，S，In，Out)的一个标记M，是p元组的一个序列M=m1，m2，…，其中p=k+n，k和n是集合P和D中的元素个数，p元组中的个体项表示事件或数据地点中的记号个数。 东北大学软件学院 p3 d5 p4 p3 d6 p4 d7 s7 s8 s10 s9 标记：元组 （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 * 东北大学软件学院 东北大学软件学院 图(又叫做线性图)是一种由两个集合定义的抽象数学结构，即一个节点集合和一个构成节点之间连接的边集合。 定义 图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。 0 0 0 0 0 n7 1 0 0 0