文档介绍：第四章测试人员的图论东北大学软件学院由安博测试空间技术中心/ 提供图东北大学软件学院图( 又叫做线性图) 是一种由两个集合定义的抽象数学结构,即一个节点集合和一个构成节点之间连接的边集合。定义图G=(V ,E) 由节点的有限( 并且非空) 集合 V 和节点无序对偶集合 E组成。 V={n 1,n 2,…,n m) 和 E={e l,e 2,…,e p}其中每条边 e k=(n i,n j), n i、n j∈V。举例东北大学软件学院 V={n l,n 2,n 3,n 4,n 5,n 6,n 7) E={e 1,e 2,e 3,e 4,e 5}={(n l,n 2),(n l,n 4),(n 3, n 4),(n 2,n 5),(n 4,n 6)} 图4-1 有7个节点和 5条边的图 n 1n 2n 4n 3n 5n 6n 7 e 1e 2e 3e 4e 5节点的度东北大学软件学院定义图中节点的度是以该节点作为端点的边的条数。我们把节点 n的度记做 deg(n) 。 deg(n 1) = 2 deg(n 2) = 2 deg(n 3) = 1 deg(n 4) = 3 deg(n 5) = 1 deg(n 6) = 1 deg(n 7) = 0 关联矩阵东北大学软件学院定义拥有 m个节点和 n 条边的图 G=(V,E) 的关联矩阵是一种 m×n矩阵,其中第 i行第 j 列的元素是 1 ,当且仅当节点 i是边j的一个端点,否则该元素是 0。00000n 710000n 601000n 510110n 400100n 301001n 200011n 1e 5e 4e 3e 2e 1相邻矩阵东北大学软件学院定义拥有 m 个节点和 n 条边的图 G= (V , E) 的相邻矩阵是一种 m×m 矩阵,其中第 i 行第 j 列的元素是 1 ,当且仅当节点 i和节点 j之间存在一条边,否则该元素是 0。0000000n 70001000n 60000010n 50100101n 40001000n 30010001n 20001010n 1n 7n 6n 5n 4n 3n 2n 1路径东北大学软件学院定义路径是一系列的边,对于序列中的任何相邻边对偶 e i、 e j,边都拥有相同的(节点)端点。路径可以描述为一系列边,也可以描述为一系列节点。一般更常见的是节点序列。 e 3,e 2 ,e 1n 3,n 4,n 1 ,n 5n 3和n 2之间 e 5,e 2,e 1,e 4 n 6,n 4,n 1,n 2,n 5n 6和n 5之间 e 1,e 4n 1,n 2,n 5n 1和n 5之间边序列节点序列路径连接性东北大学软件学院定义节点 n i和n j 是被连接的,当且仅当它们都在同一条路径上。“连接性”是一种图的节点集合上的等价关系。为了说明这一点,可以再复习一遍定义等价关系的三个性质: 1 .连接性是自反的,因为每个节点显然都在到其本身长度为 0的路径上。 2 .连接性是对称的,由于如果 n i和n j 在一条路径上,则 n j和n i也在同一条路径上。 3 .连接性是传递的。组件东北大学软件学院定义图的组件是相连节点的最大集合。等价类中的节点是图的组件。图 4-1 种的图有两个组件: ? {n 1, n 2, n 3, n 4, n 5, n 6} ? {n 7}压缩图东北大学软件学院定义给定图 G = (V , E) ,其压缩图通过用压缩节点替代每个组件构成。给定图的压缩图是惟一的。 S 1 = {n 1,n 2,n 3,n 4,n 5,n 6} S 2 = {n 7}