用8长圈C最大填充和最小覆盖完全二部图K

摘要

本文主要考虑了下面两个问题. 1.用Km,n表示具有m+n个顶点，二部集的基数为m和n的完全二部图.D.Sotteau[1]解决了当m，n都是偶数，且m，n≥4时，完全二部图Km,n的C2k的分解问题.DanArchdeacon等[2]解决了当n是奇数，且k≤n时，Kn,m\I的C2k的分解问题，这里I为Kn,n的1-因子.Elizabeth.J等[3]解决了当m，n是任意数时，完全二部图Km,n的最大C4-填充问题.Lakeisha Brown等[4]解决了当m，n是任意数时，完全二部图Km,n的最大C6-填充问题.本文在上面的基础上，完全解决了当m,n是任意数时，完全二部图Km,n的最大C8-填充和最小C8-覆盖的问题.根据m和n的奇偶性，主要分了下面三种情况来构造的：(1)m，n都是偶数；(2)m，n一个是奇数一个是偶数；(3)m，n都足奇数.本部分主要使用的是直接构造的方法. 2.流量疏导是当今光网络研究中的一个前沿和热点问题，在波分复用(WDM)光网络中使用流量疏导技术能有效降低网络的成本，减少网络节点中业务信息的处理量.我们希望降低WDM光网络中ADM的总数.这个问题的解决依靠将完全图的边划分成一些子图，每个子图至多包含c条边(其中c是疏导率)，以减少所有子图顶点的总数.对于给定的疏导率c，利用图论和设计理论已经得到了最优的构造[5].特别地，对于c=1时，每个子图都是1条边，没有降低成本的可能.当c=2时，每个子图至多包含2条边，由于Kn线图是欧拉图，在每个欧拉圈上用连续的点可以降低成本，从而可使最低成本是[3n(n-1)/4][6].对于疏导率c=3[7]，c=4[8,9]，c=5[10]，c=6[6]，c≤n(n-1)/6[8]的环上的业务疏导问题，已经解决.本文在上面的基础上，研究了无向环WDM中疏导率c=8的业务疏导问题.当每对站点使用不超过波容量的1/8时，存在具有最小花费的分解已经在本文中得到部分的结果.事实上，当n≡0，1，2，3，4，5，6，7(mod 16)，除去一些未确定的n=34，35，36，37，38，39，在本文中已解决.本部分技巧主要依靠的工具是图论与组合设计理论.

目录

文摘

英文文摘

声明

1绪论

1.1研究背景

1.1.1圈填充和覆盖问题的研究背景

1.1.2业务疏导问题的研究背景

1.2本文的结构与主要结果

2 Km，n的最大C8-填充和最小C8-覆盖

2.1预备知识

2.2具体构造

3当疏导率c=8时，环上的业务疏导问题

3.1预备知识

3.2具体构造

4结论

参考文献

致谢