论文部分内容阅读
图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图.为了研究拟阵中圈图的性质,我们提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中圈的性质,路的性质,并且把圈图的概念推广为n阶圈图,并得到了n阶圈图的一些性质。
设E是一个有限集.如果S1,S2()E,那么S1-S2={x|x∈S1和x()S2}.
一个拟阵M就是一个有限集E以及E的一个非空子集族(),且满足以下条件:
(C1)若C1,C2∈()且C1()C2,则C1=C2.
(C2)设C1,C2∈()并且a,b∈E.若a∈C1∩ C2且b∈C1-C2,则存在C3∈()满足b∈C3()(C1∪ C2)-{a}.
当C∈()(M),我们称C为M的一个圈.如果M的一个圈只有一个元素,则称之为M的一个环.如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元.如果M既没有环也没有平行元,则称M是一个简单拟阵.如果一个元素含在M的任一基中,则称之为M的一个反环.
如果S是E的一个子集,且对任意的圈C,都有C()S或者C()E\S.则称S为M的一个分离集.显然E和()都是M的分离集.M的极小分离集称为M一个分支.如果拟阵M只有一个分支,则称M为连通拟阵.设e∈E,则M.e和M△e分别表示由拟阵M经过收缩和删除e后所得到的拟阵.
拟阵M=(E,())的基图是这样一个图G,其中V(G)=(),E(G)={B1B2:B1,B2∈(),且|B1B2|=1},这里图G的顶点和M的基用同样的符号表示.
设G是一个图,图G的点集和边集分别记为V(G)和E(G),令V(G)=|V(G)|.包含G的每个点的路称为G一条哈密顿路;同样地,包含G的每个点的圈称为G一个哈密顿圈.如果个图存在一个哈密顿圈,则称之为哈密顿的.如果对一个图G的任意两个顶点来说,G都有一条哈密顿路连接它们.则称G是哈密顿连通的.如果对一个图G的任意一条边来说,G都有一个含这条边的哈密顿圈,则称G是边哈密顿的,或者称G是正哈密顿的,记为G∈H+.如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密顿圈,则称G是负哈密顿的,记为G∈H-.如果G既是正哈密顿的,又是负哈密顿的,我们称G是一致哈密顿的。
一个有n个顶点的图G称为顶点泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一个顶点,G都存在一个过该顶点的长度为k的圈.一个有n个顶点的图G称为边泛圈的,当且仅当对任意的k,3≤k≤n,以及G的任意一条边,G都存在一个长度为七的圈包含这条边.
现在我们给出拟阵圈图的概念.定义拟阵M的圈图G=G(M的顶点集V(G)=(),边集E(G)={CC| C,C∈(),|C∩ C|≠0}。这里C和C既代表G的顶点,也代表M的圈.
定义拟阵M的k阶圈图Ck(M)的顶点集为V(Ck(M))=()(M).两个顶点C,C∈()(M)在Ck(M)中相邻当且仅当在M中|C∩ C|≥k.为了符号表示方便,我们既用C表示Ck(M)的顶点,也用C表示M中的圈.
本文分为五章.第一章给出关于树图,拟阵基图以及森林图的一个简短但相对完整的综述.第二章给出拟阵圈图的概念,并讨论拟阵圈图的连通度和边连通度.第三章我们深入讨论了拟阵圈图的哈密顿性,边泛圈性以及圈图中顶点不交圈的性质.第四章讨论了拟阵圈图中路的性质.第五章我们给出了拟阵的圈图的定义,并讨论了它的直径和连通度.
下面列出本文的主要结果.
结论1设G=G(M)是一个连通拟阵M的圈图,而且B是M的一个基,则G的连通度K(G)≥2|E-B|-2.
结论2设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则δ(G)≥2|E-B|-2.
结论3设G=G(M)是一个连通拟阵M的圈图,而且G的最小度是δ(G),则G的边连通度k(G)=δ(G).
结论4设G=G(M)是一个连通拟阵M的圈图,而且M含有至少三个圈,则G=G(M)是边泛圈的.
结论5设G=G(M)是一个连通拟阵M的圈图,而且M含有至少四个圈,则G是一致哈密顿的.
结论6设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且k1+k2+…+kp=n(ki为整数,ki≥3,i=1,2,…,p),则G有一个2-因子F包含p个顶点不交的圈D1,D2,…,Dp而且圈Di的长度为ki(i=1,2,…,p).
结论7设G=G(M)是一个连通拟阵M的圈图,而且M含有至少三个圈,则G的直径不超过2.并且,d=(G(M))=2当且仅当M中有两个没有公共元素的圈.
结论8设G=G(M)是一个连通拟阵M的圈图,如果|V(G)|=n并且C1,C2∈V(G),则对于任意的k满足2≤k≤n-1,存在一条长度为k的路连接C1和C2.
结论9设M是一个连通简单拟阵.则如下结论成立.(ⅰ)C2(M)是连通的.(ⅱ)如果M没有一个约束子拟阵同构于U2,6,则在C2(M)中任何两个不相邻的顶点C1和C2有一个公共邻点G.(ⅲ)C2(M)的直径不超过2当且仅当对于任何边集合X()E,M在X上的约束子拟阵都不同构于U2,6.
结论10设M是一个包含至少两个圈的连通简单拟阵,且M不是一条线,则C2(M)是2-连通的.