林秋英[1]2002年在《无向循环图与广义de Bruijn有向图的支撑树与欧拉环游的计数》文中研究表明本文首先讨论度数为奇数的无向循环图的支撑树计数问题，给出其解析表达式及渐近结果，并给出一有效方法来计算支撑树数目。接着，本文还讨论了广义de Bruijn有向图的情况，特别给出一类特殊的广义de Bruijn有向图的支撑树与欧拉环游数目的简洁表达式。由于迭线图的支撑树数目与原图的支撑树数目有密切关系，所以这两类图的迭线图的支撑树数目也相应可以得到。
林秋英[2]2002年在《广义de Bruijn有向图及其迭线图的支撑树与欧拉环游的计数》文中研究说明给出了一类特殊的广义 de Bruijn有向图的支撑树与欧拉环游的数目的简洁表示式 .并得到广义 de Bruijn有向迭线图的支撑树与欧拉环游数目的计算公式 .
黄佳[3]2007年在《图的控制稳定性研究》文中指出图论是一门新兴的学科，但由于它在很多领域都有着广泛应用，图论近几十年来发展十分迅速。其中，控制理论经过了叁十年的发展，已经成为了图论研究中的一个重要领域，究其原因，也是因为控制不仅在理论上，还在实际问题中有着重要的应用，正是由于这方面的研究和实际应用之间有着紧密的联系，在本文中我们将研究图在边改变下的控制稳定性，即考虑图中边的改变对控制有何影响。之所以采用这种动态的视角，是因为图作为很多现实问题的模型，时常要做一些改变，才能适应现实的变化；于是，我们必须关注图的变化对一些参数和性质有何影响，具体到本文，我们主要研究叁个参数——约束数，加强数和控制收缩数，它们分别反映了图在叁种基本的边改变：删去，增加和收缩下的控制稳定性。对于约束数b(G)，我们首先对交叉数较小的图得到了一系列结果，它们包含了前人得到的平面图约束数的若干上界。在这些结果种最重要的两个是b(G)≤min{8，Δ(G)+2}在cr(G)≤3时成立，和然后我们考虑de Bruijn图B(d，n)和Kautz图K(d，n)。这两类图作为互连网络的拓扑结构，有很多好的性质，因此已经超越经典的超立方体网络成为下一代并行系统体系结构的首选。我们证明了de Bruijn图和Kautz图的约束数是我们还确定了这两类图的全约束数(约束数的变形，对应于全控制数)：b_t(B(d，n))=d-1，d≥2，且b_t(K(d，n))=d，d≥1。最后我们证明了k正则的点可迁图G如果拥有有效控制集则应用这一结果我们得到了一些常见网络的约束数，包括双环网，圆环和立方连通圈。对于加强数γ(G)，我们对有向图给出了定义，并且得到了很多和无向图情形类似的结果。我们还研究了无向图和有向图的加强数之间的关系，然后我们考虑在一篇加强数的综述文章中提出的两个问题：我们部分地刻画了一个已知上界中取等号的情形，并且对k正则图G给出了新的r(G)的上下界：其中γ=γ(G)≥2，e=γ(k+1)-n(G)。最后我们确定了de Bruijn图和Kautz图的加强数：受到近年来关于(全)控制细分数的研究的启发，我们提出了(全)控制收缩数的概念，并给出了它的实际意义。我们证明了对所有的图这个参数的取值只能是0，1，2或3，并且刻画了分别取这些值的四个图类。最后，我们总结了上面这些工作，并给出了关于平面图约束数的若干猜想的一些不成熟结果，还提出了很多有待进一步深入研究的问题。
顾磊[4]2011年在《社会网络：拓扑性质与代数性质》文中研究说明现代对于社会网络及其关联的小世界模型的研究很多都是在模拟和数值试验中完成,其中两个重要的拓扑性质就是小世界性和强聚集性,般指的就是平均距离或者直径远小于顶点数量而图中叁角形的数量又接近于正则格。Watts和Strogatz提出了将正则格的一部分边随机以概率p移走到其他顶点的模型(WS模型)并通过数值模拟发现存在一个概率区间使得移边概率p在该区间内具有强聚集性和小世界性。Watts和Strogatz猜测存在一簇介于有序和无序(随机)的图使其聚集性能很强而平均距离或者直径接近于随机图,并称之为小世界网络。同时期Newman和Watts提出了用正则格和随机图的并去掉自环和重边后构成的模型(NW模型),这个模型的聚集系数相当容易估计。Newman、Moore和Watts利用连续型模型近似和中值场近似(以及独立的Barbour和Reinert利用连续模型)给出了平均距离的估计。我们提出了广义小世界模型并利用等周常数结合最大度得到该模型直径的上界,再利用组合计数估计叁角形数量得到聚集系数的下界。从而证明了广义小世界模型为一簇满足强聚集性和小世界性的小世界网络。社会网络及小世界模型上的代数性质是指的将图看作一个矩阵并通过研究矩阵的谱来研究网络的性质。这里网络的代数结构,尤其是Lapla-cian矩阵的第二小特征值(也称代数连通度)和最大特征值和网络上的动力系统有很强的关联,特别在多智能体系统的一致性问题和耦合系统的同步问题中有广泛的应用。Olfati-Saber利用计算机模拟发现WS模型的代数连通度与正则格比较有很大的提高,这个性质对于提高多智能体系统达成一致性的速度非常重要。我们给出了NW模型代数连通度的严格估计以及与正则格比较的代数连通度获取量的下界。代数连通度决定了小世界网络上多智能体系统达成一致性的速度,因此我们的结果可以用于设计成本低廉连接较少而一致性很快的多智能体系统。此外我们还分析了小世界网络上多智能体系统对时滞的鲁棒性能以及给出了一簇可同步的小世界网络。社团性质指的是局部连接紧密而与外界连接稀疏的拓扑性质,它是社会网络的局部拓扑性质中很重要的一部分。对于社团性质的研究着重于找到现实网络中的这些社团,也就是社团划分,目前给定网络有许多社团划分的算法,但是仍然缺少一个通用有效并且确定划分数量的快速算法。在本篇论文中,我们提出了利用一个或者多个Laplacian矩阵特征向量的分量投影到一维或者多维欧式空间后,使用原点或者坐标轴进行切割,再考虑每个子块的连通分支的快速算法,在文章中称为弱Nodal域划分方法(WNDP),我们还提出了叁个对不同特征向量划分后比较的标准从而决定网络具体划分块数。
张永红[5]2009年在《基于分布式De Brujin图的P2P覆盖网设计与分析》文中研究说明对等网络(Peer-to-Peer Networks,简称P2P网络)是采用对等模式工作的计算机网络,是分布式系统与计算机网络相结合的产物。目前,P2P网络已经被广泛应用于Internet环境下的文件共享中。在P2P网络中的每个结点在功能上是平等的,在行为上是自由的,在连接上是互联的,打破了传统的客户/服务器模式,让一切网络结点享有平等、自由、互联的功能,不再有客户、服务器之分,任何两个网络结点之间都能共享文件、传递信息。因此,它能够极大程度地提高网络效率、充分利用网络带宽、开发了每个网络结点的潜力,具有非常高的扩展性和容错性。这使得P2P技术迅速发展成为计算机网络的一项重要技术,在应用领域和学术界获得了广泛的重视。由于它占据了当前Internet超过一半的带宽资源,被认为是“改变Internet的新一代网络技术”。P2P网络高效的一个重要原因是它在网络应用层上构建了一个有严格拓扑结构的覆盖网络。从设计思想和体系结构来看,P2P覆盖网络的研究可分为结构化和非结构化两种,它们有各自的优缺点。本论文的研究是基于结构化P2P覆盖网络,结构化P2P覆盖网络是基于分布式哈希表(DHT)来准确、快速地路由信息和定位数据对象。针对结构化P2P网络拓扑的研究发现,构造的P2P系统性能在很大程度上与该P2P系统底层所依据的静态图的性质有关,因此在学术界对于结构化P2P网络的研究,可根据底层所依据的静态图形不同,分为常数度DHT和非常数度DHT。近年来,对于常数度DHT的研究已经引起了学术界的高度重视,尤其是对于平均路由长度与路由表规模的折衷方面的研究。常数度DHT通常是基于一定的常数度静态图来构造的,例如:CAN是基于d-维环面的;Viceroy是基于蝶形图;D2B和Koorde都是依赖于De Brujin有向图的;FissonE和Moore都是建立在静态Kautz图上的。这些基于常数度静态图构造的P2P系统,其性能不仅在某些方面优于非常数度P2P系统,而且在很大程度上与其所依赖的静态图的性质有关,因此从图论的角度来研究P2P系统成为一种行之有效的方法。本论文首先从图论的角度入手研究P2P系统,提出了另一种常数度结构化的P2P覆盖网络协议,它是基于De Brujin有向图的。此系统首先对De Brujin有向图进行修改,然后把分布式线图技术应用于修改后的De Brujin有向图,而得到的一种新的P2P协议DDBG(Distributed De Brujin Graph)协议。该协议融合了De Brujin有向图和环的优点,使得结点的动态加入和离开过程更加方便,提高了网络的容错性和自由度,具有很高的可用性。其次从图论与系统拓扑相结合的角度,针对现有的结构化P2P系统和本论文构造的P2P系统,提出了一种基于图论的结构化P2P系统理论分析的通用框架,使图的性质与P2P系统的性能更加合理地联系在一起,为以后构造结构化P2P系统提供了有利的理论指导。本文共分为五章.第一章简要介绍了P2P网络、P2P网络的发展及现状,P2P网络的核心机制与增强机制,及论文的研究内容等。第二章研究了图论中基本概念,特别是线图技术与分布式线图技术,详细研究了De Brujin有向图及对De Brujin有向图的改进。第叁章构造了一种新的P2P覆盖网络协议DDBG-基于De Brujin图构造的分布式De BrujinP2P协议。第四章基于对所构造的网络协议DDBG的理论分析,提出了一种基于图论的结构化P2P系统理论分析的通用框架。第五章总结全文,并提出了下一步要解决的问题。
参考文献：
[1]. 无向循环图与广义de Bruijn有向图的支撑树与欧拉环游的计数[D]. 林秋英. 厦门大学. 2002
[2]. 广义de Bruijn有向图及其迭线图的支撑树与欧拉环游的计数[J]. 林秋英. 数学研究. 2002
[3]. 图的控制稳定性研究[D]. 黄佳. 中国科学技术大学. 2007
[4]. 社会网络：拓扑性质与代数性质[D]. 顾磊. 上海交通大学. 2011
[5]. 基于分布式De Brujin图的P2P覆盖网设计与分析[D]. 张永红. 曲阜师范大学. 2009