《测试人员的图论》PPT课件

《《测试人员的图论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章测试人员的图论东北大学软件学院由安博测试空间技术中心http://www.btestingsky.com/提供图东北大学软件学院图(又叫做线性图)是一种由两个集合定义的抽象数学结构，即一个节点集合和一个构成节点之间连接的边集合。定义图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}=

2、{(nl，n2)，(nl，n4)，(n3，n4)，(n2，n5)，(n4，n6)}图4-1有7个节点和5条边的图n1n2n4n3n5n6n7e1e2e3e4e5节点的度东北大学软件学院定义图中节点的度是以该节点作为端点的边的条数。我们把节点n的度记做deg(n)。deg(n1)=2deg(n2)=2deg(n3)=1deg(n4)=3deg(n5)=1deg(n6)=1deg(n7)=0关联矩阵东北大学软件学院定义拥有m个节点和n条边的图G=(V，E)的关联矩阵是一种m×n矩阵，其中第i行第j列的元素是1，当且仅当节

3、点i是边j的一个端点，否则该元素是0。e1e2e3e4e5n111000n210010n300100n401101n500010n600001n700000相邻矩阵东北大学软件学院定义拥有m个节点和n条边的图G=(V，E)的相邻矩阵是一种m×m矩阵，其中第i行第j列的元素是1，当且仅当节点i和节点j之间存在一条边，否则该元素是0。n1n2n3n4n5n6n7n10101000n21000100n30001000n41010010n50100000n60001000n70000000路径东北大学软件学院定义路径是一系列

4、的边，对于序列中的任何相邻边对偶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．连接性是自反的，因为每

5、个节点显然都在到其本身长度为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，n6}S2={n7}圈数东北大学软件学院定义．图G的圈数由V(G)=e–n+p

6、给出，其中：e是G中的边数。n是G中的节点数。p是G中的组件数。有向图东北大学软件学院定义有向图（或框图）D=(V，E)包含：一个节点的有限集合V=(n1，n2，…，nm)，一个边的集合E=是节点ni、nj∈V的一个有序对偶。有向图例子东北大学软件学院n1n2n4n3n5n6n7e1e2e3e4e5V={nl，n2，n3，n4，n5，n6，n7)E={e1，e2，e3，e4，e5}={，，，，

7、}图4-2一个有向图外度和内度东北大学软件学院定义有向图中节点的内度，是将该节点作为终止节点的不同边的条数。节点n的内度记做indeg(n)有向图中节点的外度，是将该节点作为开始节点的不同边的条数。节点n的外度记做outdeg(n)indeg(n1)=0Outdeg(n1)=2indeg(n2)=1Outdeg(n2)=1indeg(n3)=0Outdeg(n3)=1indeg(n4)=2Outdeg(n4)=1indeg(n5)=1Outdeg(n5)=0indeg(n6)=1Outdeg(n6)=0indeg(n

8、7)=0Outdeg(n7)=0节点的类型东北大学软件学院定义内度为0的节点是源节点。外度为0的节点是吸收节点。内度不为0，并且外度不为0的节点是传递节点。有向图的相邻矩阵东北大学软件学院定义有m个节点的有向图D=(V，E)的相邻矩阵是一种m×m矩阵：A=(a(i，j))，其中a(i，j)是1，当且仅当从节点i到节点j有一条边，否则该元素为0。