（应用数学专业论文）多色有向图的本原指数.pdf

中北大学学位论文 摘要 组合数学又称之为组合论或组合分析，是数学的一个分支。在日常生活中经常会遇到 组合数学的问题，诸如金融分析、投资方案的确定、运筹规划、计算机科学、信息论、控制 论、网络算法和分析等等。图论与非负矩阵理论是组合数学中的两个主要研究内容，这两 个内容有着密切的联系。非负矩阵a 可以与它所对应的伴随有向图d ( a ) 建立一对应关系， 这样就可以利用图论的知识来解决非负矩阵的一些问题。 本文选取了三类具有一定代表性的特殊有向图，2 本原的选取了一类含有三个圈的双 色有向图和一类含有两个双向圈的双色有向图；3 - 本原的选取了一类含有三个圈的三色有 向图。 本文主要内容为： 在第一章中，首先介绍了非负矩阵的相关概念知识。由图与非负矩阵的关系引入了有 向图的本原矩阵与本原指数的相关知识及其在国内外研究概况，提出了本文所做的工作。 在第二章中，考虑一类含有三个圈的双色有向图d ，圈长分别为礼，n 一1 7 ( i l n 一2 。讨 论了d 的各种可能着色情况并列出了其本原情况，文中给出了d 的各种本原情况下的指数上 界。 在第三章中，考虑一类含有两个双向圈的双色有向图d ，由于它是包含两个双向圈，所 以它含有四个圈且均为n 一圈，文中同样给出了d 的各种本原情况下的指数上界。 在第四章中，考虑一类特殊的三色有向图d ，d 中恰含三个圈，圈长分别为n ，9 1 2 和3 。 讨论了各种着色情况下的本原条件，借助逆矩阵找到了d 的指数上界，最后刻划了极图。 关键词：本原矩阵，本原指数，本原图，双色图，三色图，指数上界，极图 第l 页 中北大学学位论文 a b s t r a c t c o m b i n a t o r i a lm a t h e m a t i c si sa l s oc a u e dc o m b i n a t o r i a lt h e o r yo rc o m b i n a t o r i a la n a l y s i s ，i sab r a n c ho fm a t h e m a t i c s i nd a i l yl i f e ，w ea l w a y sm e e tw i t hm a n yq u e s t i o n so fc o m b i - n a t o r i a lm a t h e m a t i c s ，s u c h 出f i n a n c i a la n a l y s i s ，d e t e r m i n a t i o no fi n v e s t m e n tp r o g r a m m e ， l o g i s t i c sp l a n n i n g ，c o m p u t e rs c i e n c e ，i n f o r m a t i o nt h e o r y , c y b e r n e t i c sa sw e l la sn e t w o r ka l - g o r i t h ma n da n a l y s i s g r a p ht h e o r ya n dn o n n e g a t i v em a t r i xt h e o r ya r et w om a i nr e s e a r c h c o n t e n t so fc o m b i n a t o r i a lm a t h e m a t i c s ，t h i st w oc o n t e n t sh a v ec l o s e rr e l a t i o n s h i p n o n n e g a - t i r em a t r i xac a nb u i l dc o r r e s p o n d e n c er e l a t i o n sw i t ht h ec o n c o m i t a n td i r e c t e dg r a p hd ( a ) ， s ow ec a ns o l v es o m en o n n e g a t i v em a t r i xp r o b l e m su s i n gt h ek n o w l e d g eo fg r a p ht h e o r y i nt h i sa r t i c l e ，w es e l e c tt h r e ec l a s s e so fs p e c i a ld i r e c t e dd i g r a p h sw i t hc e r t a i nr e p r e s e n - t a t i o n i no t h e rw o r d ，w es e l e c tac l a s so fp r i m i t i v et w o - c o l o r e dd i g r a p h sw i t ht h r e ec y c l e s a n dac l a s so fp r i m i t i v et w o - c o l o r e dd i g r a p h sw i t ht w od o u b l ed i r e c t i o nc y c l e sf o r2 - p r i m i t i v e ， a n dac l a s so fp r i m i t i v et h r e e - c o l o r e dd i g r a p h sw i t ht h r e ec y c l e sf o r3 - p r i m i t i v e i t sp r i m a r yc o v e r a g ei s ： i nc h a p t e r1 ，f i r s t l y , w ei n t r o d u c et h er e l a t i o n a lc o n c e p t so fn o n u e g a t i v em a t r i x s e c - o n d l y , f r o mt h er e l a t i o no fg r a p ha n dn o n n e g a t i v em a t r i xw ei n t r o d u c es o m ee l e m e n t a r y k n o w l e d g ea n dt h ed o m e s t i ca n df o r e i g nr e s e a r c hs u r v e yo ft h ep r i m i t i v e m a t r i x e sa n dp r i m - i t i v ee x p o n e n t so fd i r e c t e dd i g r a p h l a s t l y , w ep r o p o s eo u rr e s e a r c hp r o b l e m s i nc h a p t e r2 ，w ec o n s i d e rt h es p e c i a lt w o - c o l o r e dd i g r a p h sw i t ht r e ec y c l e sdw h o s e c y c l e - l e n g t h sa l en n 一1a n d 佗一2r e s p e c t i v e l y w ed i s c u s sa l lc o l o r i n gc o n d i t i o n sa n dl i s t i t sp r i m i t i v ec o n d i t i o n s w eg i v et h eu p p e rb o u n d so nt h ee x p o n e n t so fa l lk i n d so fp r i m i t i v e c o n d i t i o n s i nc h a p t e r3 ，w ec o n s i d e rt h es p e c i a lt w o - c o l o r e dd i g r a p h sw i t ht w od o u b l e - d i r e c t i o n c y c l e sd f o ri th a st w od o u b l e - d i r e c t i o nc y c l e s ，i nf a c ti th a sf o u rc y c l e sa n da l l o ft h i s f o u rc y c l e sa l en - c y c l e s a m e l y ，w eg i v et h eu p p e rb o u n d so nt h ee x p o n e n t so fa l lk i n d so f p r i m i t i v ec o n d i t i o n s i nc h a p t e r4 ，w ec o n s i d e rt h es p e c i a lt h r e e - c o l o r e dd i g r a p h sda n di tj u s tc o n s i s t st h r e e 第1 i 页 中北大学学位论文 c y c l e sw h o s ec y c l e - l e n g t h sa r en n 一2a n d3r e s p e c t i v e l y e v e r yp r i m i t i v ec o n d i t i o nu n d e r t h ec o l o r i n gc o n d i t i o ni sd i s c u s s e d w ef i n dau p p e rb o u n do nt h ee x p o n e n tb yt h ei n v e r s e m a t r i x f u r t h e r ，w eg i v et h ec h a r a c t e r i z a t i o n so fe x t r e m a lt h r e e - c o l o r e dd i g r a p h s k e yw o r d s p r i m i t i v em a t r i x ，e x p o n e n t ，p r i m i t i v ed i g r a p h ，t w o - c o l o r e dd i - g r a p h ，t h r e e - c o l o r e dd i g r a p h ，u p p e rb o u n d ，e x t r e m a ld i g r a p h 第l n 页 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行 研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名： 压3 金逾 日期： 徊弓、s 、九 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包括：学校 有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、 缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借 阅；学校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学 位论文的全部或部分内容( 保密学位论文在解密后遵守此规定) 。 签名：圈塑日期： 导师签名： 力弦鼾3 乃 中北大学学位论文 第一章引言 1 1非负矩阵 1 1 1 非负矩阵的本原性 非负矩阵组合理论是组合矩阵论中一个研究方向，当我们研究非负矩阵的组合性质的 时候，我们可以把一个非负矩阵转化为一个 o ，1 ) 非负矩阵来研究，许多与非负矩阵相关的 概念很自然地在研究有限马尔可夫链中提出了，如在文献【1 】中考虑了有限马尔可夫链，从 而提出了n 阶非负矩阵的本原指数的概念： z 七= a z 七一l ( 七1 ) ， 其中a 是n 阶非负矩阵且初值z o 是非零非负向量。对所有充分大的k ，使得x 七0 ，满足这样 的条件就可以区分马尔可夫链。易证当且仅当存在一个正整数z 使得a 0 ，则对每个非零 非负向量初值x o 都存在一个k 使得对所有k k 都有x 七0 。 这就引入了非负方阵a 本原及其本原指数的定义：设a 是礼阶非负矩阵，如果存在一个 正整数k ，使a 七 0 ，则称a 为非负本原矩阵。非负本原矩阵a 的本原指数是指使a 七 0 的 最小整数k ，记为，y ( a ) 或e x p ( a ) ，看下面这样一个例子： 设方阵a = a 2 = 11 0 0 o 0 11 11 ol 0 0 00 11 o1 0o ，则： ，a s = 2 2 2 2 11 12 11 11 ，a 4 = 44 3 3 2 2 23 2 3 11 显然a 3 中的每个元素都大于零，a 4 中的每个元素也都大于零且易知a 七 0 ，k 3 ，所 以非负矩阵a 是本原的，- 目- 7 ( a ) = 3 。这就是非负矩阵的本原性的相关概念，对于非负矩阵 对及非负矩阵簇可作类似推广。 第1 页 中北大学学位论文 1 1 2 非负矩阵的推广一非负矩阵对及非负矩阵簇 在文献【2 】中考虑了【3 】中2 维离散动力系统，从而提出了椰介非负本原矩阵对的本原指数 的概念： x ( h + 1 ，k + 1 ) = 血( ，k + 1 ) + b x ( h + 1 ，后) ，h ，k z ，h + k 0 ，( 1 2 2 1 ) 其c a 和b 是n 阶非负矩阵，初始条件x ( h ，一h ) ( 九z ) 是n 维非负向量。对非负整数h 和七，定 义a 和b 的( ，k ) 一h u r w i t z 乘积为所有h 个a 和k 个b 的乘积之和，记为( a ，b ) ( ，七) j 例如： ( a ，b ) 1 ，o ) = a ， ( a ，b ) ( 2 ，2 ) = a 2 8 2 + a b a b + a b 2 a + b a 2 b + b a b a + b 2 a 2 。 非负矩阵对( a ，b ) ( a 和b 均是非零的等阶方阵) 是本原的当且仅当( 1 2 2 1 ) 式的解是始终严 格正的【4 】。 这就提出了非负矩阵对似，j e i ) 本原及其本原指数的定义：如果存在非负整数h 和k ，使得 对h + 七 0 ，有( a ，b ) ( h ，k ) 0 ，则称非负矩阵对( a ，b ) 是本原的，并且将h + k 的最小值定 义为非负本原矩阵对( a ，b ) 的本原指数，记为e x p ( a ，b ) 。 对于非负矩阵，如果有a 七0 ，则对所有的z k ，都有a 0 。但对于非负矩阵对则不 存在这样的结论，如： a = o0o l0o 1oo 通过计算可知： ( a ，b ) 4 ，6 = ，b = 614 13 3 o0l 0 0 0 o10 ，( a ，b ) 4 ，7 = 446 o31 44 6ii164 显然( a ，j e i ) 4 ，620 ，而( a ，b ) 4 , 7 并不是严格正的，所以对于非负矩阵对本原指数的确定 比较复杂，这是一个新的概念也是一个更加复杂的研究方向。 礼阶非负本原矩阵簇的本原指数提出背景【5 】： 类似于2 维离散动力系统，可以将一个扎阶k 簇矩阵a = ( a 1 ，a 2 ，a k ) 考虑为七维离散 动力系统x ( i l ，i 2 ，i k ) ( i l ，i 2 ，砍e z 且t l + i 2 + + i k 0 ) 。该系统由初始条件 z ( f i ，f 2 ，i 七) ( 1 + i 2 + + i k 0 ) 第2 页 中北大学学位论文 秘递归公式 x ( h + 1 ，t 2 + 1 ，如+ 1 ) = a l x ( i l ，i 2 + 1 ，i k + 1 ) + a 2 x ( i l + 1 ，i 2 ，i 3 + l ，i k + 1 ) + + a k x ( i l + 1 ，i 2 + l ，如) 所控制，其中x ( i l ，i 2 ，如) 是n 维非负向量。 设a 一( a 1 ，a 2 ，氐) 为豫阶菲负矩阵簇，a = ( o r l ，0 ：2 ，8 蠹) 是k 维菲受整数组，众表 示所有a 1 个a l 、q 2 个岛、& 蠢个蠢蠢乘积之和。例如： 蔗1 如，1 ) = 矗l 如。 这就提出了非负矩阵簇似，曾) 本原及其本原指数的定义：如果存在庇维菲负整数组a ，使 得a 囊 0 ，则a 是本原豹。在所有满足 o 的非负整数组8 中，穰l + q 2 + + & 纛的最，l 、 值定义为非负本原矩阵簇a 的本原指数。 非负本原矩阵簇即是非负本原矩阵对的推广形式。 1 2图与菲负矩阵 1 2 1 单色图与非负矩阵 非负矩阵组合理论与图的某些性质有密切联系，图的本原性以及本原指数与非负矩阵 的本原以及本原指数是有密切关系的。妃阶j 负矩阵a h i ) 和霭阶有南图d 之闯存在一种 一一对应关系。有向图d 称为非负矩阵五的伴随有向图，记为d ( a ) ，a 为。的邻接矩阵。非 负矩阵和伴随有向图建立了一对应关系后，即可从非负矩阵a 一池，) 中元素的数值来判 断d ( a ) 中是否存在一条对应弧；同样可从d ( a ) 中各条途径的弧来判断a = ( ) 中元素的数 值。 例如：a 1 2 o 表示从顶点l 到顶点2 有一条弧；a 1 2 0 表示从顶点l 到顶点2 没有弧；a l l 0 表示从顶点1 到顶点1 有一条弧，即顶点1 有环。下面我们看一个具体的例子： 设方阵a ll o 0 oo 11 oo 重量 0l 0 0 第3 页 中北大学学位论文 此时非负方阵a 所对应的伴随有向图d ( a ) 为 若a 是非负本原方阵，则d ( a ) 称为本原有向图。换言之，有向图j d 称为本原的，如果d 的 邻接矩阵a 是本原的，a 的本原指数即为d 的本原指数，根据非负矩阵本原性及其本原指数 的定义，可将有向图d 本原性及本原指数的概念定义为： 一个有向图d 是本原的，当且仅当存在非负整数k ，且k 0 ，使得d 中的每一对顶 点( 1 ，歹) 都存在从i 至1 j 的( 七) 一途径，七的最小值定义为有向图d 的本原指数，记为e x p ( d ) 。( 尼) 一 途径是指从涯归的途径中包含k 蓝弧。 这样对于( 0 ，1 ) 非负方阵a 的本原性及其本原指数的研究就可以转化为研究有向图d ( a ) 的 本原性及其本原指数这样一个等价的图论问题了。 1 2 2双色图与非负矩阵对 亿阶非负矩阵对与双色有向图的一一对应关系： 设d 是一个有向图，d 的一条长为l 的途径是指连续的顶点序列 1 ，v 2 ，铆+ l ，其中对 所有的i = 1 ，2 ，l ，d 中都有从仇到仇+ 1 的弧。如果秽1 ，也，v z + l 互不相同，则称该途径 是一条长为f 的路。如果v l = 铆+ 1 ，则称为一条闭路或圈【6 】。如果d 是包含红弧和蓝弧的有向 图，则称d 是一个双色有向图。 如果d 中每一对顶点( i ，歹) 都存在一条从i 到j 的途径，则双色有向图d 是强连通的。假 设d 中一条途径为u ，可用r ) 和6 ) 分别表示u 中红弧和蓝弧的条数，这样即可称u 为一 r，、1 条( r ) ，6 ) ) 一途径，“，的分解为向量( r ) ，6 p ) ) 或lr ：u ? i 。 【6 ( u ) j 。 与非负矩阵与其伴随有向图的对应关系类似，对任意一对非负矩阵对似，b ) 同样与其伴 随有向图存在一一对应关系，其伴随有向图记为d ( a ，b ) ，显然d ( a ，b ) 具有顶点1 ，2 ，n 。 非负矩阵对与其伴随有向图建立了对应关系后，即可从非负矩阵对( a ，b ) 中元素的数值来 判断其伴随有向图d ( a ，b ) 中对应弧存在与否。如：从矩阵a = ( a o ) 中元素的数值可判 断d ( a ，b ) 中是否存在对应的红弧，如果啦， 0 ，则从顶点i 到顶点j 存在一条红弧；同样 从矩阵b = ( 玩j ) 中元素的数值可判断d ( a ，b ) 中是否存在对应的蓝弧，如果玩， 0 ，则从项 第4 页 中北大学学位论文 点i 到顶点j 存在一条蓝弧。 如果双色有向图对应的非负矩阵对( a ，b ) 是本原的，则称双色有向图d ( a ，b ) 是本原的， j t d ( a ，b ) 的本原指数e x p ( d ( a ，b ) ) 即为( a ，b ) 的本j 燃e x p ( a ，b ) 。由非负矩阵对的本原性 及其本原指数的概念，可将双色有向图的本原性及其本原指数的概念定义为： 一个双色有向图d 是本原的，当且仅当存在非负整数h 和k ，且h + k 0 ，使得d 中的每 一对顶点( 1 ，歹) 都存在从涯归的( ，七) 一途径，h + 尼的最小值定义为双色有向图d 的本原指数， 记为e x p ( d ) 。( h ，尼) 一途径是指从i 到歹的途径中包含h 条红弧和k 条蓝弧。 另外，设c = 7 1 ，7 2 ，饥) 是d 的圈集合，定义d 的圈矩阵为： r1 m ：10 1 眈啦_ 1 铆l ， 1 b lb 2 b z lb t l 其中啦，兢( 1 i c ) 表示圈竹中的红弧和蓝弧的数目。m 是一个2 f 矩阵，它的第 列是m 的分 解。m 的c o n t e n t ( 记为c o n t e n t ( m ) ) 定义为0 如果m 的秩小于2 ，否则定义为m 的所有非零2 阶 主子式的最大公因数。 非负矩阵对与其伴随有向图之间存在这样一种对应关系，可以通过研究双色有向图的 本原性及本原指数等问题来解决非负矩阵对的相关问题。 1 2 3 多色图与非负矩阵簇 一个k 着色图g 是指一个k 维分支子图( g l ，g 2 ，g 七) ，使得g 1 ，g 2 ，g 知将g 的弧分 为k 个非空子集。g t 表示在g 中所有着第i 种颜色的弧数。 类似于g 是本原的观点，可以说k 着色( g 1 ，g 2 ，g 七) 是“本原的，如果存在一组肛维 正整数r l ，r 2 ，仇使得g 中的任意顶点对( t | ， ) ，存在一条从u n v 的途径，该途径中恰好包 含g 中的n 条弧，其中i = 1 ，2 ，k 。 矩阵理论中已经有了判断一个着k 种颜色的特殊图是否k 本原。假设一个有向图g 是由k - 着色的( g 1 ，g 2 ，g 七) 组成的，g 中的圈用c l ，c 2 ，e l 表示，从而建立尼xz 矩阵m = 【m 巧】， 则g 的圈矩阵定义为： m = = r o l l 7 n 2 1 r n k l m 1 2 m r 2 2 i n k 2 m l ( z 一1 、m l l m 2 ( t 一1 ) ? t 1 2 1 m 七( f 1 ) k u 第5 页 中北大学学位论文 其中仇巧( 1 i 尼，1 j f ) 表示圈勺中着第i 种颜色的弧数。 m 的c o n t e n t ( 记为c o n t e n t ( m ) ) 定义为o ，如果m 的秩小于七，否则定义为m 的所有非零k 阶 主了式的最大公因数。 显然，七= 1 时，非负矩阵簇的本原概念即为非负本原矩阵的概念；尼= 2 时，非负矩阵 簇的本原概念即为非负本原矩阵对的概念。 因此，非负本原矩阵簇是非负本原矩阵对或是非负本原矩阵的推广，在文献【5 】中已经 得到了非负本原矩阵簇本原的判断定理； 令g 是个本原有向图且( g l ，g 2 ，g 七) 是g 的七一着色，那么g 是k 本原的当且仅当非 负矩阵m 的k k 阶子式是互素的。 1 3图的本原指数在国内外的研究成果 1 3 1 国外研究情况 关于非负本原矩阵a 的本原指数的研究最早始于1 9 5 0 年w i e l a n d t 的工作【7 】，w i e l a n d t 所 研究的图如图1 3 1 所示： - _ _ _ _ _ - _ 一_ _ _ _ _ - _ _ _ _ - 图1 3 1w i e l a n d t 图 w i e l a n d t 给出了礼阶本原指数的一般性上界e x p ( a ) 一1 ) 2 + 1 。随着对本原指数的 继续研究得到了一些重要的成果，在1 9 6 4 年，d u l m a g e 和m e n d e l s o h n 结合图论知识，推导出 了n 阶本原指数的一般性上界的一4 种形式：e x p ( a ) n + s ( n 一2 ) ，其中s 是a 的伴随有向 图d ( a ) 的最小圈长。另外在文献 6 】中关于e x p ( a ) 的研究也取得了一定的成果。 这些结论对于图论方面的研究具有重要的指导意义。 目前对双色本原有向图( 非负本原矩阵对) 的研究只得到了一些初步的结果。 在文献【2 】中，有关双色有向图的研究得到了如下一些重要结论： 第6 页 中北大学学位论文 定理1 3 1 2 】设( a ，b ) 是n 阶非负矩阵对，且a ，b 均是非零矩阵，m 是( a ，b ) 的伴随有向 m d ( a ，b ) 的圈矩阵，则下列结论是等价的： ( 1 ) ( a ，b ) 是本原的。 ( 2 ) d ( a ，b ) 是强联通的，且c o n t e n t ( m ) = 1 。 ( 3 ) d ( a ，b ) 是强联通的，且 = z 2 ， m z ：z z 。) = z 2 。 定理1 3 2 【2 】设d 是本原双色w i e l a n d t 有向图，如图1 3 1 所示，n 3 ，且d 至少包含一条 红弧和一条蓝弧，则2 舻一4 n + l e x p ( d ) 2 n 2 3 n + 1 。 定理1 3 3 【2 】设( a ，b ) 是n 阶非负矩阵对，礼5 ，则非负矩阵对( a ，b ) 的本原指数的最大 值为 0 。 图1 3 2d 的未着色图 在文献【1 0 l 中考虑了t 一1 的情形，此时所对应的圈矩阵为 m = n ：l ，他：2 ， 文中找到了指数上界并刻划了终呻1 _ 2 _ _ 8 _ ( 8 + 1 ) _ ( 8 + 2 ) 巾包含条蓝 弧的指数集，得到以下主要结论： 第8 页 定理1 3 8f l o 若双色有向图d 是本原的，且n 一1 2 _ 一s _ ( 8 + 1 ) _ ( 8 + 2 ) 中 包含一条蓝弧，则2 n 2 3 n + 1 e x p ( d ) 2 n 2 2 n + 2 s n s 。 定理1 - 3 9 【1 0 】若双色有向图d 是本原的，h _ n _ 1 _ 2 _ _ 8 _ ( s + 1 ) _ ( s + 2 ) 中 不包含蓝弧，贝l j e x p ( d ) = 2 n 2 4 礼+ 1 。 定理1 3 1 0 【1 0 】若双色有向图d 是本原的，8 = o r n 一1 _ 2 _ _ 8 _ ( 8 + 1 ) 一 ( 8 + 2 ) 中包含一条蓝弧，贝, l j e x p ( d ) = 2 n 2 3 n + 1 ，此时双色有向图d 为w i e l a i l d t 图。 定理1 3 1 1 【1 0 】若双色有向图d 是本原的，8 1 r n 一1 2 _ _ s _ ( s + 1 ) _ ( s + 2 ) 中包含。一条蓝弧，则d 的指数集是 2 n 2 + 2 ( 七一1 ) n 一七i 七= 0 ，1 ，s ) u 1 【2 礼2 - 3 n + l 。 在文献 1 1 1 中考虑t t = 2 的情形，此时所对应的圈矩阵为： m ：l 叶1口l ， i qq 一1l 其中n s + 4 ，n = 2 q + 1 。找到了指数上界并刻划了极图，得到以下主要结论： 定理1 3 1 2 【1 1 】若双色有向图d 是本原的，则 ，l n s - 2 2 n s t l ， ( s _ 一q - “z ) 2 n 2 6 佗+ 2 e x p ( d ) ( s 3 ) 凡：一( 3 s + 8 ) n + s + 3 ，：9 g 一1 ；。 定理1 3 1 3 【1 1 】若双色有向图d 是本原的，贝, l j e x p ( d ) = 2 n 2 一饥+ 2 当且仅当d 中存在一 条2 长的红路。 定理1 3 1 4 【1 1 】若双色有向图d 是本原的，r s q 一2 ，贝l j e x p ( d ) = 生= 呈2 吐丝当且仅当n 圈 上存在一条g + 1 长的红路。 定理1 3 1 5 【1 1 】若双色有向图d 是本原的，r s q 一1 ，贝l | e x p ( d ) ) = ( s + 3 ) n 2 一( 3 s + 8 ) n + 8 + 3 当且仅当d 中存在一条s + 3 长的红路，且所有红弧不间断。 在文献f 1 2 1 中对以下图1 3 3 进行了讨论，得到了以下重要结论， 图1 3 3 中由两个双向礼( 几23 ) 圈构成的双色有向图d ，且d 至少有一条蓝弧和一条红 第9 页 中北犬学学位论文 弧。 ：兰言n aan 二6 ， 敝一 i 蚓12 _ 】， 王1 兰嚣二8 嚣二蠢 ， ：兰言魏二8 嚣二6 ：l ：口叶1l ，贝, l j e x p ( d ) 3 ，那么 ( 1 ) 如果n 5 ，女l l j e x p ( d ) 2 ( 口2 + 口) = 学，且等号可以成立。 ( 2 ) 如果n = 3 ，贝l j e x p ( d ) 5 ，且等号可以成立。 1 3 3图的主要研究问题及有待于进一步探讨的问题 ( 1 ) 继续寻找非负矩阵的本原条件； ( 2 ) 影响非负本原矩阵对( 簇) 本原指数大小的关键因素； ( 3 ) 找出本原指数的一般上界，并研究其极图刻划； ( 4 ) 探索研究非负矩阵的本原指数的一些性质在非负本原矩阵对( 簇) 的本原指数中的 推广； ( 5 ) 对一些特殊双色图或三色图的研究，找到其指数的范围，并对达到指数的上、下界 的极图进行刻划。 第1 1 页 中北大学学位论文 l 。4 本文主要的工作 本文主要内容为： 在第一章中，首先介缨了鼍# 负矩阵的相关概念知识，由图与鼍# 负矩阵的关系引入了有 向图本原及其本原指数的相关概念以及在国内外研究概况，提出本文所做的工作。 在第二章中，考虑一类含有三个圈的双色有向图d ，圈长分别为n ，l l 和他一2 。讨 论了d 的各种可能着色情况并列出了箕本原情况，文中给出了移的各种本原情况下的指数上 界。 在第三章中，主要考虑一类含有两个双向圈的双色有向图d ，由于它是包含两个双向 圈，所以它含有四个圈且均为r , 一圈，文中同样给出了各种本原情况下的指数上界。 在第四章中，主要考虑一类特殊盼三色有向圈d ，p 中恰含三个圈，圈长分别为髓，协一 2 ) 秘3 。谖明了本原条件，找到了刀的指数上界，最后借助逆矩阵刻划了极图。 在结束语中，概括了本文研究的问题，以及有待于继续探讨的问题。 第1 2 页 中北大学学位论文 第二章一类含有三个圈的双色有向图的本原指数的上界 2 1 弓l 言 一个双色有向图是一令所有弧都着蓝色或红色的有向图。双色有向图允许有舔且从i 到j 可以同时有一条蓝弧和一条红弧。双色有向图d 是强连通的，如果对任意的顶点对( ，歹) 在d 中 存在一条从i 到歹的途径。d 中从i 至：u j 的条( ，k ) - 途径是指从i 至归的一条包含h 条红弧和后条 蓝弧的途径。给定d 中的一条途径u ，用r ) 和6 0 ) 分别表示红弧和蓝弧的条数，定义u 的分 解为向量l l 。 l6 ( ) i 双色有向图d 是本原的，当且仅当存在菲负整数h 和k ，且h + 凳 0 ，使得d 中的每一 对顶点( ，歹) 都存在从i n j 的( 磊，k ) - 途径，h 蠢的最小值定义为双色有囱图d 的本原指数，记 为e x p ( d ) 。 设d 是一个双色有向图且c = 饥，讹，j 一，m ) 是d 的圈集合，m 是一个2 z 矩阵，它的 第i 判是3 i 的分解，且膨是由m 中所有不同捌组成的矩阵，称膨是p 的圈矩阵且是d 的严 格瀚矩阵。m 鹃c o n t e n t ( 记为c o n t e n t ( m ) ) 定义为0 。如果掰的秩小于2 ，否则定义为掰的所 有非零2 阶主子式的最大公因子。 引理1 1 【2 】设d 是一个n 阶双色有向图，m 是d 的圈矩阵，则d 是本原的当且仪当d 强连通 且c o n t e n t ( m ) 拦1 。 双色有向图指数的概念在研究有限m a r k o v 链时就缀自然地被提出( 冕 1 2 1 1 1 1 ) 且在瞬 4 1 潮 矧中已经 ! 导出一些结果。 第1 3 页 中北大学学位论文 2 。2特殊图及其着色情况 本章将考虑一类含有三个圈的挖阶双色有向图，记作玖，其未着色图如图2 。2 所示。 一l 2 图2 2 双色有向图d 。的未着色图 由图2 。2 可知，显然对任意d 坟，d 有一个摊一圈，一个如一1 ) 一圈和一个加一2 ) 一圈， 注意到弧( n 一1 ) 一扎，死_ 1 ，l _ 2 中，至少有两条弧具有相同颜色。不失一般性，假设这 三条弧中至少有两条红弧，于是风中的双色有向图有以下1 6 种可能，如表格2 2 所示。 第1 4 页 中北大学学位论文 表格2 2 ( n 一1 ) 一1 n 一1 2 ( n 一1 ) 一佗 佗叫11 叫2 情况1红红红红红 情况2蓝红红 红 红 情况3 红 蓝 红红红 情况4蓝蓝 红红红 情况5 红红蓝红红 情况6 蓝红蓝红红 情况7 红 蓝蓝红 红 情况8蓝蓝蓝红红 情况9 红红红 蓝 红 情况1 0蓝 红红蓝红 情况1 1红蓝红蓝红 情况1 2蓝蓝 红 蓝 红 情况1 3 红红红红蓝 情况1 4蓝红红红蓝 情况1 5 红 蓝红红蓝 情况1 6 蓝蓝红红蓝 且伪的分解是m 的第i 列，l = 1 ，2 ，3 。 2 3双色有向图的本原性 显然，若d 队，则d 是强连通的。假设在路径2 _ 3 _ _ ( 礼一2 ) _ ( n 一1 ) 中 有a 条红弧及( 礼一a 一3 ) 条蓝弧，其中0sa n 一3 。 对于情况1 ，d 的圈矩阵为m ：i n + 3n + 2口+ 1 i 。 【n o 一3 n 一口一3n o 一3 j 于是c o n t e n t ( m ) = g c d n a 一3 ，n a 一3 = n a 一3 ，因此d 是本原的当且仅 当佗一a 一3 ：1 ，即o = 礼一4 。 第1 5 页 中北大学学位论文 对于情况2 ，d 的圈矩阵为m ：l 口+ 3 n + 1口+ 1 i 。 对于情况， 的圈矩阵为 = li 。 于是n t e n t ( m ) ：g c d 2 ( n a l - 3 ) ，2 ( 佗一n 一3 ) + 口+ 3 ，一( 口+ 1 j ) = 2 n o 一4 ，因 此d 本原当且仅当。为偶数。 r1 对于情况3 ，d 的圈矩阵为m ：l 口+ 3n + 2 。 i 。 对于情况， 的圈矩阵为 = il 。 于是c d n t e 礼( m ) ：9 c d ( n o 二3 ，3 ( 扎一口一3 ) + 口+ 3 ，2 ( n n 一弓) + n + 2 ) = 1 ，因 此d 是本原的。 广1 对于情况4 ，d 的圈矩阵为m ：i a + 3 1 口+ 1 口 i 。 对于情况，的圈矩阵为= l i 。 i 佗一n 一3n a 一2 钆一口一2l f 是c o n t e n t ( m ) = g c d 2 ( n q 一3 ) + o + 3 ，3 ( n n 一3 ) + a + 3 ，n a 一3 + 1 ) 21 ， 因此d 是本原的。 对于情况5 ( 由于情况9 和情况1 3 的圈矩阵和情况5 完全相同，可以统一为情况5 ) ，d 的圈 矩阵为m ：l 叶2 0 + 28 + 1 i 。 于是c 饥乞吼( m ) ：夕c d 一( 口+ 2 ) ，n 一口一之一( 口+ 2 ) ，佗一口一3 ) = 1 ，因此d 是本原 的。 对于情况6 ( 情况1 0 和情况1 4 的圈矩阵和情况6 完全相同，可以统一为情况6 ) ，d 的圈矩 阵为m ：1 0 + 20 + 1卅1 i 。 于是c 品e 位( m ) ：夕c d n 一口一2 ，n n 二2 一( 口+ 2 ) ，一口一1 ) = 1 ，因此d 是本原的。 对于情况7 ( 情况1 1 和情况1 5 的圈矩阵和情况7 完全相同，可以统一为情况7 ) ，d 的圈矩 阵为m ：1 0 + 2卅2 口 i 。 于是c 品e 耐( m ) ：9 c 烈一口一2 ，2 ( n n = - 2 ) ，2 ( n n 一2 ) + o ) ，因此d 是本原的当且 仅当。为奇数。 对于情况8 ( 情况1 2 和情况1 6 的圈矩阵和情况8 完全相同，可以统一为情况8 ) d 的圈矩阵 为m ：l 口+ 2 卅1 口 l 。 l n a 一2n a 一2n a 一2l 于窟葫e n t ( m ) ：夕c 烈他一d 一2 ，2 ( 丢。一2 ) ，佗一口一2 ) = 礼一。一2 ，因此d 是本原 的当目仅当n a 一2 = i ，即。兰n 一3 。 第1 6 页 中北大学学位论文 综合以上讨论，可以得出双色有向图d d n 有八种本原的情况，即有八个本原矩阵， 以下将对八种本原情况分别按上面的顺序进行讨论其本原指数的上界。 2 4本原指数的上界 引理4 1 如果d d n 是本原的，且d 是情况1 ，那么e x p ( d ) 2 ( n 一1 ) 2 。 证明：因为d 的圈矩阵为m ：l 礼一1 n 一2 亿一3 i 。 l 111 j 对于d 中的任意顶点对( f ，j ) ，下面证明在d 中有一条从i 到歹的( 2 n 2 6 n + 4 ，2 n 一2 ) - 途 径。设砌是从z 到j 的最短途径，记r = r 嘛) 以及b = 6 ) ，则o b 1 ，0 r n 一1 。于 是从顶点z 出发沿到顶点j i ，绕7 1 圈( n 一2 ) 6 次，绕7 2 匿 2 n 一2 一r 一( n 一1 ) 6 次，绕7 3 圈r 次， 其途径分解为： ： + c 几一2 ，6 死：1 + ( 2 n - 2 - r - ( n - 1 ) b ) 礼：2 小3h2 礼2 2 - ：4 因此，e x p ( d ) 2 ( n 一1 ) 2 ，证毕。 引理4 2 如果d d n 是本原的，且d 是情况2 ，那么e x p 证明：因为。的圈矩阵为m = 扎二：二3 n 二：二2 其中0 a m 一3 ，且。为偶数。 ( d ) 佗 n