（运筹学与控制论专业论文）本原几乎可约矩阵的k指数.pdf

摘要 本文主要研究本原几乎可约矩阵的k 一顶点指数。我们采用图论 的语言来描述、用图论的技巧和方法来研究我们的问题。研究本原几 乎可约矩阵的k 一指数等价于研究本原极小强连通有向图的k 一指数。 1 9 8 2 年，j a r o s s i l 咳0 划了围长为g 的n 阶本原极小强连通有向图 的本原指数最大值和极图。1 9 9 1 年，邵嘉裕l z i 刻划了n 阶本原极小 强连通有向图的本原指数集。1 9 9 9 年，柳柏濂【3 】刻划了最大值，2 0 0 2 年周波【4 】刻划了极图，但是k 一指数集还没有被研究。2 0 0 5 年，胡亚 辉l s l 将j a r o s s 的结果推广到了k 顶点指数，并完全刻划了本原几 乎可约矩阵的卜指数集。本文将在以上的基础上，研究了最小圈长 为2 的本原极小强连通有向图卜顶点指数，并完全刻划其卜指数集。 在第一章，我们介绍了一些最基本的概念及广义本原指数的研究 进展。 在第二章，我们介绍了有关顶点指数和极小强连通有向图的一些 基础知识。主要介绍了f r o b e n i u s 数及其估计，数e x p d ( 甜) 和数e x p d ( “，) 的估计极小强连通有向图的若干结论及n 阶本原极小强连通有向图 的上界和极图。 在第三章，我们研究了当n 是偶数时，n 阶最小圈长为2 的本原 极小强连通有向图的卜指数集。并得到了如下结果：设刀( 4 ) 为偶数， 则e ( 1 ) = 4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，11 2 n - 7 ，2 n - 6 ，2 n - 5 ，2 n - 4 ) 。 在第四章，我们研究了当n 是奇数时，n 阶最小圈长为2 的本原 极小强连通有向图的卜指数集。并得到了如下结果：设胛仑4 ) 为奇数， 贝i je ( 1 ) = 4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1l 2 n 一8 ，2 n 一7 ，2 胛一6 ，2 n 一5 ) 。 关键词：本原矩阵，几乎可约矩阵，极小强连通有向图，卜指数 a bs t r a c t t h i st h e s i si sd e v o t e dt ot h es t u d yo ft h ek 。e x p o n e n to fp r i m i t i v e n e a r l yr e d u c i b l em a t r i c e s w eu s eg r a p h t h e o r e t i cv e r s i o nt or e l a t e ，u s e g r a p h - t h e o r e t i c m e t h o d sa n dt e c h n i q u e st o p r o v e o u rr e s u l t s t h e a s s o c i a t e dd i g r a p ho fap r i m i t i v en e a r l yr e d u c i b l em a t r i xi sap r i m i t i v e m i n i m a l l ys t r o n gd i g r a p h i n 19 8 2 ，j a r o s s 1 1c h a r a c t e r i z e dt h e m a x i m u ma n de x t r e m a ld i g r a p ho ft h ee x p o n e n to fp r i m i t i v em i n i m a l l y s t r o n gw i t hnv e r t r i c e sa n dg r i t hg i n19 91 ，j i a o y us h a o 2 1c h a r a c t e r i z e d t h ee x p o n e n ts e t i n19 9 9 ，b o l i a nl i u p 1c h a r a c t e r i z e dt h em a x i m u m i n 2 0 0 2 ，b oz h o u 4 1c h a r a c t e r i z e dt h ee x t r e m a ld i g r a p h i n2 0 0 5 ，y a h u i h u 5 1g e n e r a l i z et h er e s u l t so fj a r o s st ot h ec a s eo ft h ek - e x p o n e n ta n d c o m p l e t e l yc h a r a c t e r i z et h e1 - e x p o n e n ts e t o nt h o s eb a s i s ，w ek n o w t h a tt h ep r i m i t i v em i n i m a l l ys t r o n gw i t hnv e r t r i c e sa n dg r i t h2 i nt h i s t h e s i sw ec o m p l e t e l yc h a r a c t e r i z et h e 1 - e x p o n e n t o ft h e p r i m i t i v e m i n i m a l l ys t r o n gw i t hnv e r t r i c e sa n dg d t h 2 i nc h a p t e r1 ，w ei n t r o d u c eaf e wb a s i cc o n c e p t s ，s u m m a r i z et h e b a c k g r o u n da n da d v a n c e m e n to f t h er e s e a r c ho ng e n e r a l i z e de x p o n e n t s i nc h a p t e r2 ，w ei n t r o d u c et h ee x p o n e n to ft h ev e a e xa n ds o m e b a s i ck n o w l e d g ea b o u tt h ep r i m i t i v em i n i m a l l ys t r o n gd i g r a p h w e m a i n l l yi n t r o d u c et h ef r o b e n i u s 、t h en u m b e re x p d ( “) 、t h en u m b e r e x p d ( 材，1 ，) a n d i t se s t i m a t i o n l a s tw ei n t r o d u c es o m er e s u l ta b o u tt h e p r i m i t i v em i n i m a ll ys t r o n gd i g r a p ha n dt h em a x i m u ma n d e x t r e m a l d i g r a p ho ft h ep r i m i t i v em i n i m a l l ys t r o n gd i g r a p h i nc h a p t e r3 ，1 - e x p o n e n t so fp r i m i t i v em i n i m a l l ys t r o n gd i g r a p h s a r es t u d i e dw h e nni se v e n t h ef o l l o w i n gr e s u i t sa r eo b t a i n e d ： 色( 1 ) = 4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，11 2 n - 7 ，2 n - 6 ，2 n - 5 ，2 n - 4 w h e r eni se v e n i nc h a p t e r4 ，1 - e x p o n e n t so fp r i m i t i v em i n i m a l l ys t r o n gd i g r a p h s a r es t u d i e dw h e nni so d d t h ef o l l o w i n gr e s u i t sa r eo b m i n e d ： e ( 1 ) = 4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，11 2 n - 8 ，2 n - 7 ，2 n - 6 ，2 n 一5 w h e r eni so d d k e yw o r d s ：p r i m i t i v em a t r i c e s ，n e a r l yr e d u c i b l em a t r i c e s ， m i n i m a l l ys t r o n gd i g r a p h s ，1 - e x p o n e n t s 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。论文主要是自己的研究所得，除了已注明的地 方外，不包含其他人已经发表或撰写过的研究成果，也不包含为获得 中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献，已在论文的致谢语中作了说明。 作者签名：盔 日期： 型茎年堑 月三么一日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其他手段保存学位论文； 学校可根据国家或湖南省有关部门的规定，送交学位论文。对以上规 定中的任何一项，本人表示同意，并愿意提供使用。 作者虢正导师虢烨学嗍吐年上月丛日 硕士学位论文 第一章引言 第一章引言 组合矩阵论是近三十年兴起并发展迅速的一个数学分支，它用矩 阵和线性代数来证明组合性定理及对组合结构进行描述和分类。同 时，也把组合论的思想和论证方法用于矩阵的精细分析及揭示阵列的 内在组合性质。组合矩阵不仅与众多的数学领域有密切的联系。而且 在信息科学、社会学、经济数学和计算机科学等许多方面都有具体的 应用背景。 非负矩阵的幂序列是组合矩阵论中一个重要的研究领域。不可约 矩阵在非负矩阵中占有十分重要的地位。几乎可约矩阵是最小不可约 矩阵。所以研究几乎可约矩阵的幂序列是很有意义的。 1 1 基本概念 定义1 1 1 ：设a 是一个n 阶的非负矩阵，如果存在一个置换矩 阵p 使得 尸7 1 彳p = ( 尝暑) icdj 其中b ，d 为非空方阵，则称a 是可约的，否则称a 是不可约 的。如果a 是一个不可约矩阵，但是把a 的任一个非零元素变为“o ， 都将把a 变成一个可约矩阵，那么我们称a 为几乎可约矩阵。就是 说，几乎可约矩阵是最小不可约矩阵。 定义1 1 2 ：一个n 阶非负矩阵称为本原的，如果存在正整数k 使a 0 ，这样的最小的k 称为a 的本原指数。记为7 ( 彳) 。 显然，矩阵的本原性与本原指数只与这个矩阵的零位模式有关。 因此，研究非负矩阵的本原性与本原指数只需研究具有相同零位模式 的( 0 ，1 ) 布尔阵就可以了。有向图是刻画布尔矩阵零位模式的典型 组合模型。一个n 阶布尔阵a = h ，) 对应于一个n 阶有向图d ( a ) = ( v ，e ) ，顶点集v = v i ，2 v 。) ，e 为弧集，其中口f ，= l 当且仅当 ( 1 ，f ，) e 。d ( a ) 称为a 的伴随有向图。反过来，给定一个有向 硕士学位论文第一章引言 图d ，就有相应的布尔阵a ( d ) 。 定义1 1 3 ：设d = ( v ，e ) 表示一个具有n 个顶点的有向图。 d 中从顶点u 到顶点v 的长为p 的途径( w a l k ) 万( 或u w v ) 是指 甜_ 专u 2 专j ”。= 1 ，( 这里x 专y 是指x 到y 的一条弧) ，其中的顶 点可以重复，我们记万0 胁) = ( 甜，材l ，甜2 u p - i ，) ，其长用刁( 万) ( 或r l ( u w v ) ) 表示，u 称为万的起点，v 称为万的终点，材，u 。，u ：u 称为万的内部顶 点。若u = v ，称万是闭途径。 如果万中所有的点均是相异的( 从而弧也相异) 称1 l 是一条长为 p 的路( p a t h ) 。若万中除u = v 外，所有顶点都相异，则称万为长为p 的圈( c y c l e ) ( 或闭路) 。长为l 的圈称为环( 1 0 0 p ) 。 设a 为a 阶布尔阵，a = 0 ) ，那么我们有： 定理1 1 1 1 6 7 1 ：d ( a ) 中存在从 ，。到，的长为p 的途径 口：p 0 营d ( 彳p ) 中有( v f ，1 f h ； 从而我们可以用图论的语言给出本原指数的定义。 定义1 1 4 ：设d = ( v ，e ) 为有向图，若存在正整数k ，使对 于d 中的任意两点1 ，1 ，存在从 ，到，的长为k ( 从而有大于k ) 的 途径，则称d 是本原的，这样的最小的k 称为d 的本原指数，记为7 ( d ) 。 显然有y ( d ) = y ( 彳) 。 定义1 1 5 ：设d = ( v ，e ) 是一个有向图，如果对d 中任意两 个顶点u ，v ，在d 中存在从u 到v 和从v 到u 的途径，则称d 是强连 通的。如果一个强连通有向图d 中去掉任何一条弧所得的有向图不 是连通的，我们称d 是极小强连通的。 我们有： 定理1 1 2 1 6 - 7 l ：( 1 ) 矩阵a 不可约当且仅当d ( a ) 强连通。 ( 2 ) a 几乎可约当且仅当d ( a ) 极小强连通。 l9 9 0 年，r a b r u a ld i 和柳柏濂基于无记忆通讯系统的背景将本 原指数作了推广，引入了三个广义本原指数：k 顶点指数，k 重上指 数和k 重下指数。考虑一种无记忆通信系统：它表现为一个带n 个顶 点的有向图d ，假设在时间t = 0 时，d 中k 个顶点( 1 k 聆) 掌握着 不同的信息，当t = l 时，每个顶点把它掌握的信息传递给所有出弧的 终点，而自己却失掉( 忘记了) 这个信息。当然，它可以同时接受来 自该顶点所有入弧的起点的信息。以这种方式继续不断地传递信息， 现在要问：使d 中每个顶点都同时掌握原来的k 个信息所花的最短 时间是多少? 如果初始时间的k 个顶点掌握着同一个信息，那么又需 2 硕士学位论文第一章引言 要多少时间，才能使d 中的每个顶点都掌握着这个信息? 定义1 1 6 ：设d = ( v ，e ) 为有向图，顶点集v = h ，1 ，2 1 ，。 ，e 为弧 集定义e x p d ( 一，v j ) 是这样最小的整数p ，使对于每一个整数，p ，从顶点v 到顶 点v ，都有长为t 的途径( 1 f ，胛) ，称e x p d ( v ) = m a x e x p ) ( v ，) 为顶点_ 的 指数。 v j e l , 。 我们将d 中各顶点的指数按从小到大的顺序排列： e x p d ( 、) e x p d ( 、) e x p d ( 、) ，我们称数e x p d ( v ) 为d 的k 顶点指数( 简 称缸指数) ，记为e x p d ( 尼) ( 或e x p ( d ，七) ) ，这正是无记忆通讯系统中，把k 个不同 信息同时传递到每个顶点所花费的最短时间。显然地， r ( d ) = e x p d ( ，z ) = m a 孑x e x p d ( 哆) ) = m d ( v j ，) ) 若 ，) ( 门) ，则d 是本原的agxexpexp - b o o 定义1 1 7 ：设x c _ 矿( d ) ，i x i = k ，集指数e x p d ( x ) 是这样最少的整数p ，使 得对于d 中的每一个顶点m ，从x 中至少有一个点，存在从此点到v f 的长为p ( 从 而大于p ) 的途径。 定义1 1 8 ：记 f ( d ，k ) = m i n e x p d ( x ) ) ，f ( d ，后) = m a nc - r g f - ki x l = k 我们称厂( d ，助为d 的第k 重下指数，称，( d ，幼为d 的第k 重上指数。 f ( d ，助正是无记忆通讯系统中，把一个信息从k 个顶点传递到每个顶点所耗 费的最小时间。，( d ，d 正是无记忆通讯系统中，把一个信息从k 个顶点传递到 每个顶点所耗费的最大时间。 由于布尔阵与有向图的对应关系，我们也可相应地用矩阵的语言给出三类广 义指数的定义。设a 为行阶布尔阵，e x p 彳( 七) ( 或e x p ( a ，后) ) 是a 的最小幂指数， 使得在这个幂中，存在k 个全l 行。f ( a ，k ) 是a 的最小幂指数，使得在这个幂 中，存在着k 行组成的子矩阵，此子矩阵无零列。f ( a ，k ) 是a 的最小幂指数， 使得在这个幂中，不存在k 行组成的子矩阵，此子矩阵有零列。 为方便起见，我们记【口，6 】- 脚lm z ，a m b ) ，用i 口i 表示不超过口的 最大整数，用口 表示不小于口的最小整数用isi 表示集合s 中元素的数目。 本文所要解决的就是当本原极小强连通有向图的最小圈长为2 时，其k 顶点指数中，1 指数集的问题，记为e ( 1 ) 。图d 的卜指数， 记为e x pr ) ( 1 ) 。 1 2 本原指数与广义本原指数的研究进展 硕士学位论文第一章引言 设f 2 。是某刀阶布尔矩阵类，e ( a ，k ) e x p ( a ，七) ，f ( a ，七) ，f ( a ，七) ) 。记 7 ( q 。) 2 搿 厂( 彳) ，p ( q 一，| ) 5 搿 p ( 彳，砒一e 1 2 e o r ( n 。) = aia q 。，r ( a ) = r ( n 。) )e ( n 。，k ) = aia q 。，e ( a ，k ) = e ( n 。，七) ) r ( n 。) = y ( 彳) la q 1 )e ( n 。，k ) = e ( a ，七) ia q 。) 我们研究的问题主要有三个： ( 一) 上界估计( 最大值问题) ：确定r ( n 。) ，e x p ( f 2 。，k ) ，厂( q 。，k ) ，f ( q 。，k ) 极阵问题：刻划歹( q 。) ，面( q 。，七) ，7 ( q 。，七) ，f ( n 。，七) 指数集问题：刻划r ( n 。) ，e x p ( f 2 。，k ) ，f ( n 。，k ) ，f ( n 。，k ) 下面，我们就各类矩阵分述其研究进展： 1 n 阶本原阵( 肼。) ( 1 ) 本原指数研究 1 9 5 0 年，h w i e l a n d t l 9 1 首先刻划了，( 眦，) = ( i - - 1 ) 2 + l ( 叁q ) ，并刻划了极 矩阵厂( 眦，) = a l a 置换相似于呢 ，其中 k 2 0l 00 0o 00 l1 o 1 0 o 0 o0 00 1o o1 oo 3 x = 1 9 6 4 年，a l d u l m a g e 和n s m e n d e l s o h n m 】给出了以d ( a ) 的最小圈 长g ( 围长) 为参数的本原指数的最好上界r ( a ) n + g ( n 一2 ) 。1 9 8 5 年，邵嘉裕【l l j 刻划了使r ( a ) = 刀+ g ( n 一2 ) ( g 2 ) 的极矩阵。1 9 9 1 年，柳柏濂和邵嘉裕1 1 2 1 刻划 了使r ( a ) = n + g ( n 一2 ) ( g = 1 ) 的极矩阵。1 9 9 5 年，沈健【l 刻划了以a 的最小多 项式的次数m 为参数的本原指数的上界y ( 彳) ( m 1 ) 2 + 1 ，1 9 9 6 年，沈健【1 4 l 刻划 了使y ( 爿) = ( 册一1 ) 2 + l 的极矩阵，还刻划了以d ( a ) 的直径d 为参数的本原指数 的上界y ( 彳) d 2 + l ，1 9 9 6 年，s n e u f e l d1 1 5 i 刻划了使y ( 彳) = d 2 + l 的极矩阵。 非负矩阵a 的布尔秩是最小整数k ，使得对某个非负矩阵最。和g 。，a 和b c 有相同的( 0 ，1 ) 模式矩阵。1 9 9 5 年，d a g r e g o r y ， s j k i r k l a n d 和n j p u l l m a n1 1 6 刻划了以a 的布尔秩b 为参数的本原指数的上界： y ( 彳) ( b 一1 ) 2 + 2 对于2 b 万一l ，也刻划了取得这个上界的极矩阵。 1 9 6 4 年，a l d u l m a g e 和n s m e n d e l s o h n t o , 1 7 l 揭示了y ( 肼。) 中存在缺 数段( g a p ) 1 9 8 1 年，m l e w i n 和y v i t e k 叫给出了一个确定【| 2i + l ，】中 的所有缺数段的一般方法，并猜想【1 ，i 纪2i + l 】，间不存在缺数段。1 9 8 5 年，邵 4 硕士学位论文 第一章引言 嘉裕0 9 证明了对于充分大的1 1 ，l e w i n v i t e k 的猜想是正确的，且 4 8 萑歹( 肼1 1 ) 1 9 8 7 年，张克民2 0 1 证明了：除了4 8 萑) ( p a i l l ) ，以外，l e w i n v i t e k 的猜想是正确的，从而7 ( 蹦。) ，被完全刻划出来了，即 f , ( p m 。) = 【1 ，i 警l + 1 】uu 【p ( g 1 ) ，卯( g 一2 ) + 门】( 刀1 1 ) ， l j p n r ( p m l l ) = 【l yo ，4 7 u 4 9 ，5 1 】uu 【p ( q 一1 ) ，p ( q 一2 ) + 1 1 】 p q l i ( 2 ) k 指数研究 1 9 9 0 年，r a b r u a l d i 和柳柏濂i s 得到e x p ( 啦，k ) = 刀2 3 n + 2 + k 1 9 9 4 年，邵嘉裕，王建中和李桂荣刻划了e x p ( p m 。，七) 对e x p ( 川，七) ，显然e x p ( 蹦，门) = 7 ( 蹦，) ；对于1 k 刀一l ，1 9 9 8 年，沈建和s n e u f e l d t 2 2 j 刻划了 e x p ( p m ，1 ) = 【1 ，i 1 ( 以2 3 n + 4 ) wu 【( p 1 ) ( g 1 ) ，p ( q 一2 ) + ? l - - g + l 】 2 p n 2 0 0 0 年，苗正科和张克 1 5 2 3 1 刻划了e x p ( p m ，七) ( 2 k 聆一1 ) ( 3 ) 第k 重下指数研究 设d ( a ) 有一个长为s 的圈( 1 占刀) r a b m a l d i 和柳柏濂证明了 心， ，靴b l疗一+ l l 一，一 ，右l 七，一1 ， ) = 【 2 l 2j 7 j 7” l 力一l + ( 七- r ) ， 若，k 1 并刻划了极矩阵e x p ( 瞩，七) 2 0 0 0 年，邵燕灵和高玉斌1 刻划了k - 指数 集e x p ( p s , r ，k ) ( 2 ) 第k 重上指数研究 1 9 9 8 年，高玉斌和邵燕灵m 垓0 划了f ( 确，k ) 。2 0 0 0 年，邵燕灵和高玉斌 刻划了极矩阵f ( 飓，k ) 1 2 n 阶本原几乎可约阵( 纠峨) ( 1 ) 本原指数研究 【1 ，2 ，6 8 ，6 9 ，7 0 ，7 1 】研究了本原几乎可约矩阵的本原指数1 9 8 0 年，r a b r u a l d i 和j a r o s s c a l 证明了y ( 用岷) = 刀2 4 n + 6 ，并刻划了极矩阵 7 ( 纠岷) 1 9 9 1 年，邵嘉裕和胡志庠【2 垓0 划了指数集 y ( 帆) = 甩+ g ( n - 3 ) 1 2 g 聆一2 ，( g ，疗一1 ) = 1 ) u 【6 ，l ( 刀2 6 n + 1 4 ) 2i 】 u u 【p ( q 1 ) + 1 ，p ( q 一2 ) + 刀】 p + 4 打 ( p ，口) = l ( 2 ) k 指数研究 1 9 9 9 年，柳柏濂【3 l 证明了 e x p ( 聊嗯，k ) = n 2 5 n + 7 + k ， 门2 4 n + 5 ， 丹2 4 n + 6 ， 若1 k 7 - - 2 ， 若k = r l - - 1 ， 若k = 刀 2 0 0 2 年，周波4 垓0 划了极阵；而( 用岘，尼) ( 3 ) 第k 重上指数研究 1 9 9 9 年，柳柏濂3 1 证明了 9 硕士学位论文第一章引言 一 ，i 刀2 4 n + 6 ，若k = 1 ， f ( p n r 七) 2 1 ( 刀一1 ) 2 一七：刀一2 ) ，喜2 七刀一1 1 9 9 8 年，周波1 7 2 l 刻划了极阵f ( 眦，k ) 1 3 其伴随有向图的最小圈长为g 的n 阶本原几乎可约阵( 帆。) 1 9 8 2 年，j a r o s s l l l 证明了厂( 佩窖) = n + g ( n - 3 ) ，并刻划了极阵y ( 佩) 1 4 刀阶布尔阵( 未必本原) ( 最) 当a 本原时，r ( a ) ，e x p ( a ，k ) ，f ( a ，k ) ，f ( a ，k ) 都是有限的。当a 非本原 时，厂( 彳) = - b o o ，但广义本原指数仍然可能存在( 有限) ，若e x p ( a ，k ) 4 - 0 0 ，我们 称彳是肛本原的；若f ( a ，k ) 0 ，故而+ 1 q ，而+ 1 呸 得口l 口2 = q ( 五+ 1 ) + 口2 ( 屯+ 1 ) 2 q 口2 不可能。 证毕 定理2 1 3 7 1 ：设( 口l ，a 2 ，口3 ) = 1 ，q ，a 2 ，口3 为正整数，则 矽( 口l ，口2 ，口3 ) 羔+ 口3 ( 口l ，呸) 一口1 一呸一口3 + 1 、“l ，“2 j 当口3 是一去一_ 旦弋时，等式成立。显然以上q ，a 2 ，口3 可以轮换。 ( q ，口2 ) 2( 口l ，口2 )( q ，口2 ) 1。 2 2 指数e x p d ( “) ，e x p d ( 甜，1 ，) 的估计 定义2 2 1 ：设d = ( 矿，e ) 是本原有向图，上( d ) = ，i ，吃，么) 是d 中不同圈 长的集合且 吒 么，g c d ( ，吒，匕) = l 。对“，y ( d ) ，从”到v 的距离 硕士学位论文第二章顶点指数及极小强连通有向图的若干基本知识 厶( 材， ，) 是指在d 中从u 到v 中的最短途径( 也是最短路) 的长，从1 , l 到1 ，的广 义相对距离巩( d ) ( 甜，v ) 是指d 中从u 到v 的接触d 的所有圈长( 某途径经过长 为r 的圈的某个顶点，则称此途径接触了圈长r ) 的最短途径的长。 定理2 2 1 1 1 9 l ： 设d = ( v ，e ) 是n 阶本原有向图，l ( d ) = r l , r 2 ，r a ) ，那么 e x p i ) ( ”，) d l ( d ) ( “，1 ，) + 九( d ) ，其中丸( d ) = 矽( ，吃，么) 。 由定理2 2 1 可得 定理2 2 2 ： 设d = ( v ，e ) 是n 阶本原有向图，l ( d ) = r l , r 2 9o 9 么) ，则 e x p d ( “) m a x 以( d ) ( “，v ) iv v ) + 丸( d ) e x p d ( 刀) m a x d l w ) ( ”，1 ，) i ”，y v ) + 九( d ) 定理2 2 3 ：设d = ( v ，e ) 是n 阶本原有向图，l ( d ) = r l , r 29o o ，吃 ，设 i _ q ( d ) = 气，r i 2 ，气) sl ( d ) 且g c d ( r ，；：，_ ) = l 。则对v u ，y ，有 e x p d ( 甜，) sd 4 ( d ) 【“，) + 矽h ( d ) e x p d ( 甜) m a x 叱( d ) ( ”，v ) lv y ) + 九( d ) 其中九( d ) = 矽( ，么，i ) 。 证明设u w v 是从甜到1 ，的接触圈c l ，c f 2 9o - 9 q ( 其中c 。，是d 中某个长为0 的圈，_ ，= l ，2 ，k ) 的长为吒( d ) ( 甜，1 ，) 的一条途径。则对任一组非负整数 a i ，a 2 ，口七，存在一条从“到，的长为叱( d ) ( ”，) + 口l + a 2 r ，2 + + 咏i 的途径： u w v = “胁+ q + + 吒+ 、- v j 口1 个 乞手手手手手手乞 口2 个 即每一个能表为形如叱( d ) ( ，v ) + 口l + 口2 气+ + q i 的数是d 中从“到1 ，的某条 途径的长。而由f r o b e n i u s 数的定义，每个不小于叱( d ) ( 甜，v ) + ( ，r , 2 ，气) 的数 能表为吒( d ) ( ，1 ，) + q _ + a 2 r f 2 + + 吼气，所以 e x p d ( 甜，v ) 叱( j d ) ( 甜，v ) + 九( d ) 从而有 e x p d ( “) m a x d 厶( d ) ( 甜，v ) 1 1 ，y ) + 九( d ) 证毕 定理2 2 4 ： 设d = ( y ，e ) 是1 1 阶本原有向图，l ( d ) = ，r 2 ，么) ，设 厶( d ) = ，吃，气 三( d ) ，1 仨厶( d )g c d ( r , , ，乞，气) = l 。如果从顶点u 到 顶点v 的长度不小于a ( a 为正整数) 的每一条途径的长能表为 r i ( u w v ) 2 z + z 2 气+ + 气气+ 口( 其守z ，i 乞，：，乙为非负整数) ，那么 e x p o ( u ，v ) 口+ 九( d ) 证明 名：e x p d ( “， ，) 口。从而 口+ 九( d ) - 1 - z i + z 2 么+ + 气气+ 口( 其中z iz 2 ，z k 为非负整数) 。 所以 硕士学位论文 第二章顶点指数及极小强连通有向图的若干基本知识 吒( d ) 一l2z i r f , + 乞气+ + 磊i ， 这与吮( d ) 是，：i ，气9 - - * 9 气的f r o b e n i u s 数矛盾。 e x p d ( 甜，) 口+ 九( d ) 证毕 由引理2 2 ，3 和引理2 2 4 ，我们有 定理2 2 5 ： 设d = ( v ，e ) 是一本原有向图，l ( d ) = r l , r 2 ，r a ) ，设厶( d ) = ，吃，气) 三( d ) ，l 仨厶( d ) 且g c d ( 气，么，气) = 1 。如果从顶点u 到顶点v 的 长度不小于吒( d ) ( 甜，1 ，) 的每一条途径的长能表为r l ( u w v ) = gr 4 + z 2 气 + + 气_ + 叱( d ) ( 甜， ，) ( 其中 z iz 2 ，乙为非负整数) ，则 e x p o ( u , v ) 2 叱( d ) ( 掰，y ) + 九( d ) 。 由引理2 2 5 容易得到 定理2 2 6 设d 是一本原无环有向图且l ( d ) = r l , r 2 ，r a ) ，如果从u 到v 的长度不小于以( d ) ( ”，v ) 的每一条途径的长能表为r k u w v ) 2z 。+ z 2 r j 2 + + 缸气+ 噍 d ) ( 甜，v ) ( 其中z l ，z 2 ：l o ：l 幺为非负整数) ，则 e x p o ( u ，v ) 2 吮( d ) ( ”，v ) + 丸( d ) 。 2 3 极小强连通有向图 本节给出极小强连通有向图的一些图论性质。 定义2 3 1 ：d = ( y ，e ) 是有向图，若顶点u v 的出度和入度都为1 ，即 d 一似) = d + ( “) = 1 ，称u 为圈点。 定义2 3 2 ： 设d = ( v ，e ) 是有向图中，我们称有向途径 万= ( u 0 ，d i n _ i 甜。) ( m 1 ) 称为一个枝，如果满足： ( 1 ) “o 和u 。不是圈点。 ( 2 ) k = u i 材：，甜册) 中的点都是圈点。 ( 3 ) d z k 】是强连通的。 一个枝可以是闭途径，k 也可以是空集。在一个极小强连通有向图中，一个 枝的长度不能为l ，就是说，极小强连通图中的每一个枝至少包含一个圈点。若 d 是一个有向圈，则它的所有顶点都是圈点，因而d 没有枝。 定义2 3 3 ：设d = ( v ，e ) 是一个有向图，材，1 ，v 我们称d 中甜和1 ，是连 通的，如果存在顶点序列( = “) ，强，甜：，( - ，) ( k 0