论文部分内容阅读
连通性是图的最基本的性质之一,是图论中重要的研究课题。在实际应用中,连通图起着重要作用,它与网络模型和组合优化密切联系。讨论连通图的结构特征一直是图论研究的前沿课题之一。在各类连通图中,为了使任意连通图都可以由一些简单的连通图重复某些运算得到,最常用的方法就是引入一些保持图的连通性的运算。连通图中可收缩边是研究连通图的结构,递归,证明图的某些性质的重要工具,对它们的研究具有重要的应用价值和理论价值。 令G=(V(G),E(G))是一个连通图,V是V(G)的一个子集.G的顶点割是指使G- V7不连通的顶点集.若IVI=K,则称V为G的一个K顶点割.G所具有的K顶点割中最小的K称为G的连通度,记为K(G).否则定义K(G)为V(G)-1.若K(G)≧K,则称G为k连通的。设e为G中的一条边,在G中删去e并把它的两个端点重合后得到的图记为G/e,此时称e为被收缩。令G是一个K连通图,e为G中一条边。如果将e收缩后所得到的的图仍是K连通图,那么称这条边e为G的可收缩边。2003年,吴吉昌和李学良给出了4连通图中可收缩边和可去边的分布情况.近年来,5连通图和6连通图中可收缩边的分布情况也得出一些结论。本文把这些结果推广到7连通图中的情况。本文主要讨论了7连通图中可收缩边在最长圈和完美匹配上的分布情况。 本文包括四章: 第一章是绪论,主要介绍了图论的历史研究和发展现状。 第二章是预备知识,介绍了一些本文中将要用到的图论方面的基本概念和术语。 第三章给出了在7连通图中可收缩边在最长圈上的分布,结论如下: (i)设G是一个7连通图,X,Y是G中的任意两点,令P=(X=)XIX2- XT(=Y)是G中一条最长(X,Y)路。若对于G中任意一个7顶点割S,在G-S中都有G的端片,则E(P)中至少存在一条可收缩边。 (ii)设G是一个7连通图,C是G中的一个最长圈。若对于G中任意一个7顶点割S,在 G-S中都有G的端片,则在C上至少存在两条G中的可收缩边.连通图中可收缩边的分布。 第四章讨论了7连通图中可收缩边在完美匹配上的分布情况.结论如下: (i)设G是一个7连通图,M是G的一个完美匹配。若对于G中的任意一个7顶点割S,在G-S中都有G的端片且M的任意一条边均不在长为3<5的圈上,则M上至少有一条G中的可收缩边。 (ii)设G是围长G(G)>5的7连通图,M是G的一个完美匹配。若对于G中的任意一个7顶点割S,在G-S中都有G的端片,则M上至少有两条G中的可收缩边。