超图的理论及其应用的研究

超图是离散数学中最具一般性的结构。信息科学家在研究数据库时，发现超图圈的传统定义与数据库的结构不符，因而引入无圈超图的新概念，并指出其非常有用。后来的理论结果也均表明无圈超图的定义是科学的。在无圈超图的研究中，圈公理被发现。科学家证明了一个超图是无圈的当且仅当它没有圈公理界定的圈。圈公理界定的圈既是局部结构，也是整体结构，这是离散数学中的新模式。圈公理清楚地显示图是超图的退化情况。圈公理极为深刻，构成了超图的理论基础。一个新的超图理论体系开始形成，许多新问题有待解决，理论体系有待进一步发展。本项目将研究这个理论体系中的若干基本问题，主要研究超图的性质、结构、规模、计数、无圈分解、圈分解、Hamilton圈分解等。我们将致力于探讨运用经典数学中的数论、群论、组合学等理论并结合计算机算法来研究上述问题，以培养青年教师和研究生的科研能力，推动新超图理论体系的发展，带动内蒙地区科研水平的提高。

课题组主要对无圈超图的规模、超图的Hamilton圈分解、超图的非Hamilton圈分解、超图的圈结构及超图的圈分解在组合设计中的应用做了研究．以此项目为依托，培养了青年教师和研究生的科研能力，推动了新超图理论体系的发展，对设计、图的交叉数、控制理论等领域开始研究．. 课题组研究了n阶(d)-连通-k-一致无圈超图的规模和非严格(d)-连通-k-匀齐无圈超图的规模，并分别得到它们的上下界，该成果发表在《应用数学学报》上．利用边划分方法和圈模型，对完全3-一致超图Kn3的Hamilton分解进行了研究，得到了Kn3的Hamilton分解的算法及n=6k+2,6k+4(k=1,2,3,4,5,6,7),n=6k+5.(k=1,2,3,4,5,6)时的圈分解．这一结果将Meszka-Rosa关于Kn3的哈密顿圈分解结果从n≤32提高到了n≤46(n≠43)，该成果发表在《数学学报》上．给出了Kn3的基础l-圈的定义，研究了Kn3的5-圈分解和7-圈分解，得到了：对于某些n， Kn3可以5-圈分解，完全二部3-一致超图K(5,5)3可以5-圈分解；若Kn3可以5-圈分解，则K(5n)3可以5-圈分解；对于某些n，K(5mn)3可以5-圈分解；对于某些n，Kn3可以7-圈分解； 如果Kn3可以7-圈分解，那么K(7n)3的7-圈分解存在；对于某些n，K(7mn)3可以7-圈分解；K (15)3-H(5,5)的长度为5的圈分解；K(11,11)3可以5-圈分解．研究了圈分解在设计及t-设计的大集中的应用．证得：存在大集LS[5](2,3,22),λ=4和LS[1](3,3,22),λ=1；对于某些λ，存在平衡设计S(3,C5,λ)；对于某些λ，存在平衡设计S(3,C7,λ)． 应用设计理论给出当n=7,10时Kn3分解成圈.对王建方界定的圈公理定义下的圈与其它学者定义的圈做了比较研究，得出王建方界定的圈公理是科学的，合理的，符合数据库的要求．在单边消去与收缩下，确定了极小连通简单r-一致超图的极小亚图．对王建方定义的虚圈和实圈的一些性质做了进一步的研究，给出了三个定理，对超图中的虚圈和实圈的概念进行了完善．对王建方的《超图的理论基础》一书中的概念进行了解读并补充一些新内容．2013年7月13日承办了中国运筹学会图论组合分会第五届图论与组合算法国际研讨会．