拟阵圈图的一些性质

来源 :山东大学 | 被引量 : 3次 | 上传用户:ziwen74
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不同支撑树之间的变换关系.因此,研究一个图的树图有助于我们更好地了解该图的性质.同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系.因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质.近些年来,树图和拟阵的基图被推广得到了一些新的图.为了研究拟阵中圈图的性质,我们提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中圈的性质,路的性质,并且把圈图的概念推广为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-连通的.
其他文献
R.Nevanlinna创立的值分布理论(也称Nevanlinna理论),以两个基本定理和亏量关系式为核心内容,被著名数学家WeyL评价为20世纪最优美的数学分支之一,而关于亚纯函数的唯一性理论是Ne
学位
动力系统总是存在滞后现象。从工程技术、物理、力学、控制论、化学反应、生物医学等中提出的数学模型带有明显的滞后量。特别是在自动控制的装置中,任何一个含有反馈的系统,从
数字签名中的公平交换问题是密码学的一个基本的问题,在电子商务中有着广泛的应用。随着网络的广泛普及与使用,通过网络处理的交易也在不断增加,公平交换问题就显得更为重要
非线性不确定系统是在实际生产中经常遇到的控制系统,解决此类系统的控制问题具有很高的现实需求和理论意义。滑模变结构控制以其良好的鲁棒性,在解决控制问题中表现出强大的