论文部分内容阅读
对简单图G=(V，E)，F是G的点(或边)子集，如果由VF(或EF)导出的子图不含圈，则称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的反馈数的上界为