广义De Bruijn图GB(d,n)的反馈数

Feedback Number of Generalized De Bruijn Digraphs GB (d, n)

作者: 专业:计算机应用技术 导师:杨元生 年度:2010 学位:硕士  院校: 大连理工大学

Keywords

Feedback Vertex Set, Feedback Number, Generalized De Bruijn Digraphs, Cycles, Acyclic Subgraph

        图G的反馈数f(G)是使得G不含圈所需要移去的最小顶点数目。图的反馈数问题在很多领域中同样具有重要的应用价值,比如:在操作系统中资源分配策略以避免死锁的问题;人工智能中的受限满足和贝叶斯推论问题;同步分布式系统中的独占学习问题等都可以转化为图的反馈数问题来研究。但是求解一般图的反馈数已经被证明是NP-hard问题,目前只能得到一些近似算法,并且只有有限几种特殊图得到了反馈数的上界或下界。广义de Bruijn网络GB(d, n)是由经典的de Bruijn网络发展出的一种网络结构,它在继承了de Bruijn网络诸如小直径,高连通性及其简单路由等优点的同时,克服了deBruijn网络的结点数目限制,将de Bruijn网络扩充到任意结点。这使得广义de Bruijn网络GB(d, n)成为一种非常适合计算机网络的拓扑结构。所以研究广义de Bruijn网络的反馈数具有重要意义。本文针对广义de Bruijn网络GB(d,n),设计了一种采用计算机算法中分支限界、回溯思想与并查集结构结合的算法来构造GB(d,n)的反馈点集并寻找规律,将计算机构造结果与数学推理证明相结合,确定了广义de Bruijn网络GB(d, n)的反馈数f(d,n)的上界为:
    The feedback number f(G) of graph G is the minimum number of vertices to be removed, which makes the graph acyclic. The feedback number problem has important application to several fields. For example, the problems are used in resource allocation mechanisms that prevent deadlocks in operating systems, in the constraint satisfaction problem andBayesian inference in artificial intelligence, in the study of monopolies in synchronous distributed systems and in converters placement problem in optical networks. Howerve, The feedback number problem is known to be NP-hard for general graphs and got only some approximation algorithm. Determining the feedback number is quite difficult even for some elementary graphs. And the problem has been studied for only few special graphs and digraphs.Generalized de Bruijn network GB(d, n) is a kind of generalization to classic de Bruijn network. Generalized de Bruijn network inherits the good properties of de Bruijn network such as small diameter, high connectivity, and easy routing, and overcomes the restriction on the number of vertices, which expands de Bruijn network to the arbitrary vertex numbers. These properties make generalized de Bruijn network be noticed as a kind of topology structure of network. So, the study of the feedback number of GB(d, n) is very important.In this paper, we design an algorithm with branch and bound, backtr acking and union-find set for structuring the feedback vertex sets of generalized de Bruijn network GB(d, n). Through finding the law of different feedback vertex sets of different d and n, and mathematical proof, we obtain the upper bound of f(d, n) as follows:
        

广义De Bruijn图GB(d,n)的反馈数

摘要4-5
Abstract5
引言7-8
1 基本概念8-14
    1.1 图的基本概念8-9
        1.1.1 图和简单图8-9
        1.1.2 补图和独立集9
        1.1.3 环9
        1.1.4 子图和导出子图9
        1.1.5 顶点度9
    1.2 几种著名的组合网络9-11
        1.2.1 超立方体网络9-10
        1.2.2 双环网络10
        1.2.3 蝶形网络10-11
    1.3 反馈数问题及研究现状11-13
        1.3.1 反馈数的概念11-12
        1.3.2 反馈数问题的研究现状12-13
    1.4 本文的主要工作13-14
2 广义De Bruijn图GB(d,n)的反馈数14-57
    2.1 广义De Bruijn图GB(d,n)的定义和性质14-16
        2.1.1 广义De Bruijn图GB(d,n)的定义14-15
        2.1.2 广义De Bruijn图GB(d,n)的性质15-16
    2.2 广义De Bruijn图GB(2,n)的反馈数16-22
    2.3 广义De Bruijn图GB(3,n)的反馈数22-51
    2.4 广义De Bruijn图GB(d,n)的反馈数51-57
结论57-59
参考文献59-61
攻读硕士学位期间发表学术论文情况61-62
致谢62-64
        下载全文需10


本文地址:

上一篇:基于贝叶斯网络的入侵检测
下一篇:基于虚拟现实技术的心脏建模方法研究

分享到: 分享广义De Bruijn图GB(d,n)的反馈数到腾讯微博           收藏
评论排行
公告