导　　师： 杨元生

学科专业： H1202

授予学位： 硕士

作　　者： ;

机构地区： 大连理工大学

摘　　要： 对简单图g=(v，e)，f是g的点(或边)子集，如果由v\f(或e\f)导出的子图不含圈，则称f是g的反馈点(或边)集。记fv(g)(或fa(g))为所有反馈点(或边)集的最小的阶数，称为g的反馈点(或边)数。 确定图的最小反馈点集问题因其在诸多领域内具有广泛的应用而得到重视。例如，光纤网络中波长转换器的安装问题；网络传输过程中避免广播风暴问题；计算机操作系统避免死锁问题等都可以转化为确定图的最小反馈点集问题。 鉴于其理论和实际意义，本文通过计算机构造和数学推理证明相结合的方法，研究了广义kautz有向图gk(2，n)和交错群图agn的反馈数。 对于广义kautz有向图gk(2，n)，通过将其顶点集合v(gk(2，n))划分为六个子集，本文给出并证明了gk(2，n)的反馈数的上界为 对于交错群图agn，本文定义了其顶点集合v(ag，)的n-1个子集，然后证明了这些子集构成了agn的剩余无圈子集。在此基础上，本文证明了当n≥5时，agn的反馈数的上界为 A subset of vertices /(resp. arcs/) of a graph G =/(V,E/) is called a feedback vertex set of G if its removal results in an acyclic subgraph. Let f/_v/(G/) /(resp.f/_a/(G/)/) denote the minimum cardinality over all feedback vertices /(resp. arcs/) sets of the graph G. The minimum feedback vertex set problem has received intense research interest for its applications in various fields. For example, installation of wavelength translators into the fiber optic network; avoiding broadcasting storms in network transmission; avoiding deadlock in computer operating systems, etc. All of these problems could be abstracted and transformed into finding the minimum feedback vertex set of a given graph. For its theoretical and practical value, this paper explores the feedback number of generalized Kautz digraphs GK/(2,n/) and alternating group graphs AG/_n with the help of related feedback number algorithm. Regarding to the generalized Kautz digraphs GK/(2,n/), this paper divides V/(GK/(2,n/)/) into six subsets. Bases on the subdivision, this paper provides and proves a upper bound of the feedback number of GK/(2,n/), that is, Regarding to the alternating group graphs AG/_n,this paper defines n -1 subsets of V/(AG/_n/) and proves that the union of these subsets forms an acyclic subgraph on AG/_n.Thus, this paper gives and proves a upper bound of the feedback number of AG/_n for n≥5, that is,

关 键 词： 交错群图 网络传输 确定图 计算机构造 数学推理

分 类 号： [TP301.6 TP311]

领　　域： [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术]