论文部分内容阅读
图论是组合数学的一个分支,在各个领域有着广泛的应用,受到了数学界和其他科学界的重视. 本文主要考虑了两个问题:标准多重二部图中点不交的4圈的存在性度条件;标准多重图中点不交的重边四边形。本文所指的有向图为无环无重边的简单有限有向图。不含环和重边的无向有限图称为简单图,顶点集非空且任意两个顶点之间的边数有限的图称为多重图,任意两个顶点之间边数至多为2的多重图称为标准多重图,长为4的圈称为4圈或者四边形,圈上的四条边都为重边的四边形称为重边四边形. 本文分为四个部分.第一部分介绍了图的基本概念以及所研究问题的历史背景和发展情况.第二部分研究了对于标准多重二部图M=(X,Y;E),满足|X|=|Y|=2k,k为正整数.如果M中每个点的度数至少为3k+1,则M一定包含k个点不交的4圈,使得其中k-1个为重边四边形,剩余一个四边形至少有三条重边.作为推论,我们给出了简单二部图和简单有向二部图中点不交的存在性度条件.第三部分主要研究了对于阶数为4k,最小度为6k-2的标准多重图,k为正整数,除三个特例外,M包含k-1个重边四边形和一个有三条重边的四边形,使得这k个四边形彼此点不交.最后提出了一些问题,以待进一步讨论和研究.