资源描述:
《关于图的分数因子的若干结果》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、分一类号TP393学校单位代码矽一滓杆箱广一才、一一硕士学,位论一文论文题目一关于图的分数因一子的若千结果研究生姓名一王一娜学科、一专业计算机应用技术一研卜究方向计算机网络结构设计与分析导师姓名、职称一禹继国·副教授、论文'完成时间`年月、'`矽滓杆箱广才硕士学位论文关于图的分数因子的若干结果研究生姓名土娜学科姓职方专称名业向计算机应用技术研究计算机网络结构设计与分析禹继国导师副教授论文完成时间年月关于图的分数因子的若干结果摘要图的因子理论是图论的一个重要分支,在图论研究中得到了极大关注在日常生活中,许多诸如编码设计、积木设计,计算机网络传输、进度
2、表等关于运筹和网络设计问题都涉及到图的因子,因子分解和正交因子【其中,文件传输间题可以模拟为因子和,一因子分解或一染色,拉丁方块和空间方块的设计则涉及到图的因子和正交因子问题本文所考虑的图都是有限简单图设是一个图,是顶点集,是边集,在图中的度记为以从和以分别表示图的边连通度和连同度侧表示的最小度如果是的子集,由导出的子图的孤立节点的集合是双并且二对于两个不联通的子集,,凡,别表示一个顶点属于另一个顶点属于的边集,并且凡,刀以,刀令和是两个整数值函数对所有任满足。三抓三的一个,一因子是的一个生成子图,满足对于所有的〔,有夕三心·三习一个分数,一示性函数是一个函数,为的每条边分配一个在,
3、中的数,因此对于任意任我们有抓`心,。三,其中二兄、二的是任的分子度,并且。却任令是图的一个分数,示性函数,令、。〔自且城的笋如果、是的生成子图满足、凡,则、成为的分数,一因子如果对于所有任,抓二是一个非负整数,这个分数勿一因子称为分数一因子尤其,分数一因子也称为分数完美匹配令,”是一个图,并令夕和是两个定义在上的整数值函数且对所有的任有贝三动成立若对的每一条边都存在的一个分数,一因子。使得二,其中是、的示性函数,则称是一个分数,一消去图若在中删去尸里,`二无后,所得图有分数完美匹配,则称是分数年边一可消去的被称为分数一覆盖图,如果的每一条。,都存在一个分数,一因子、,使得城,其中是
4、、的示性函数一个简单图是分数一可扩的,如果每一个分数一匹配盯都可以被扩展成分数完美匹配、,并且对于所有的。〔盯,有是分数一因子一临界的,如果删去任意一个顶点,剩下的子图仍有分数完美匹配图是分数一覆盖的,如果的每一条边。都属于一个分数年因子、,且满足二,其中九是、的示性函数一个图是分数一可扩的,如果每一个一匹配可以被扩展成一个分数完美