测试人员的图论.pptx
《测试人员的图论.pptx》由会员分享,可在线阅读,更多相关《测试人员的图论.pptx(39页珍藏版)》请在咨信网上搜索。
1、图图东北大学软件学院东北大学软件学院图图(又又叫叫做做线线性性图图)是是一一种种由由两两个个集集合合定定义义的的抽抽象象数数学学结结构,即一个节点集合和一个构成节点之间连接的边集合。构,即一个节点集合和一个构成节点之间连接的边集合。定义定义 图图G=(VG=(V,E)E)由由节节点点的的有有限限(并并且且非非空空)集集合合V V和和节节点点无序对偶集合无序对偶集合E E组成。组成。V=nV=n1 1,n n2 2,n nm m)和和 E=eE=el l,e e2 2,e ep p 其中每条边其中每条边e ek k=(n=(ni i,n nj)j),n ni i、n nj j V V。举例东北大
2、学软件学院东北大学软件学院V=nV=nl l,n n2 2,n n3 3,n n4 4,n n5 5,n n6 6,n n7 7)E=eE=e1 1,e e2 2,e e3 3,e e4 4,e e5 5=(n=(nl l,n n2 2),(n(nl l,n n4 4),(n(n3 3,n n4 4),(n(n2 2,n n5 5),(n(n4 4,n n6 6)图图4-1 4-1 有有7 7个节点和个节点和5 5条边的图条边的图n1n2n4n3n5n6n7e1e2e3e4e5节点的度东北大学软件学院东北大学软件学院定义定义 图中节点的度是以该节点作为端点的边的条数。我们图中节点的度是以该节点
3、作为端点的边的条数。我们把节点把节点n n的度记做的度记做deg(n)deg(n)。deg(ndeg(n1 1)=2)=2 deg(n deg(n2 2)=2)=2 deg(n deg(n3 3)=1)=1 deg(n deg(n4 4)=3)=3 deg(n deg(n5 5)=1)=1 deg(n deg(n6 6)=1)=1 deg(n deg(n7 7)=0)=0 关联矩阵关联矩阵东北大学软件学院东北大学软件学院定义定义 拥拥有有m m个个节节点点和和n n条条边边的的图图G=(VG=(V,E)E)的的关关联联矩矩阵阵是是一一种种mnmn矩矩阵阵,其其中中第第i i行行第第j j列列的
4、的元元素素是是1 1,当当且且仅仅当当节节点点i i是是边边j j的一个端点,否则该元素是的一个端点,否则该元素是0 0。e1e2e3e4e5n111000n210010n300100n401101n500010n600001n700000相邻矩阵相邻矩阵东北大学软件学院东北大学软件学院定义定义 拥拥有有m个个节节点点和和n条条边边的的图图G=(V,E)的的相相邻邻矩矩阵阵是是一一种种mm矩矩阵阵,其其中中第第i行行第第j列列的的元元素素是是1,当当且且仅仅当当节节点点i和和节点节点j之间存在一条边,否则该元素是之间存在一条边,否则该元素是0。n1n2n3n4n5n6n7n10101000n2
5、1000100n30001000n41010010n50100000n60001000n70000000路径路径东北大学软件学院东北大学软件学院定义定义 路路径径是是一一系系列列的的边边,对对于于序序列列中中的的任任何何相相邻邻边边对对偶偶ei、ej,边都拥有相同的,边都拥有相同的(节点节点)端点。端点。路路径径可可以以描描述述为为一一系系列列边边,也也可可以以描描述述为为一一系系列列节节点点。一般更常见的是节点序列。一般更常见的是节点序列。路径节点序列边序列n1和n5之间n1,n2,n5e1,e4n6和n5之间n6,n4,n1,n2,n5e5,e2,e1,e4n3和n2之间n3,n4,n1,
6、n5e3,e2,e1连接性连接性东北大学软件学院东北大学软件学院定义定义 节节点点ni和和nj是是被被连连接接的的,当当且且仅仅当当它它们们都都在在同同一一条条路路径径上。上。“连连接接性性”是是一一种种图图的的节节点点集集合合上上的的等等价价关关系系。为为了了说说明这一点,可以再复习一遍定义等价关系的三个性质:明这一点,可以再复习一遍定义等价关系的三个性质:1连连接接性性是是自自反反的的,因因为为每每个个节节点点显显然然都都在在到到其其本本身身长度为长度为0的路径上。的路径上。2连连接接性性是是对对称称的的,由由于于如如果果ni和和nj在在一一条条路路径径上上,则则nj和和ni也在同一条路径
7、上。也在同一条路径上。3连接性是传递的。连接性是传递的。组件组件东北大学软件学院东北大学软件学院定义定义 图的组件是相连节点的最大集合。图的组件是相连节点的最大集合。等价类中的节点是图的组件。图等价类中的节点是图的组件。图4-1种的图有两个组件:种的图有两个组件:n1,n2,n3,n4,n5,n6 n7压缩图压缩图东北大学软件学院东北大学软件学院定义定义 给给定定图图G=(V,E),其其压压缩缩图图通通过过用用压压缩缩节节点点替替代代每每个个组件构成。组件构成。给定图的压缩图是惟一的。给定图的压缩图是惟一的。S1 =n1,n2,n3,n4,n5,n6S2=n7圈数圈数东北大学软件学院东北大学软
8、件学院定义定义 图图G的圈数由的圈数由V(G)=e n+p给出,其中:给出,其中:e是是G中的边数。中的边数。n是是G中的节点数。中的节点数。p是是G中的组件数。中的组件数。有向图有向图东北大学软件学院东北大学软件学院定义定义 有有向向图图(或或框框图图)D=(V,E)包包含含:一一个个节节点点的的有有限限集集合合V=(n1,n2,nm),一一个个边边的的集集合合E=e1,e2,ep,其其中中每每条条边边ek=是是节节点点ni、njV的的一一个个有有序序对偶。对偶。有向图例子有向图例子东北大学软件学院东北大学软件学院n1n2n4n3n5n6n7e1e2e3e4e5V=nV=nl l,n n2
9、2,n n3 3,n n4 4,n n5 5,n n6 6,n n7 7)E=eE=e1 1,e e2 2,e e3 3,e e4 4,e e5 5=n=,n,n,n,n 图图4-2 4-2 一个有向图一个有向图外度和内度外度和内度东北大学软件学院东北大学软件学院定义定义 有有向向图图中中节节点点的的内内度度,是是将将该该节节点点作作为为终终止止节节点点的的不不同边的条数。节点同边的条数。节点n n的内度记做的内度记做indeg(n)有有向向图图中中节节点点的的外外度度,是是将将该该节节点点作作为为开开始始节节点点的的不不同边的条数。节点同边的条数。节点n n的外度记做的外度记做outdeg(
10、n)indeg(n indeg(n1 1)=0 Outdeg(n)=0 Outdeg(n1 1)=2)=2 indeg(n indeg(n2 2)=1 Outdeg(n)=1 Outdeg(n2 2)=1)=1 indeg(n indeg(n3 3)=0 Outdeg(n)=0 Outdeg(n3 3)=1)=1 indeg(n indeg(n4 4)=2 Outdeg(n)=2 Outdeg(n4 4)=1)=1 indeg(n indeg(n5 5)=1 Outdeg(n)=1 Outdeg(n5 5)=0)=0 indeg(n indeg(n6 6)=1 Outdeg(n)=1 Outd
11、eg(n6 6)=0)=0 indeg(n indeg(n7 7)=0 Outdeg(n)=0 Outdeg(n7 7)=0)=0节点的类型节点的类型东北大学软件学院东北大学软件学院定义定义 内度为内度为0 0的节点是源节点。的节点是源节点。外度为外度为0 0的节点是吸收节点。的节点是吸收节点。内度不为内度不为0 0,并且外度不为,并且外度不为0 0的节点是传递节点。的节点是传递节点。有向图的相邻矩阵有向图的相邻矩阵东北大学软件学院东北大学软件学院 定义定义 有有m m个个节节点点的的有有向向图图D D=(V(V,E)E)的的相相邻邻矩矩阵阵是是一一种种mmmm矩矩阵阵:A A=(a(i(a(
12、i,j)j),其其中中a(ia(i,j)j)是是1 1,当当且且仅仅当从节点当从节点i i到节点到节点j j有一条边,否则该元素为有一条边,否则该元素为0 0。n1n2n3n4n5n6n7n10101000n20000100n30001000n40000010n50000000n60000000n70000000路径和半路径路径和半路径东北大学软件学院东北大学软件学院定义定义 (有有向向)路路径径是是一一系系列列边边,使使得得对对于于该该序序列列中中的的所所有有相相邻邻边边对对偶偶e ei i,e,ej j来来说说,第第一一条条边边的的终终止止节节点点是是第第二二条条边边的初始节点。的初始节点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 测试 人员
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。