论文部分内容阅读
图的路和圈的研究是图论学科一个重要的、经久不衰的课题。经过很长一段时期探索,对于路和圈已得到了一些很好的结果。当前,对图的路和圈的研究主要是在一些特定领域展开。在这篇文章中,我们尝试着在简单图、有向图、染色图领域对图的路和圈的某些特性进行刻画,得出了一些令人满意的结果。 在第一章里,针对简单图中的路和圈,我们尝试从新的角度提出了一些关于路和圈的问题,并给予论证,使得简单图中路和圈的理论更加丰富。 在第二章里,文章对有向图中最短的有向圈以及C-H猜想进行了一些探索。首先,回顾了C-H猜想的发展进程。其次,针对C-H猜想讨论了可能存在反例的一些必要条件,虽然这些条件不能证明或拒绝这个猜想,但它们给出了这个猜想的一些特殊例子的论证。最后,文章还对强连通图中与C-H猜想相关的一些问题以及有向超图中的有向圈进行了初步探讨。 在第三章里,文章对染色图中的路和圈进行了较深入的研究,为了便于研究,文章从四个方面入手,[即:正常顶点染色、正常边染色、一般顶点染色、一般边染色],着重研究在每一种情形中路和圈的特性:一方面要考虑路和圈尽可能长,另一方面要兼顾路和圈中的不同染色要尽可能多。理想情况下,找到一条各项染色不同的最长路(或圈)。