测试人员的图论.ppt
《测试人员的图论.ppt》由会员分享,可在线阅读,更多相关《测试人员的图论.ppt(40页珍藏版)》请在三一办公上搜索。
1、第四章 测试人员的图论,东北大学软件学院,由安博测试空间技术中心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条边的图,节点
2、的度,东北大学软件学院,定义 图中节点的度是以该节点作为端点的边的条数。我们把节点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之间存在一条边,否则该元素是
3、0。,路径,东北大学软件学院,定义 路径是一系列的边,对于序列中的任何相邻边对偶ei、ej,边都拥有相同的(节点)端点。路径可以描述为一系列边,也可以描述为一系列节点。一般更常见的是节点序列。,连接性,东北大学软件学院,定义 节点ni和nj是被连接的,当且仅当它们都在同一条路径上。“连接性”是一种图的节点集合上的等价关系。为了说明这一点,可以再复习一遍定义等价关系的三个性质:1连接性是自反的,因为每个节点显然都在到其本身长度为0的路径上。2连接性是对称的,由于如果ni和nj在一条路径上,则nj和ni也在同一条路径上。3连接性是传递的。,组件,东北大学软件学院,定义 图的组件是相连节点的最大集合
4、。等价类中的节点是图的组件。图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,n
5、2,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(
6、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来说,第一条边的终止节点是第二条边的初始节点。环路是一个在同一个节点上开始和结束的有向路径。(有向)半路径是一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 测试 人员
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6126361.html