完全多部图的广义连通度

摘要

连通度是图论的基本概念之一，它常被用来衡量一个通讯网络的性能。一个通讯网络可以自然地表示成图的形式，而连通度就是为使这个图不连通所需移除的元素(顶点或边)的最小数目，因此连通度越高也就意味着这个通讯网络的性能越好。连通度被众多的数学家进行研究。近年来，数学家们又提出了一些新的连通度概念，如彩虹连通度，广义连通度等，从不同的侧重点研究图的连通性质。这篇论文的主要结果就是关于广义连通度的一些进展。
　　 令G为一个具有n个顶点的非平凡连通图，k为一个整数，满足2≤k≤n。对G的一个足一元子集S，用K(S)表示G中边不交树T1，T2，…，Te的数目e，这些树要满足V(T1)∩V(Tj)=S，对每对不同的整数i，j，其中1≤i，j≤e(注意到这些树在G＼S中是顶点不交的)。G中满足这一性质的一族树{T，，T2，…，Te)称为连接S的内部不交树集。图G的k-连通度，记为Kk(G)，定义为Kk(G)=min{K(S))，其中最小是取遍V(G)的所有足k-元子集S。因此，K2(G)=K(G)，而Kn(G)是G的边不交生成树的数目。
　　 本文的第一章主要介绍一些记号和定义，以及相关的结果等。
　　 在第二章中，我们设计了一种方法--列表方法，利用这利，方法我们可以方便而快捷的找到任意完全二部图的所有边不交生成树。我们还计算了完全二部图的所有广义k-连通度并得到下面的结果：令a，b为满足a≤b的任意两个正整数，如果k>b-a+2，且a-b+k是奇数，那么
　　 Kk(Ka，b)=a+b-k+1/2+[(a-b+k-1)(b-a+k-1)/(4(k-1)]；如果k>b-a+2，且a-b+k是偶数，那么
　　 Kk(Ka，b)=a+b-k/2+[(a-b+k)(b-a+k)/(4(k-1)]；如果k≤b-a+2，那么
　　 Kk(Ka，b)=a
　　 在第三章中，我们将列表方法进一步用于完全三部图，可以找到任意完全三部图的所有边不交生成树。应用数学分析和近似算法等中的一些技巧，我们计算出了等部完全三部图的所有广义k-连通度。对满足b≥2且3≤k≤3b的任意两个整数b，k，等部完全三部图K3b的k-连通度为：
　　 在第四章中，我们用图的分解以及匹配的一些方法，找到了完全多部图G的所有[m(G)/n(G)-1]棵边不交生成树，其中m(G)表示G的边数，n(G)表示G的顶点数。我们还根据完全二部图和等部完全三部图的广义k-连通度的结果，提出了关于完全多部图的广义k-连通度的一些猜想。