关于一类具有较大围长的代数二部图的研究

发布时间：2017-10-21 08:35

  本文关键词：关于一类具有较大围长的代数二部图的研究

  更多相关文章： 围长 代数图 组合数 有限域 路径

【摘要】：代数二部图D(k,q)首先是由Lazebni k和Ustimenko于1995年提出,它是一类具有较大围长,q-正则并且边传递的代数二部图.由于其具有较大的围长,也就是最短环的长度比较大,因此在很多领域中都有着重要的应用,尤其广泛应用于极端图论,有限几何,编码理论和密码学等领域.关于二部图D(k,q)有一个著名的猜想：猜想A：当k为奇数且素数幂q≥4时,二部图D(k,q)的围长等于k+5.在[1]中证明了当k为奇数并且(k+5)/2|(q-1)时猜想A是成立的,其中q为某个素数幂.进一步在[2]中证明了在另一种特定的情形下猜想A也是成立的,此时k为奇数,q=pm,k=2ps-5,其中p是一个素数,s,m均为正整数.本文证明了猜想A在更一般的情形下也是成立的.本文主要通过将一般的组合数在有限域上进行推广,然后给出了推广的组合数的一些重要性质,并且利用这些性质对上述猜想A做了进一步的分析.主要内容如下：首先介绍代数二部图D(k,q)的相关概念,国内外研究现状及其应用,之后介绍了一类与其同构的代数二部图λ(k,q)的构造以及λ(k,q)中路径的显式表达式,介绍了已知的一种特定情形下关于猜想A的证明.接着我们将普通的组合数在有限域上进行了推广,对于阶为h的元素6和非负整数k,s,我们定义了新的组合数θ(k,s)：证明了组合数θ(k,s)的若干个性质,这些性质都可以看做是一般组合恒等式在有限域上的推广.利用这些性质,我们进一步证明了当q=pm,2h|(q-1),k=2hps-5时猜想A也是成立的,其中p为素数,h为正整数.
【关键词】：围长 代数图 组合数 有限域 路径
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要2-3
• ABSTRACT3-5
• 第一章 绪论5-10
• 第二章 与D(k,q)同构的二部图λ(k,q)10-20
• 2.1 二部图λ(k,q)的构造10-12
• 2.2 二部图λ(k,q)中的路径及ρ_s(ω_1,ω_2,...,ω_n)的定义12-20
• 第三章 组合数在有限域上的推广20-35
• 3.1 组合数θ(k,s)的定义20-21
• 3.2 组合数θ(k,s)的性质21-29
• 3.3 在更一般情形下代数二部图λ(k,q)的围长及猜想的证明29-35
• 结束语35-36
• 参考文献36-38
• 致谢38-39

【相似文献】

中国期刊全文数据库 前10条

1 王洪伟;;二部图匹配强迫数的谱[J];山东大学学报(理学版);2009年12期

2 张国志;王世英;;饱和二部图[J];晋中学院学报;2010年03期

3 王文虎;杨雨;;二部图的所有极大匹配[J];电脑开发与应用;2011年08期

4 谢政，，陈浩光;赋双权二部图中最大权最小权完美匹配[J];国防科技大学学报;1994年04期

5 舒辉四;连通弦二部图的H－分类[J];广东机械学院学报;1995年01期

6 谢政,陈挚,许晓冬;赋权二部图最大匹配的灵敏分析[J];数学理论与应用;2002年01期

7 田晓明;对有向二部图求最大匹配集矩阵算法的研究[J];数理医药学杂志;2002年03期

8 田俊华;求二部图完全匹配的一种回溯算法[J];榆林学院学报;2003年03期

9 马美杰,戴珍香;二连通二部图的偶泛圈性[J];烟台大学学报(自然科学与工程版);2003年04期

10 张同全,李建平;二部图上的K_(1,m)划分问题[J];云南大学学报(自然科学版);2005年04期

中国重要会议论文全文数据库 前4条

1 常迎香;;一类无完美匹配的二部图[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 李小强;张宁;;基于邻接矩阵的二部图的判定方法[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

3 吴宏林;刘绍明;;基于二部图最大匹配的汉日词对齐[A];内容计算的研究与应用前沿——第九届全国计算语言学学术会议论文集[C];2007年

4 姚家保;古天龙;徐周波;;二部图无权最大匹配的符号OBDD算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

中国博士学位论文全文数据库 前7条

1 孙静;二部图参数与圈型结构研究[D];华中师范大学;2014年

2 王洪伟;二部图的匹配强迫数[D];兰州大学;2008年

3 边红;图中的若干极值问题[D];厦门大学;2008年

4 马丽;素数幂与2倍素数幂阶局部本原图[D];云南大学;2012年

5 叶萌;图张开及其在互极大图与互极大理想图中的应用[D];上海交通大学;2013年

6 刘赛华;若干图类的κ-共振问题的研究[D];兰州大学;2010年

7 吕华众;图的条件匹配排除问题的计算复杂性和平衡超立方图的若干网络性质[D];兰州大学;2013年

中国硕士学位论文全文数据库 前10条

1 王雅静;基于二部图网络的协同过滤推荐算法研究[D];燕山大学;2015年

2 韩路;基于核心图的标签传播社团划分算法[D];南京信息工程大学;2015年

3 张文琦;均衡二部图中的2-因子[D];山东理工大学;2010年

4 胡琳;二部图的列表着色问题[D];新疆大学;2004年

5 杨帆;（3，4）-双向正则二部图的区间着色[D];华中师范大学;2008年

6 丁立佳;二部图完美匹配计数与禁位排列[D];大连交通大学;2014年

7 冯文丽;关于二部图的两个结果[D];山西大学;2005年

8 李斌;关于两类二部图能量的探究[D];青海师范大学;2010年

9 孙晓萌;基于社团划分和加权二部图网络的个性化推荐算法研究[D];河北工业大学;2015年

10 宋一兵;二部图的距离和问题[D];华中师范大学;2014年

本文编号：1072318