（应用数学专业论文）互连网络的最小反馈点集.pdf

摘要 本文集中研究了三类互连网络中的反馈数问题第一章给出与本文有关 的一螳基本概念和结论，介绍目前学术界对这一问题研究进展和问题的困难 程度第二章从超立方体删络出发，在超立方体网络的递归定义中得出其结 构的特殊性：超立方体网络可以看出两个较低阶同类网络的复合利用这一 特性，可以推广己知的一些结论，把这些结论和方法应用的比超立方体网络 更复杂的折叠立方体网络巾，解决折叠立方体网络中的反馈数问题后两章 研究另外两类结构很相似的网络：d eb r u i j n 网络和k a u t z 网络在这两类 网络中，我们发现了几乎处处布满整个网络的最小圈圈中沿着有向边的方 向，各个顶点均可经最少的变换次数回归自身，我们称其为“最小轨道”借 助于最小轨道，可以得到网络中反馈数一个相当好的下界d eb r u i j n 网络 和k a u t z 网络都具有很强的自相似性，高维的网络包含着完整的较低阶的 网络利用此属性，我们可以对网络从整体到局部、从外围到中心，按统一 的法则进行处理，一直到阶数最低的平凡情况这是我们确定嘲络反馈数上 界的书要方法射于这i 类网络，本文都给出了反馈数的上下界并且给出 了使得反馈数上下界相等的条件和确定出了最小反馈点集的具体方法 4 2 0 0 5 年中国科学技术大学硕士学位论文 a b s t r a c t i nt h i sp a p e r t h r e ec l a s s e so fi n t e r c o n n e c t e dn e t w o r ka r ed i s c u s s e da b o u t t h ef e e d b a c kn u m b e r s o m eb a s i cc o n c e p t sa n dr e s u l t sa r ei n t r o d u c e di n t h ef i r s tc h a p t e r ，a n dt h er e s e a r c hd e v e l o p m e n ta n dt h ed i f f i c u l t yo ft h i si s s u e i nt h es e c o n dc h a p t e r ，b e g i nw i t ht h eh y p e r c u b en e t w o r k s ，w ef o c u so n oneo fi t se n h a n c e df o r m t h ef o l d e dh y p e r c u b en e t w o r k s b e n e f i t e d f r o mt h es p e c i a ls t r u c t u r eo ft h ed e f i n i t i o nu s i n gi t e r a t e dl i n eg r a p h so ft h e h y p e r c u b e s ，w eg e n e r a h z et h ep r o p e r t i e sk n o w nf r o mt h eh y p e r c u b e st o t h ef o l d e dh y p e r c u b en e t w o r k sw h i c ha r em o r ec o m p l e x s o ，w ef i n dt h e l o w e rb o u n da n dt h eu p p e rb o u n do ft h ef o l d e dh y p e r c u b en e t w o r k s d eb r u i j nn e t w o r ka n dk a u t zn e t w o r ka r es t u d i e di nt h ef o l l o w i n gt w o c h a p t e r s ，w h i c ha r em u c hs i m i l a re a c ho t h e r i nt h e s et w oi n t e r c o n n e c t e d n e t w o r k s ，w ef i n ds o m em i n i m u mc y c l e sm e r e l y s p r e a da l lo v e rt h ew h o l e n e t w o r k s a l o n gt h ed i r e c t i o no ft h ec y c l e ，e v e r yv e r t i c ec a nr e t u r nt oi t s e l f t h r o u g ht h es m a l l e s tt i m e so fs h i f t w ec a l lt h e s ec y c l e st h em i n i m u mo r b i t s ap r e t t yg o o dl o w e rb o u n do ft h ef e e d b a c kn u m b e rcanb eo b t a i n e d f r o u lt h i s n o to n l yd eb r u i j nn e t w o r k s ，b u tk a u t zn e t w o r k sa r es t r o n g l ys i m i l a r t oi t s e l f an e t w o r kh a sg r e a t e rd i m e n s i o ni n c l u d e sa n yn e t w o r kw h i c hh a s s m a l l e rd i m e n s i o nt h i sm e a n st h a tw ec a nd e a lw i t ht h en e t w o r kf r o mt h e w h o l et op a r t ，f r o mt h eo u t s i d et oi n s i d eb yu s i n gt h es a m em e t h o dt ot h e u l t i m a t eo r d i n a r yc a s ev e r yl o wd i m e n s i o n t h i si sh o ww ec a l lg e tt h eu p p e r b o u n do ft h ef e e d b a c kn u m b e ro ft h e s et w on e t w o r k s t h ec o n d i t i o nu n d e r w h i c ht h eu p p e rb o u n dr e a c h e st ot h el o w e ra n dt h em e t h o dh o wt od e c i d e t h et h em i n i m u mf e e d b a c kv e r t e xs e t sa r ep r o v i d e di n a l lt h e s et h r e e c l a s s e so fn e t w o r k s 第一章基本概念和预备知识 1 1 与本文有关的概念 定义1 1 1 称数学结构d = f y p ) ，e ) ，掣，d 为一个图，其中v ( d ) 是非 空集合，妒d 足从集合e ( d ) 到v ( d ) v ( d ) 的一个映射，则称d 是一 个以v ( d ) 为顶点集合，以e ( d ) 为边集合的有向图v ( d ) 中的元素称为 图d 的顶点，e ( d ) 的元素称为图d 的边，砂d 称为关联函数若妒d ( e ) = ( u ，u ) ，e e ( d ) ，( “， ) v ( d ) v ( d ) ，则简写成e = “ ；称u 是有向 边e 的起点，v 是有向边e 的终点，若i v ( d ) i + o 。， e ( d ) i 2 ，c 的取值范围均为( 警 2 时也成立，此时c 的取值是1 对 1 、 1 ， 2 4 无圈导出子图连通性分析 因为折叠立方体网络比超立方体网络多出2 虹1 条边，所以确定反馈数 相应就更困难些但这里得到的结果不仅有简洁的表达式，在某些情况下， 我们的得到的无圈导出子网络具有更好的整体连通性 命题2 4 1 如果k 为奇数，则如上述方法构造的f q k + - 的无圈导出子图的 连通分支个数比风中连通分支个数少1 证明 因为f q 女+ 1 中互补点间奇偶不变，e 的对偶点是一偶点，e 的互补点是 一奇点如定理2 3 2 的证明知，e 的对偶点和互补点必不在同一连通分支卜 兄1q j 尚有2 一_ 一各 个奇点要求与站中 2 一1 1 的个奇点互补对应 又因为k 2 ，所以2 一1 2 一f 筹1 即：r 1 中的每一个孤立的奇 2 0 0 5 年中国科学技术大学硕士学位论文1 9 点，都一j 以通过互补边与凰中原来保留的点相连所以这2 一尝； 个 点的加入，并不会使凰中连通分支个数增加且e 把原不连通的两个分支连 成了一个分支( 当k = 3 时如f i g2 3 1 中d 所示) ，于是总的连通分支减少 了1 个 证毕 容易验证当七= 3 ，4 时，由定理2 3 1 和定理2 3 2 给出的f ( k ) 的下界和 上界相等，即f ( 3 ) = 3 和f ( 4 ) = 7 此时我们的界是很好的由我们构造 所得的导出子图仅有一个连通分支，女f l f i g2 31 中b ，d 所示 第三章d eb r u i j n n 络中的反馈数 3 1 d eb r u i j n 网络 d eb r u i j n 网络是n g d eb r u i j n 和i j g o o d 于1 9 4 6 年提出来的d e b r u i j n 网络仅次于超立方体网络频频出现在科技文献中，它具有许多与超立 方体网络一样的好性质，还有一些优于超立方体网络的性质，并被认为是对 超立方体恻络的挑战而替代下一代的并行计算机互连网络基于d eb r u i j n 网络的大规模超级计算机互连网络已经开始进入实施阶段 我们以d 元集上的有序k 元数组( d a r yk t u p l e s ) 给出d eb r u i j n 网络的定义 定义3 1 1 给定整数d 2 ，k 2 ，d eb r u i j n 有向图记为b ( d ，) ，其 顶点集y ( b ( d ，) ) = z l z 2x k ：2 2 。 o ，1 ，d 1 ) ) ；b ( d ，k ) 中以 顶点。1 。2 。为起点的d 条有向边的终点为x 2 2 3，其r r id f 0 ，1 d 1 1 也a j _ 以用线图的构造方法给出一个等价的定义 定义3 1 2 对于固定的正整数d ，用g j 表示在d 阶完全有向图的每个顶 点上添加一个环后得到的有向图则b ( d ，k ) 可递归的定义为 b ( d ，1 ) = 材；b ( a ，2 ) = l ( 耐) ；b ( d ，七) = l k - 1 ( 耐) ，k22 易知： b ( d ，k ) = l ( b ( d ，k 1 ) ) d eb r u i j n 网络这样一个简单的递 归结构是很有用的，它不仅能使我们通过线图导出d eb r u i j n 网络的许多 性质，而且它的任何重线图的顶点度不变这个性质表明若将b ( d ，) 作为 计算机互连网络的拓扑结构，则日后对其进行扩容或升级是方便的，因为 它不需要增加插口且d eb r u i j n 是d 正则的，无平行边，有d 个环， l 矿( 口( d ：女) ) l = d ，i e ( b ( d ，女) ) l = d k + 1 为了表述刚题的方便，我们做如下约定 约定1 d eb r u i j n 网络中的环不被认为是圈： 约定2 若i ，j 为自然数，彤成立表示i 是j 的因子，i 可以是1 ，也可以 是j 2 0 0 5 年中国科学技术大学硕士学位论文 2 l 3 2 定义在d eb r u i j n 网络1 - - 白9 右移变换 确定反馈数的下界，就是要确定网络中有多少个一定要被断开的有向 圈 定义3 2 1 记p = c 。，c 。，c 。) 为有向网络d 中两两互不相交的有向圈的 集合如果d p 不再包含有向圈，则称p 为d 的一个圈划分称n 为圈划 分的阶数 实际上，网络的任何一个圈划分的阶数，都是该网络反馈数一个下界 若阻圈划分的阶数来衡量圈划分的大小，选择比较大的圈划分，就可以比较 准确地确定了列络的反馈数的下界 命题3 2 1 网络的反馈数不小于网络的最大圈划分的阶数 定义3 2 2 记u 为d eb r u i j n 网络的一个顶点 的d 进制编码的每个组成 单位称为一个码称如卜定义在d eb r u i j n 网络中两个顶点v ，u 之问的变换 为d eb r u i j n 有移变换 西：v v u = x l z 2 - - x kh 西( u ) 一u = z 2 - x k x 并且称 为源，u 为像， 结合d eb r u i j n 网络的定义不难发现 可逆映射即：西( 口) = u u ；西- 1 ( u ) ； 边e ( b ( d ，) ) 西是建立在b ( d ，k ) 顶点集上的 且若咖( u ) = u ，则必存在一有向 定义3 2 3 若项点u 经过n 次连续的右移变换后与自身相等，则记最小们 自然数n 为u 的( 右移变换) 回归次数顶点u 称为n 次右移变换回归顶 点，或简称n 次顶点 b ( d ，k ) 中任一顶点”，最多经k 次连续的右移变换后，必可回归自 身特殊地，如果 编码的所有码均相同，则 必为1 次顶点：反过来，如 果u 为1 次顶点，则 所有的码必相同b ( d ，k ) 中共有d 个1 次顶点，分别 处于各自的环中 既然b ( d ，) 中任一顶点都可以经有限步的右移变换回归自身，那么在 网络中必然存在许多由右移变换所产生的圈在右移变换的过程中，源、像 2 0 0 5 年中国科学技术大学硕士学位论文 2 2 顶点的码的集合相同且从源到像编码是逐位变化的，我们有理由相信：这样 的一种变换所确定的路径一定是顶点沿有向边方向回归自身的最短道路 定义3 2 4 如顶点 b ( d ，k ) 为n ( 22 ) 次顶点，则 与其n 一1 个连续的 右移变换的像顺序连接，就构成一个圈称这样的圈为d eb r u i j n 网络中的 最小轨道其轨道长度记为n 右移变换的可逆性决定了不同的最小轨道是不相交的；且任一次数为n ( 2 ) 的顶点又必然处于某长为n 的最小轨道中因为不把环看成圈( 约定1 ) ， 所以诸最小轨道就构成了对b ( d ，) 的一个囤划分以b ( 2 ，4 ) 为例，f i g 3 2l 中的粗线表示其中的诸最小轨道 1 l “ 我们以此作为计算b ( d ，) 反馈数卜- 界的理论基础 命题3 2 2d eb r u i j n 网络的反馈数不小于网络中最小轨道的总数 3 3 d eb r u i j n 网络中反馈数的上下界 引理3 3 1 若i ，j 为互质的两正整数且i j ，则使得j l ( i n ) 成立的最小 的正整数n = j 证明 ( 略) 引理3 3 2 在b ( d ，k ) 中，记正整数i ，满足1 i 1 ) 位出现第一个码d 一1 ， 则u 的编码可以记为口：面= 可x ( d 1 ) y 孤表示不是d 一1 的其之 码，x 表示长为n 一2 的一段码或空集，其中没有任何一个码为d 一1 ，y 表 示一段码或空集因为”在一个有向圈中，沿着有向边的方向，v 的邻点u 的 编码就可以表示为x ( d 一1 ) y z ，z 1 0 ，1 ，d 一1 ) ，即 沿着有向圈方 向每前进一步，其编码巾码d l 的位置就向前移动一位如果u 处于某 有向圈中，那么u 就能沿着有向边的方向，经过不断的变换必可以回到自 身既然码d l 在顶点”的编码中首次出现是第礼位，那么在刚开始的连 续n 一2 次变换中，码d 一1 只可能在变换点编码的第一位到第n 范罔内出 现，所咀不可能回归v 本身因此必然要经过某一个以码d 一1 为首的顶点， 才能住卜一顶点或更卜几次变换时回归u 这就说明，在b ( d ，) f d l 中， 编码中出现码d 一1 的顶点不会出现在任何一个有向圈中如果要继续确定 原网络的反馈点集合，在考虑其它的有向圈时，只需考虑那些顶点中不出现 码d 一1 的顶点，也就是u ( d 一1 ，k ) 中的顶点因为不考虑环，编码中码全 部为d 一1 的一次顶点是可以保留在原网络中的递归特性可以简化这一过 程最后，从b ( 2 ，k ) 中去掉f 1 后，u ( 2 ，自) r 】为孤立带环点，此时网络中 已不再含有有向圈 定理3 3 2 b ( d ，女) 的反馈数的上界为耋2 i 一d + 1 证明 记f ( d ，k ) 为d eb r u i j n 网络b ( d ，女) 中由上述算法得到的反馈点集的阶 数，得 2 0 0 5 年中国科学技术大学硕士学位论文2 6 证毕 f ( d ，k )1 ，k ) 2 + ，( d 一2 ，女) + 菩_ ( d 3 4 结论 在b ( d ，k ) 中，当k 一2 时，反馈数的上界为2 1 + 3 1 + - + d 1 一d + 1 = 业笋；因2 l ，计算下界为且l + 等一d d + 堂孚盟一d = 争= 上界 此刊文中所确定的反馈点的卜界和下界相等文中算法得到的反馈点集就是 最小反馈点集 似旷一。妒一。 “ 盏辫一 l，l一，l一 一 一一 一一生。 扩 扩i扩i驴了。：lc。：f 第四章k a u t z n 络中的最小反馈点集研究 4 1 什么是k a u t z 网络 k a u t z 网络是k a u t z 于1 9 6 9 年提出来的，后来又有人独立发现了它k a u t z 网络具有许多与d eb r u i j a 网络一样的好性质，也有一些优于超立方体网络 的性质 定义4 1 1 对于给定的整数d 2 、k 1 ，k a u t z 有向刚络记为k ( d ，) ，其顶 点集v ( k ( d ，七) ) = f l z 2 茁k ：x i o ，1 ，d ，z t x i + l ，i = 1 ，2 ， ，k 一 1 1 ：k ( d ，) 中以顶点x l t 2 如为起点的d 条有向边的终点为x 2 x 3 z d ， 其f 1 f d ，l ，d ) ，q z k a u t z 网络也可以递归定义对于固定的d ，用表示d 阶完全有向图， 则( d ，) 可以递归地定义为：k ( d ，1 ) = + 1 ，k ( d ，2 ) = l ( t g + 1 ) ，( d ，k ) = 驴一1 ( 凰+ 1 ) k ( d ，七) 有d + d 一1 个顶点，d + 1 + d 条有向边，且是d 正则 的简单图 在顶点度和直径都一样的情况下，k a u t z 网络顶点数比d eb r u i j n 网 络顶点数多得多换句话说，在顶点度和直径都给定相同值的条件下，若 将k a u t z 有向网络和d eb r u i j n 有向网络都视为计算机互连网络的拓扑结构， 贝1 k a u t z n 络可以连接比d eb r u i j n 网络多得多的计算机例如，当顶点度和 直径都为8 时，d eb r u i j n 网络所能连接的计算机个数为6 5 5 3 6 ，而k a u t z 网络 所能连接的计算机个数为8 1 9 2 0 4 2k a u t z 网络顶点集合的等价划分 与d eb r u i j n 网络不同的是，k a u t z n j 络要求顶点编码中相邻的码不能 相同 定义4 2 1 记u 为k a u t z 网络的一个顶点u 的每个组成单位称为一个码。称 如下定义在k a u t j 网络两个顶点u ，u 之间的变换为最小变换 击：v ，矿 卜_ + 庐( ) = u 情况1 ：若顶点”的首位码和末位码不同，则 2 7 中国科学技术大学硕士学位论文2 8 ”r 。，( ”) = “：以”的首位码移动到其末位码之后形成一新 码，作为u 的编码： 情况2 ：若顶点v 的首位码和末位码相同，则 ”- + 9 ( ) = “：如情况1 得到u 的编码后，再把u 编码的最末 位改为它的首位码以此作为的编码 称“是”的最小变换点。 易知，最小变换是建立在k a u t z 网络顶点集合上的可逆映射与第三章d e b r u i j n 网络类似，我们定义能使k a u t z 网络中顶点u 经n ( 1 ) 次连续的最小 变换又回到自身的最小的自然数n 为u 的回归次数，同时称口为礼次顶点； 易$ k a u t z l 叫络k ( d ，k ) 中任一顶点的回归次数不会超过k ：与d eb r u i j n 嘲 络不l 口j 的是：k a u t z 网络中不包含1 次顶点；若 v ( k ( d ，) ) 为n ( 2 ns ) 次顶点，则 与其r t 一1 个连续的最小变换点顺序连接，构成k ( d ，k ) 中 的有向圈，称这样的圈为k a u t z 网络中的最小轨道，并记其长度为n ：反过来 也一样，每一个k 为n 的最小轨道，必包含且只包含n 个次数为n 的顶点： 同样，在k a u t z 网络中，包含着互不相交的诸最小轨道；如果称处于同一最小 轨道的两个顶点的关系为等价关系，则诸最小轨道实际上实现了对k a u t z 网 络顶点集合的等价划分 以k ( 2 ，3 ) 为例，f i g4 2 1 中粗线表示k ( 2 ，3 ) 中的诸最小轨道 2 0 2 0 0 5 年中国科学技术大学硕士学位论文 2 9 4 3 计算k a u t z 陬 络中的反馈数 引理4 3 1k a u t z n 络的反馈数不小于其最小轨道的总数 命题4 3 1 记w k ( i ) 为k ( d ，k ) 中i 次顶点的总数若itk 且i 十( 七一1 ) ， 则毗( i ) = 0 ；若i | 或il ( k 一1 ) ，则帆( i ) = 瞰( i ) 证明 记k ( i ) 是k ( d ，k ) 中所有i 次回归顶点的集合 1 、当i f k 且i t ( k 一1 ) 时，若w ；( i ) 0 ，则存在某 k ( t ) ， = 扩( ) ， 记v = 。l 。2 。 情况1 ：若u 的首、末码不同，则，( u ) = = ，( ) ，且i 是最小的使 得v = ，v ) 成立的正整数：记t = g c d ( i ，) ，即3 a ，b z ，s t a i + 6 = t 所以，。( u ) = f a i + b kv ) = u ，t 1 kk一1k k 一1 结合引理4 3 1 和引理4 3 2 ，可以直接得出k a u t z 网络反馈数的下界 定n 4 3 1k a u t z 络k ( d ，k ) 反馈数的下界为 盟掣+ 鲤辔型， 疗一l r 面确定反馈数的上界： 这里提供一种确定k a u t z 网络反馈集方法，由此可以很方便地确定反馈 数的上界以k ( 2 ，1 ) ，k ( 2 2 ) ，k ( 2 ，3 ) 为例，由算法所得1 i 含有向圈的子图 女n f i g4 31 所示( 空心点表示反馈点集) ： 2 0 0 5 年中国科学技术大学硕士学位论文3 1 k a u t z 网络是可以递归定义的，其结构的特殊性决定了下面简单的事实： 引理4 3 3 在k a u t z 丽j 络k ( d ，k ) 6 p - 去掉所有编码中出现码d 的顶点，剩下的 图就；黾k ( d - 1 ，k ) 利用k a u t z 网络的这个特性，可以给出确定反馈点集的具体方法 记f d 为k ( d ，) 中编码以码d 开头的顶点集合：r d 为k ( d ，七) 中编码出 现码d 的顶点集合按j i 如卜做法，可以确定k a u t z 网络的一个反馈点集： 第1 步：从k ( d ，k ) 中去掉集合乃：此时有k ( d ，) 吼= k ( d 一1 ，k ) ： 第2 步：从k ( d 一1 ，) 中去掉集合f d 一1 ；此时有k ( d 一1 ，七) r d 一1 = k ( d - 2 ，k ) ； 第d 步：从k ( 1 ，) 中去掉集合f 1 = 1 x ) ( l x ) 表示首位编码为1 的长 度为k 的单个顶点集合) f = u d ：。只就是所求的k a u t z 网络的一个反馈点集 本做法具有很强的递推性，故只需要就做法的第一步和最后一步给出论 证 经第步后，从图上去掉了l f d = 韭d 4 ! 二个以码为首的顶点，剩下的- 1 d 图如果还包含有有向煳，那么这些有向嘲所经过的所有顶点中，没有一个顶 点的编码中会出现码d 如果k ( d ，) f d 含有一包含顶点v 的有向圈，而 的编码中出现码d ， 设u 的编码巾从左到右数在第n ( 1 ) 位出现第一个码d ，则 的编码 可以记为v = d x d y d 表示不是d 的其它码，x 表示长为n 一2 的一 段码或空集，其中没有任何一个码为d ，y 表示一段码或空集v 在一个有 向圈中，沿着有向边的方向，u 的邻点“的编码可以表示为x d y z ，z 0 ，1 ，册且z 与y 的最后一个码不同，即u 沿着有向圈方向每前进一步， 其编码中码d 的位置就向前移动一位如果v 处于某有向圈中，即u 能沿着 有向边的方向，经过不断的变换回到自身那么考察其中编码的位置就会发 现，在变换过程中，d 由原来位置开始，不断前移既然码d 在顶点”的编 码中首次出现是第礼位，那么在刚开始的连续n 一2 次变换中，码d 只可能 在变换点编码的第二位到第n 范围内山现，所以不可能回归”本身因此必 然要经过某一个以码d 为首的顶点，才能在卜一顶点或更卜几次变换时回 中国科学技术大学硕士学位论文3 2 归 这就说明，在f d ，) 毋中，编码中出现码d 的顶点不会出现在任何 一个有向圈中如果要继续确定原图的反馈点集合，在考虑其它的有向圈时， 只需考虑那些顶点中不出现码d 的顶点，也就是k ( d 一1 ，k ) 中的顶点递归 特性可以简化这一过程 随着d 的不断减小，问题归结为求k ( 1 ，k ) 中反馈点集合而对任何k2 2 ，k ( 1 ，k ) 均为有向娲，其反馈点集合容易求出 定理4 3 2k ( d ，k ) 的反馈数的上界为耋li 一1 ( d 1 ，七2 ) 证明 记f ( a ，k ) 为k a u t z 网络k ( a ，k ) 中按上述方法得到的反馈点集的阶数 得 州，纠：等竿+ ，( d - 1 , k ) 证牛 d + d 一1 ( d 1 ) + ( d 一1 ) 一1 d + 1d d + d k 一1 d + 1 亡鲨 ，i + 1 r i t 一1 塑二! 生( ! 二! ! ! ： d 十f ( d 2 ，k ) 一+ 竽+ - + + 毛一十1 4 4 确定最小的反馈点集 在k ( d ，纠中，2 次琐点的总数仅与d 有关，为( d + i ) d 当k = 3 时，k ( a ，3 ) 巾仅有2 次回归顶点和3 次回归顶点，个数分别为( d + 1 ) d 和d 3 + 舻一( d + 1 ) d ：d a d 当k ：2 时，反馈数的下界为鲤笔迎+ 垃旦掣= 亟些垫笋蝗l 型+ 妒( 1 ) g ( 1 ) = 堑字，上界为冬1i = i l + 2 1 + + 毋= 下界： 当：3 时，反馈数的下界为垃萼迎+ 止萼坦：虹些塑凄幽+ 掣： d a 亏d + o + 掣，上界为耋1 i 2 = 1 2 + 2 2 + + d 2 = 韭生必6 = 下 2 0 0 5 年 中国科学技术大学硕士学位论文 3 3 界即当2 k 3 时，文中所确定的反馈数的上界和下界相等，由此确定出 的k ( d ，k ) 中的反馈点集就是最小反馈点集 第五章后记 确定反馈数的下界，就要计算网络中有多少个圈为使原图的导出子图 不再包含圈，则每一个圈都至少要被去掉其中的。个点如果可以在网络中 找到许多互不相交的网，并且去掉这些圈后网络中不再包含其它的圈，则这 些囤的总数就是反馈数一个比较好的卜界自然，我们希望这个卜_ 界越火越 好，对应地就是希望这些圈的总数尽可能地大一些又因为网络中顶点的总 数是一定的，唯有每一个圈的长度尽可能地小，才能使圈的总数尽可能地大 这就是我们给出d eb r u i j n 网络和k a u t z 网络中最小轨道定义时最初的想 法以最小轨道的总数去度量反馈数的下界，不仅仅局限于d eb r u i j n 嘲络 和k a u t z 网络对一般网络也同样适用 研究网络应从其构造的特殊性着手虽然不能解决一般网络的反馈问题， 对具体的网络却可以深入研究其互连规律，针对这一规律采取相应的方法 以d eb r u i j n 网络和k a u t z 网络为例，其线图的递归定义级级叠加，如同集 滴水为大海，汇片术成森林低阶网络和高阶网络存在着内在的相似性，高 阶网络包含着低价网络，而低价网络隐含有高阶网络的信息随着线图构造 的不断作用，沿着网络的某一特定参数，我们发现：点被解释为对称边、三 角形、乃至其他而点、对称边、三角形具有很明显的共性，三者住某种定义 下应该是一致的高阶网络是低阶网络具体细节某种形式的放大释义，而低 阶网络包含有高阶网络的所有特性，但因为阶数太低，有的信息被隐藏，不 易发觉 第六章文章的创新点 创新绝不是胡思乱想创新思维唯一的活水源头就是具体问题具体分析 从研究问题的实际情况出发，尽一切可能的方法去获取答案没有创新点，就 很难超越前人的高度而要想取得突破性的进展，则必须借助创新思维，以 从来未被人尝试过的角度去研究问题 通常把图看成顶点和连边的集合，或抽象成某现实问题的数学模型，或 看成某代数结构看法的不同取决于研究问题性质的不同反馈问题是研究 如何使图不再包含圈，因此圈成了图的一个最基本的参数考虑到反馈问题 的实际情况，图在这里应该被看成仅仅是诸多互不相交的囤的集合，这就是 本文对图的全新的视角两个不同的图，只要它们包含的圈是相同的，就认 为两者之间是没区别的对d eb r u i j n 网络，可以只考虑成诸最小轨道的集 合，而置1 次顶点于不顾；而k a u t z 网络则可以看成完全是最小轨道的集合 k a u t z 网络不再是点、边的集合，也不再是代数结构，只是一些圈的集合，这 些圈是互不相交的犹如堆成一堆的大小不尽相同的珍珠项链只要数一数 项链的个数，就可以确定反馈数的下界 3 5 参考文献 【1 】mrg a r e y ，dsj o h n s o n ，c o m p u t e r sa n di n t r a c t a b i l i t y ，f r e e m m a ，s a nf r a n - c i s c o ，c a ，1 9 7 9 【2 as h a m i r ，al i n e a rt i m ea l g o r i t h mf o rf i n d i n gm i n i m u mc u t s e t si nr e d u c i b l e g r a p h s ，s i a mjc o m p u t 8 ( 4 ) ( 1 9 7 9 ) 6 4 5 6 5 5 【3 】ydl i a n g ，msc h a n g ，m i n i m u mf e e d b a c kv e r t e xs e ti nc o c o m p a r a b i l i t y g r a p h sa n dc o n v e xb i p a r t i t eg r a p h s ，a c t ai n f o r m 3 4 ( 1 9 9 7 ) 3 3 7 - 3 4 6 【4 】cw a n g ，ell l o y d ，mls o f i a ，f e e d b a c kv e r t e xs e t sa n dc y c l i c a l l yr e d u c i b l e g r a p h s ，j a c m3 2 ( 2 ) ( 1 9 8 5 ) 2 9 6 - 3 1 3 5 】ydl i a n g ，o nt h ef e e d b a c kv e r t e xs e ti np e r m u t a t i o ng r a p h s ，i n f o r m p r o c e s s l e f t5 2 ( 3 ) ( 1 9 9 4 ) 1 2 3 1 2 9 f 6 】gws m i t h rbw a l f o r d ，t i l ei d e n t i f i c a t i o no fam i n i m a lf e e d b a c kv e r t e xs e t o fad i r e c t e dg r a p h ，i e e et r a n sc i r c u i t ss y s t e m sc a s 一2 2 ( 1 ) ( 1 9 7 5 ) 9 1 4 【7 】fll u c c i o ，e x a c tm i n i m u mf e e d b a c kv e r t e xs e ti nm e s h e sa n db u t t e r f l i e