学习笔记 (5)
上一篇 /
下一篇 2007-05-28 20:14:02
/ 个人分类:软件测试学习笔记
又要介绍概念了,其实连我自己都没有理解这些定义,居然还写出来实在是误人子弟了,所以大家如果看到不对的地方大可不必大惊小怪。去Google上搜一下保证有更好的解释。开始。
图中节点的度是以该节点最为端点的边的条数。
图论与关联矩阵之间的关系:拥有m个节点和n条边的图G=(V,E)的关联矩阵是一种m*n的矩阵,其中第i行第j列的元素是1,当且仅当节点i是边j的一个端点,否则该元素是0。通过研究可以发现任何列的表项和为2,这是因为每条边恰好有两个端点;另外,行的和是节点的度。如果节点的度是0,则说这个节点是孤立的。
相邻矩阵:拥有m个节点和n条边的图G=(V,E)的相邻矩阵是一种m*m矩阵,其中第i行第j列的元素是1,当且仅当节点i和节点j之间存在一条边,否则该元素是0。行的和是节点的度。
图中的路径:是一系列的边,对于序列中的任何相邻边对偶ei,ej,边都拥有相同的(节点)端点。
另一个概念,组件:图的组件是相连节点的最大集合。
图的另一个性质,圈数:图G的圈数由V(G)=e-n+p给出,其中:e是G的边数n是G中的节点数p是G中的组件数。
下面介绍有向图,
有向图中节点的内度,是将该节点作为终止节点的不同边的条数。有向图中节点的外度,是将该节点作为开始节点的不同边的条数。(呵呵,真是来而不往非礼也)。由此可见,一般图和有向图对于度的概念之间的联系是:deg(n)=indeg(n)+outdeg(n)。
节点的类型:内度为0的节点是源节点,外度为0的节点是吸收节点。内度不为0,并且外度不为0的节点是传递节点。既是源节点又是汇节点(吸收节点)的节点是孤立节点。
收藏
举报
TAG:
软件测试学习笔记