de Bruijn图与Kautz图的κ元控制数和特殊圈

作     者：徐建勇 

作者单位：山西大学 

学位级别：硕士

导师姓名：王世英

授予年度：2011年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：de Bruijn图 Kautz图 线图 k元控制数 σ自逆圈 

摘      要：当前VLSI技术的进步,使得建造具有数千甚至数万个处理器的超大型并行分布式系统已经可以实现了.而在这些并行分布式系统中,最重要的一个步骤就是决定各个处理器之间连接的拓扑结构,即互联网络（简称网络）.这是因为网络的拓扑性质直接影响到并行分布式系统的硬件和软件两个层面的各种设计.de Bruijn图与Kautz图是应用比较广泛的两类互联网络. 出于多方面的考虑,人们期望通过一定数量的处理器来控制整个网络系统.对于无向图上控制问题的研究是近年来的一个研究热点.在一个无向图G中,称一个点控制它本身及其相邻的所有点.对于正整数κ≥1,图G的一个κ元控制集D是顶点集V（G）的一个子集,使得G中的每一个顶点被D中至少κ个点控制.图G的最小κ元控制集的基数称为κ元控制数,记为γκ（G）. 在并行处理系统中,由于圈的结构可被用于模拟网络的稳定性,所以在图中我们经常选择圈来作为考察对象.一个有向圈C的逆,记作C,是指一个满足V（C）=V（C）且A（C）={（v,w）|（w,v）∈A（C）}的圈.若存在一个同构映射σ,使得σ（C）=C,则称C是自逆的或σ自逆的. 在本文中,我们主要研究de Bruijn图与Kautz图的κ元控制数和特殊自逆圈问题.本文分为四章. 在第一章,我们介绍了一些本文将要用到的有关图论方面的基本概念. 在第二章,我们研究了无向de Bruijn图（记为UB（d,n））与无向Kautz图（记为UK（d,n））的κ元控制问题,主要结果如下： （1）当d≥2,2d-1≥κ≥2时, （2）当d≥2,2d≥κ1时, 在第三章,我们研究了在有向de Bruijn图（记为B（d,n））中,当d为偶数时的特殊圈问题,主要结果如下： （1）设n2为偶数,那么在B（d,n）中不存在自逆的Hamilton圈. （2）设n≥2,在B（d,n）中至少存在2/d个长度为2n的σ自逆圈. （3）当n为奇数时,在B（d,n）中存在长度至少为4的σ自逆圈当且仅当在B（d,n）中存在一条不包含交错弧和σ不动点的路P=v1v2…vk,使得（σ（v1），v1）与（vk,σ（vk））是交错弧,其中k≤（dn）/2. （4）当n为偶数时,在B（d,n）中存在长度至少为4的σ自逆圈当且仅当在B（d,n）中存在一条不包含交错弧的路P=v1v2…vk,并且路P上存在2个不动点v1与vκ,其中k≤（（dn）/2+1）. （5）当n为奇数时,在B（d,n）中至少存在2/d个长为2n的σ自逆圈. （6）在B（d,n）中至少存在2/d个长为4的σ自逆圈. （7）若C是B（d,n）中的σ自逆圈,那么L（C）是B（d,n+1）中的σ自逆圈. 在第四章,我们研究了在有向Kautz图中（记为K（d,n））,当d为奇数时的特殊圈问题.主要结果如下： （1）对于d≥3,并且n≥2为偶数,那么在K（d,n）中不存在σ自逆的Hamilton圈. （2）当n为奇数时,在K（d,n）中存在长度至少为4的σ自逆圈当且仅当在K（d,n）中存在一条不包含交错弧和σ不动点的路P=v1v2…vk,使得（σ（v1）,v1）与（vk,σ（vk））是交错弧,其中k≤（dn+d（n-1））/2 （3）当n为偶数时,在K（d,n）中存在长度至少为4的σ自逆圈当且仅当在K（d,n）中存在一条不包含交错弧的路P=v1v2…vk,并且路P上存在2个不动点v1与vκ,其中k≤（dn+d（n-1））/2+1. （4）若C是K（d,n）中的σ自逆圈,那么L（C）是K（d,n+1）中的σ自逆圈.