图与超图的哈密顿圈问题研究

摘要

本文研究了图与超图的哈密顿圈问题。分为图的哈密顿圈问题和超图的哈密顿圈问题两部分。对于研究背景和概况以及各章节相关定义在第一章绪论部分将会给出。
　　在图的哈密顿圈问题部分，分为两章，主要讨论了一些特定条件下图的哈密顿圈计数和构造问题。对图的哈密顿圈问题研究主要以鲁卡斯提出的夫妻围圆桌入座问题以及推广问题为依托分别展开研究。主要包括n对夫妻沿一条直线桌入座问题;n对夫妻沿两条直线桌入座问题;n对夫妻沿三条直线桌入座问题等。在这一部分，主要应用了正行列式法，序列法，根据集合等势关系递推等方法进行研究。并在每一节均给出了相应特定条件下图的哈密顿圈构造和计数。
　　在超图的哈密顿圈问题部分，主要讨论了3-一致超图在3(|)m条件下的哈密顿圈分解的存在性，并通过构造重边的方式，改造条件，做出λ重3-一致超图的哈密顿圈分解的构造。然后，讨论了λ重r-一致超图G=λK(r)r×m，在r(|)mr-1，λ=r的条件下的哈密顿圈分解的存在性和构造问题。这一部分，主要用整环Zrm与超图顶点集相对应，然后通过差分模式和拓展的差分模式对相应序列进行研究的方法。

目录

声明

摘要

1．1 研究背景和意义

1．2 国内外研究现状

1．3 图的哈密顿圈问题及其研究结果

1．4 超图的哈密顿圈问题及其研究结果

1．5 本文的研究内容

第2章 夫妻沿直线桌入座问题

2．1 pn的计算

2．2 q1，n的计算

第3章 夫妻沿三条直线桌入座问题

第4章 超图的哈密顿圈问题

4．1 λK(3)3×m，3(|)m的哈密顿圈问题

4．2 λK(r)r×m，r是素数且r(|)mr-1的哈密顿圈问题

第5章 结论与展望

参考文献

攻读硕士期间发表的论文

致谢