论文部分内容阅读
图论和拟阵理论在二十世纪经历了空前的发展。图的支撑树及拟阵的基都是组合理论的基本研究对象。一个连通图的树图能够反映该图的不同支撑树之间的变换关系。因此,研究一个图的树图有助于我们更好地了解该图的性质。同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系。因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质。近些年来,树图和拟阵的基图被推广得到了一些新的图。我们主要研究拟阵基图,拟阵的基关联图,邻接叶边交换森林图以及图的分数荫度等。 一个拟阵M就是一个有限集E以及E的一个非空子集族β,且满足以下条件:对任意的B1,B2∈β及任一元素e1∈B1B2,存在一个元素e2∈B2B1,使得(B1e1)∪e2∈B,记为M=(E,β)。β中的每一个元素称为M的一个基。M的一个基的任何子集都称为M的一个独立集。如果C(?)E不是一个独立集,并且任何子集X(?)C都是一个独立集,则称C为M的一个圈。如果M的一个圈只有一个元素,则称之为M的一个环。如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元。如果M既没有环也没有平行元,则称M是一个简单拟阵。如果一个元素含在M的任一基中,则称之为M的一个反圈。 如果S是E的一个子集,且对任意的圈C,都有C(?)S或者C(?)ES。则称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一条Hamilton路;同样地,包含G的每个点的圈称为G一个Hamilton圈。如果(?)图存在一个Hamilton圈,则称之为Hamilton的。如果对一个图G的任意两个顶点来说,G都有一条Hamilton路连接它们。则称G是Hamilton连通的。如果对一个图G的任意一条边来说,G都有一个含