（应用数学专业论文）矩阵对的本原指数及矩阵运算的图操作.pdf

中北大学学位论文 摘要 非负矩阵组合理论是研究那些仅依赖于矩阵的零位模式，而与矩阵元素本身数值大小 无关的性质，它与图的一些性质有密切联系，在信息科学，通信网络，计算机科学等许多学 科中都有具体的应用。 本原矩阵的本原指数及广义本原指数是非负矩阵组合理论的重要研究内容，到目前为止， 许多问题已得到解决。而在新的背景下，对非负矩阵对的本原指数的研究应运而生。事实 上，非负矩阵对可以与一个双色有向图建立一一对应关系，这样就可以把矩阵的问题转化 为图的问题进行研究。本文主要研究了一类特殊双色有向图，主要内容为： 第一章概述了图论和非负矩阵组合理论这两门学科的发展及研究内容，并介绍了一些 基本概念以及本原指数的国内外研究概况，提出本文所做的工作。 第二章研究一类特殊双色双圈有向图，其基础有向图包含一个( ( t 一1 ) m + 1 ) 一圈和( 加+ 1 1 一圈。应用组合矩阵论和图论的方法得到这类图本原的条件和指数的界。最后得到本原指 数集并对达到指数上下界的极图进行刻划。 第三章研究一种利用n 阶方阵及其所确定的赋权有向图的关系解决矩阵运算的方法，使 其应用在第二章的计算当中。 关键词：本原指数，双色有向图，极图，本原指数集，赋权有向图 第1 页 中北大学学位论文 a b s t r a c t t h ec o m b i n a t i o n a lt h e o r yo fn o n n e g a t i v em a t r i xr e s e a r c h e st h eq u a l i t i e st h a td e p e n d o nt h ep a t t e r no fm a t r i xa n dt ob eu n c o n c e r n e dw i t ht h ev a l u eo fm a t r i xe l e m e n t i t h a s c l o s er e l a t i o nw i t hs o m eq u a l i t yo fg r a p h ，a n dh a sr e l a t i v e l ya p p l i c a t i o ni nm a n y a r e a ss u c h 鹪i n f o r m a t i o ns c i e n c e ，c o m m u n i c a t i o nn e t w o r k s ，c o m p u t e rs c i e n c e p r i m i t i v ee x p o n e n ta n dg e n e r a l i z e dp r i m i t i v ee x p o n e n to fp r i m i t i v em a t r i c e sa r ei m - p o r t a i l tr e 8 e a r c hc o n t e n ti nt h ec o m b i n a t i o n a lt h e o r yo fn o n n e g a t i v em a t r i x s of a r ，m a n y p r o b l e m sh a v eb e e nr e s o l v e d i nt h en e wc o n t e x t ，t h er e s e a r c hf o rp r i m i t i v ee x p o n e n to f n o n n e g a i t i v em a t r i xp a i r sc s 舶f l ei n t ob e i n g i nf a c t ，t h e r ei sao n e - t o - o n er e l a t i o n s h i pb e t w e e n n a n n e g a t i v em a t r i xp a i r sa n dt w o - c o l o r e dd i g r a p h ，s ot h ep r o b l e mo fm a t r i c e sc a nt r a n s f o r m i i l t ot h ep r o b l e mo fg r a p h i c st os o l v e t h i sp a p e rs t u d i e so n ec l a s s e so fs p e c i a lt w o - c o l o r e d d i g r a p h ，t h em a i nc o n t e n t sa sf o l l o w s ： i n 出a p t e r1 ，f i r s t l yt h ed e v e l o p m e n ta n dc o n t e n to ng r a p ht h e o r ya n d c o m b i n a t i o n a l t h e o r yo fn o n n e g a t i v em a t r i xa r ed e s c r i b e dr o u g h l y t h e n ，s o m ee l e m e n t a r yc o n c e p t sa n d t 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 ee x p o n e n t so fd i r e c t e dd i g r a p h a r e i n t r o d u c e d l a s t l y , o u rr e s e a r c hp r o b l e m sa r ep r o p o s e d i nc h a p t e r2 ，as p e c i a lt w o - c o l o r e dd i g r a p hw i t ht w oc y c l e si sc o n s i d e r e d ，w h o s eu n c o l o r e d d j g ，a p hc o n s i s t so fo n e ( ( t 一1 ) m + 1 ) 一c y c l ea n do n e ( t i n + 1 ) 一c y c l e u s i n gt h em e t h o do f c o m b i n a 七o r i a lm a t r i xt h e o r ya n dg r a p ht h e o r y , t h ep r i m i t i v i t yc o n d i t i o n sa n dt h eb o u n d o n t h ee x p o n e n ta r eg i v e n f u r t h e r ，t h ee x p o n e n ts e ti so b t a i n e da n dt h ee x t r e m a ld i g r a p h st h a t m e e tt h eu p p e rb o u n da n dt h el o w e rb o u n da r ec h a r a c t e r i z e d i nc h a p t e r3 ) u s et h ec o n n e c t i o no fn s q u a r em a t r i xa n d i t sw e i g h t e dd i g r a p h ，p u tf o r w a r d ag r a p h i c a lm e t h o dt os o l v et h eo p e r a t i o no fm a t r i x ，a n du s et h i sm e t h o di nc h a p t e r2 k e y w o r d s ：p r i m i t i v ee x p o n e n t ，t w o - c o l o r e dd i g r a p h ，e x t r e m a ld i g r a p h ，t h e s e to fp r i m i t i v ee x p o n e n t ，w e i g h t e dd i g r a p h 第1 i 页 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教! j 币的指导下，独立进行 研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：三苣三! 一日期：工塑导g 止 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包括：学校 有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、 缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借 阅；学校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学 位论文的全部或部分内容( 保密学位论文在解密后遵守此规定) 。 签 翮签名：笄铅融二一 眺埤：篁：2 1 日期：趔：堇：垄2 中北大学学位论文 第一章引言弟一早jii 1 - 1图论与非负矩阵理论 组合数学是计算机出现以后迅速发展起来的一门数学分支。现代数学可以分为两大类： 一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的，如组合数学等。组 合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如 在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。 图论是组合数学中的一个重要分支，到现在大概只有二百多年的历史。图论开始的大 多数问题起源于游戏，最有代表性的工作是著名的瑞士数学家欧拉于1 7 3 6 年发表的哥尼斯 堡七桥问题。他的那篇论文被公认为图论历史上第一篇论文。1 8 4 7 年，基尔霍夫研究电网 络发现了图论新的应用提出了树的概念，它可以用来解决优化中的最小连接问题。1 8 5 7 年， 凯莱在有机化学领域里发现了树并研究了树的计数问题。1 8 5 9 年，哈密顿发现了与图有关 的难题，成为哈密顿问题，它可以用来解决旅行售货员问题。另外，工作分配问题，邮路问 题，最优路线问题等都可以用图论的方法解决。1 8 7 8 年，“图 这个词第一次出现在的英国 0 。使a 七 0 成立的最小七称为月的本原 指数，记为，y ( a ) 或e x p ( a ) 。 由于本原方阵的本原性及其本原指数只与方阵的零元素位置分布有关，而与非零元素 的具体数值无关。所以可以假设所有非零元素均为1 ，即所谓的( o ，1 ) 或布尔方阵。下面我们 看两个具体的例子： 设方阵 a = 11 0 0 0 0 11 0 0 l1 01 0 0 第2 页 中北大学学位论文 则 = 11 ll 11 11 所以矩阵a 是本原的，r t ( a ) = 3 。 设方阵 则 b 2 ： 11 0l 0 0 l1 b= 0 01 10 0 010 ，a 3 ： 010 o 01 10 0 ，b 3 ： l1 l1 l1 l1 0lo 0 01 10 0 11 11 11 ll = b 。 显然不存在正整数k 使得b k 0 ，所以b 是不本原的。 矩阵a 可以与它所对应的伴随有向图d ( a ) 建立一一对应关系，即矩阵a = ( ) 中元素 值非零或零对应于d 中有没有弧。例如：a 1 2 0 表示从顶点u l 到顶点现有一条弧；a 1 2 = 0 表 示从顶点v 。到顶点? 3 2 没有弧；a 1 1 0 表示从顶点v l 到顶点v 1 有一条弧，即顶点v l 有环。利用 这种对应关系，则上例中方阵a 所对应的伴随有向图d ( a ) 如图1 2 1 所示。 图1 2 1 方阵b 所对应的伴随有向图d ( b ) 如图1 2 2 所示。 图1 2 2 第3 页 中北大学学位论文 若a 是本原方阵，贝i j d ( a ) 称为本原有向图，a 称为j 7 ) ( 月) 的邻接矩阵。换言之，有向图d 称 为本原的，如果d 的邻接矩阵4 是本原的。对于( o ，1 ) 方阵a 的本原性及其本原指数的研究就 可以转化为研究有向图d ( a 1 的本原性及其本原指数这样一个等价的图论问题了。 1 2 2本原矩阵对及双色本原有向图 n 阶本原矩阵对的本原指数提出于如下背景 1 6 1 ： 考虑2 维离散动力系统 x ( h + 1 ，k + 1 ) = a x ( h ，k + 1 ) + b x ( h + 1 ，七) ，h ，k z ，h + k 0 。 ( 1 2 2 1 ) 其中a 和b 是n 阶非负矩阵，初始条件x ( h ，一九) ( z ) 是n 维非负向量。对非负整数h 和k ，定 义a 和b 的( 九，k ) 一h u r w i t z 乘积为所有h 个a 和k 个b 的乘积之和，记为( a ，b ) ( ，七) 。例如： ( 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 ) 式的解是始终严格正的【2 】。 如果存在非负整数h 和k ，使得对九+ k 0 ，有( a ，b ) ( ，七) 0 ，则称矩阵对( a ，b ) 是本原 的的，并且将h + k 的最小值定义为本原矩阵对( a ，b ) 的本原指数，记为e x p ( a ，j e i ) 。 设d 是一个有向图，d 的一条长为z 的途径是指连续的顶点序列仇，v 2 ，砷+ 1 ，其中对 所有的i = 1 ，2 ，z ，d h h 有从仇到协+ 1 的弧。如果v 1 ，t j 2 ，铆+ 1 互不相同，则称该途径是 一条长为2 的路。如果v 。= 叻+ - ，则称为一条闭路或圈【3 】。如果d 是包含红弧和蓝弧的有向 图，则称d 是一个双色有向图。n 阶矩阵对与双色有向图可以建立相应的对应关系。对每一 对非负矩阵对( a ，b ) ，其伴随有向图，记为d ( a ，b ) 。显然d ( a ，b ) 具有顶点1 ) 1 ，v 2 ，矩 阵a = ( a o ) 中元素值非零或零对应于d 中有没有红弧，如果a i j 0 ，则从顶点忱到顶点存 在一条红弧；矩阵b = ( b o ) 中元素值非零或零对应于d 中有没有蓝弧，如果幻 0 ，则从 顶点耽到顶点存在条蓝弧。根据这种一一对应关系，我们可以在双色有向图和它的伴随 非负矩阵对之间建立联系，通过研究双色有向图的问题去解决非负矩阵对的问题。我们称 双色有向图d 是本原的，如果其伴随非负矩阵对( a ，b ) 是本原的，且d 的本原指数e x p ( d ) 既 为( a ，b ) 的本原指数e x p ( a ，b ) 。双色有向图d 是强连通的，如果d 中每一对顶点( 忱，) 都存 在从地到吩的途径。d 中的一条途径u ，用r ) 和6 ) 分别表示u 中红弧和蓝弧的条数，称u 为 第4 页 一条( r ) ，6 ( u ) ) - 途径，u 的分解为向量( r ) ，6 ( u ) ) 或 瞄 o 一个双色有向图d 是本原的，当且仅当存在非负整数h 和七，且h + k 0 ，使得d 中的每 一对顶点( 仇，吻) 都存在从忱到的( ，后) - 途径，h + 七的最小值定义为双色有向图d 的本原指 数，记为唧( d ) 。( h ，七) 途径是指从饥到吻的途径中包含 条红弧和七条蓝弧。 设c = 7 1 ，7 2 ，m 】是d 的圈的集合，定义d 的圈矩阵 一i a l a 幻2 ia l - 1 a t ， 6 2 6 l 一1 其中吼，6 i ( 1 i z ) 表示圈m 中的红弧和蓝弧的数目。m 是一个2 2 矩阵，它的第i 列是m 的 分解。m 的容度( 记为c o n t e n t ( m ) ) 定义为。如果m 的秩小于2 ，否则定义为蝴所有非零2 阶 子式的最大公因子。 非负矩阵对与其伴随有向图之间存在这样一种对应关系，可以通过研究双色有向图的 本原性及本原指数等问题来解决非负矩阵对的相关问题。 1 2 3 本原矩阵簇与多色图 在本原矩阵对的研究基础上，人们又提出了本原矩阵簇的概念，其研究背景如下【4 】： 类似于2 维离散动力系统，可以将一个几阶k 簇矩阵a = ( a ，a 2 ，a ) 考虑为七维离散 动力系统z ( i l ，i 2 ，i 七) ( i 1 ，i 2 ，i k z 且1 i l + i 2 + + i k o ) 。该系统由初始条件 和递归公式 x ( i l ，i 2 ，i k ) ( i l + i 2 + + i k 0 ) x ( i l + 1 ，i 2 + 1 ，i 七+ 1 ) = a 1 z ( i l ，i 2 + 1 ，如+ 1 ) + a 2 z ( i 1 + 1 ，i 2 ，i a + 1 ，如+ 1 ) + + l 七z ( t l + 1 ，i 2 + 1 ，i 七) 所控制，其中x ( i l ，i 2 ，i 知) 是n 维非负向量。 设a = ( a l ，a 2 ，a 七) 为几阶非负矩阵簇，o t = ( o l l ，0 1 2 ，q 七) 是七维非负整数组，a 表 示所有n 1 个a 1 、0 1 2 个a 2 、q 七个a 七之和。例如： a ( 1 ，1 ，1 ) = a n a 2 a 珐。 第5 页 中北大学学位论文 如果存在k 维非负整数组q ，使得a o 0 ，则a 是本原的，使得a a 0 的a 1 + q 2 + + q 七 的最小值定义为本原矩阵簇a 的本原指数。本原矩阵簇即是本原矩阵对的推广形式。 一个着k 种颜色的有向图g 是由七簇子图g l ，g 2 ，g 七组成的，其中g 1 ，g 2 ，g 知将g 中的弧分割成k 个非空子集。我们认为g t 在g 中着第i 种颜色，类似于g 是本原的观点，我们 可以说着七种颜色的g l ，g 2 ，g 七是k 本原的，如果存在一组正整数r l ，r 2 ，仇使得g 中的 任意顶点对( 让，u ) ，有从仳到u 的途径，即恰好有r t 条弧着第i 种颜色，其中i = 1 ，2 ，k 。 我们可以利用矩阵来判断一个特殊的着k 种颜色的有向图是否尼本原。假设一个本原有 向图g 是由后种颜色g 1 ，g 2 ，g 组成的，g 中的圈用c 1 ，c 2 ，c l 表示，建立k f 矩阵，则 圈矩阵 m = r o l lm 1 2 m l ( t - 1 )r o l l m 2 1m 2 2 m 2 ( 1 1 ) m 2 1 m k li n k 2 m k ( t 一1 、h l 其中m 巧( 1 i k ，1 歹z ) 表示圈c j 中着第i 种颜色的数日。若：c o n t e n t ( 蚴= 1 ，则有向 图后本原。实质上，它是一个充分条件【4 】。 显然，k = 1 时即为本原矩阵的概念；k = 2 时即为本原矩阵对的概念。因此，非负本原 矩阵簇是本原矩阵对和本原矩阵的推广。 1 3国内外对矩阵本原性的研究现状 1 3 1 本原矩阵 关于非负本原矩阵a 的本原指数的研究最早始于1 9 5 0 年w i e l a n d t 的工作 1 】，w i e l a n d t 所 研究的图如图1 3 1 所示： l _ _ _ 。_ _ _ _ _ _ _ _ 。 _ _ _ _ _ _ _ _ _ i - - _ _ _ _ - - _ 一 图1 3 1w i e l a n d t 图 一1 第6 页 中北大学学位论文 w i e l a n d t 给出了n 阶本原指数的一般性上界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 结合图论知识，推导出 了佗阶本原指数的一般性上界的一种形式：e x p ( a ) n + s ( n 一2 ) ，其中s 是a 的伴随有向 图d ( a ) 的最小圈长。以与有向图相关联的非记忆通讯系统为背景，b r u a l d i 等在1 9 9 0 年提出 了本原有向图的广义指数的概念，并在计算机科学、概率论等数学分支上得到了应用。关 于，y ( a ) 或e x p ( d ) 的研究主要集中在以下四个方面【5 】： ( 1 ) 点指数：设是有向图d ，顶点i 的“点指数”e x p d ( i ) 是最小整数k ，使得从点i 到每一 点j 有长不小于七的途径。 ( 2 ) 第一类广义本原指数：对于有向图d 中的顶点 i = 1 ，2 ，扎) 进行适当排序后有， e x p d ( 1 ) e x p d ( 2 ) e x p dn ) 则e x p d ( 七) ( d 中第七小的点指数) 为d 的第k 个广义本原指数。 ( 3 ) 第二类广义本原指数：设d 是本原有向图，1 k 死一1 ，则称 f ( d ，k ) = m i n e x p d ( s ) l s y ( d ) ，i s i s = 七) 为d 的七重下广义指数。 ( 4 ) 第三类广义本原指数：设d 是本原有向图，l k n 一1 ，则称 f ( d ，k ) = m a x e x p d ( s ) i s y ( d ) ，l s i = 七) 为d 的k 重上广义指数。 目前国内外关于7 ( a ) 或e x p ( d ) 的研究，相当大部分的问题已得到或接近完全解决( 6 【7 【8 】 【9 【1 0 】【1 1 1 2 】 1 3 】【1 4 】【1 5 】) 这些结论对于图论方面的研究具有重要的指导意义。 1 3 2 本原矩阵对 对矩阵对( 双色有向图) 的本原性及其本原指数的研究是一个全新的领域，国内外研究 此内容的文献不多，近期的一些成果及重要结论见文献 2 】【6 】【1 6 】【1 7 】【1 8 】【1 9 】【2 0 】【2 1 】【2 2 【2 3 【2 4 】 2 5 2 6 。例如：在文献 2 中，得至l j t n 阶非负本原矩阵对本原指数最大值的范围是 ，n 3 5 n 23 n 3 + 2 n 2 2 n ， 【_ 丁，r j 第7 页 中北大学学位论文 且得到了三个等价结论： 设( 4 ，b ) 是几阶非负本原矩阵对，且a ，b 均是非零矩阵。设m 是d ( a ，b ) 的圈矩阵，则以 下结论是等价的。 ( 1 ) ( a ，b ) 是本原的； ( 2 ) d ( a ，b ) 是强联通的，且 = z 2 ； ( 3 ) d ( a ，b ) 是强联通的，且c o n t e n t ( m ) = l 在文献【6 】【1 9 】【2 3 】对未着色图为图1 3 2 ( 其中s 0 ，t o ) 的双色有向图的本原性及本原 指数进行研究，得到了一些重要结论。 s 图1 3 2d 的未着色图 在文献【6 】中考虑了t = 1 的情形，此时本原的情况下所对应的圈矩阵 m = 一讲 找到了指数上界并刻划了 n 一1 _ 2 _ _ s _ ( s + 1 ) 一( s + 2 ) 中包含一条蓝弧的指数集，得到以下主要结论： 定理1 3 1 若双色有向图d 是本原的，且 竹_ 1 2 _ _ s _ ( s + 1 ) _ ( s + 2 ) 中包含一条蓝弧，则 2 n 2 3 n + 1 e x p ( d ) 2 n 2 2 n + 2 s n s 。 第8 页 定理1 3 2 若双色有向图d 是本原的，且 佗_ 1 _ 2 _ _ s _ ( s + 1 ) 一( s + 2 ) 中不包含蓝弧，则 e x p ( d 1 = 2 n 2 4 n + 1 。 定理1 3 3 若双色有向图d 是本原的，s = 0 _ r n _ 1 _ 2 _ _ s _ ( s + 1 ) _ ( s + 2 ) 中包含一条蓝弧。则 e x p ( d ) = 2 n 2 3 n + 1 。 此时双色有向图d 为w i e l a n d t 图。 定理1 3 4 若双色有向图d 是本原的，s l f i 礼_ 1 _ 2 一_ s _ ( s + 1 ) _ ( s + 2 ) 中包含一条蓝弧，则d 的指数集是 2 n 2 + 2 ( k 一1 ) n k l k = 0 ，1 ，s ) u 2 佗2 3 n + 1 ) 。 在文献 1 9 1 中考虑了= 2 的情形，此时本原的情况下所对应的圈矩阵 叶口x1 ， 其中n s + 4 ，n = 2 q + 1 。找到了指数上界并刻划了极图，得到以下主要结论： 定理1 3 5 若双色有向图d 是本原的，则 ，l 下n 3 - - 2 n 2 + l ， ( 一7q2s-q-,) 2 6 叶2 吲 ( s # 3 ) n ：_ ( 3 5 + 8 ) n + s + 3 ：s 口- 1 ；。 定理1 3 6 若双色有向图d 是本原的，则 e x p ( d 1 = 2 礼2 6 n + 2 当且仅当d 中存在一条2 长的红路。 第9 页 中北大学学位论文 定理1 - 3 7 若双色有向图d 是本原的，且ssq 一2 则 e x p ( d ) = 掣 当且仅当几圈上存在一条g + 1 长的红路。 定理1 3 8 若双色有向图d 是本原的，且s g 一1 则 e x p ( d ) = ( s + 3 ) n 2 一( 3 s + 8 ) n + 8 + 3 当且仅当d 中存在一条s + 3 长的红路，且所有红弧不间断。 在文献 2 3 】中考虑了t 3 ，s = o 的情形，此时本原的情况下所对应的圈矩阵 m = 佗一ann b 。一6 ， 其中号o n 。给出了本原条件，找到了指数上界并刻划了极图，得到以下主要结论： 定理1 3 9 若双色有向m d 是本原的，且n ( 几一) 一b n = 1 。 ( 1 ) 若6 = 1 ，则几是奇数，t = 佗一2 ，o = 孚，且 e x p ( d ) 生等生。 ( 2 ) 若b 2 ，则 e x p ( d ) ( n a ) ( 2 b n + 1 ) + 佗。 定理1 3 1 0 若双色有向图d 是本原的，且n ( 礼一t ) 一b n = - 1 。 ( 1 ) 若礼一a 一1 ，则 e x p ( d ) ( n a ) ( 2 b n 一1 ) + n 。 ( 2 ) 若n a t 一1 ，则 e x p ( d ) ( 礼一n ) ( 2 轨一1 ) 。 定理1 3 1 1 若双色有向图d 是本原的，且n ( n t ) 一b n = 1 。 ( 1 ) 若b = 1 ，则 e x p ( d ) ：丝等生 第1 0 页 中北大学学位论文 当且仅当 t _ ( t + 1 ) _ _ 几_ 1 为蓝路，且n 圈上的a 长红弧连续。 ( 2 ) 若b 2 ，则 e x p ( d ) ( n a ) ( 2 b n + 1 ) + 礼 当且仅当n 圈上的a 长红弧连续。 定理1 3 1 2 若双色有向图d 是本原的，e la ( n t ) 一b n = - 1 。 ( 1 ) 若礼一a t l ，则 e x p ( d ) = ( 礼一a ) ( 2 b n 一1 ) + 礼 当且仅当 t 一( t 十1 ) 一_ 佗_ 1 为红路，且几圈上的n n 长蓝弧连续。 ( 2 ) 若n a t 一1 ，则 e x p ( d ) = ( 凡一a ) ( 2 b n 一1 ) 当且仅当n 圈上的n a 长蓝弧连续。 在文献【2 0 】中对以下图1 3 3 进行了讨论，得到了以下重要结论， 图1 3 3 中由两个x 购n ( n 3 ) 圈构成的双色有向图d ，且d 至少有一条蓝弧和一条红 弧。 图1 3 3 双向圈d 显然d 有两个伽圈和n 个2 圈，且d 的严格圈矩阵是以下矩阵的子矩阵 a 斟 第1 l 页 定理1 3 1 3 设d 是如图1 3 3 所示的佗阶双色双向圈，则 ( 1 ) 如果在d 中没有一个单色的2 圈，则d 是本原的当且仅当n 是奇数，且每个礼圈上红 弧的个数为华或下n - i - 1 。 ( 2 ) 如果在d 中至少有一双色2 一圈和一单色2 圈，则d 是本原的当且仅当几是奇数。 ( 3 ) 如果在d 中没有双色2 一圈，则d 不本原。 由定理1 3 1 3 可知，d 是本原的当且仅当礼为奇数，且d 对应的严格圈矩阵m 为下列矩 旧n - 1 卦h a0 ：兰n a 口n 二6 ， ：兰言竹一aq 几二6 。 定理1 3 1 4 图d 为如图1 3 3 所示的n 阶本原双色双向圈，设n = 2 q + 1 且 儿心1 则 e x p ( d ) 3 ，那么 ( 1 ) 如果n 5 ，则 e x p ( d ) 2 ( 9 2 + g ) ：掣， 且等号可以成立。 ( 2 ) 如果佗= 3 ，则 e x p ( d ) 5 ， 且等号可以成立。 本原矩阵对指数( 双色图本原指数) 主要研究问题： ( 1 ) 继续寻找矩阵的本原条件； ( 2 ) 影响本原矩阵对本原指数大小的关键因素； ( 3 ) 找出本原指数的一般上界，并研究其极图的刻划； ( 4 ) 探索研究传统本原指数的一些性质在本原矩阵对本原指数的推广； ( 5 ) 对一些特殊图的研究，找到其指数的范围，并对达到指数的上、下界的极图。 1 3 3 本原矩阵簇 关于非负本原矩阵簇的研究，国内外这方面的文献相当少，只取得的少部分成果。例如： 在文献 2 7 】中，给出了住阶非负本原矩阵簇的本原指数最大值估计为o ( 舻+ 1 ) 。在文献 2 8 】中， 证明了任意本原有向图均存在2 着色是2 本原的。进一步，利用反证法对k 4 时，通过构造 例子证明了含有k 个圈的本原有向图着k 种颜色不是k 本原的。最后给出了含有三个圈的三色 有向图的本原条件的一个猜想：若g 是含有三个圈的本原有向图，三个圈c - ，q ，c 3 的圈长分 别为f 1 ，1 2 ，z 3 ，令z 1 ，f 2 ，z 3 的最大公因数是g ，则三色有向图g 所对应的矩阵 m = n z f 1 一a x b ! ， 1 2 b y c z 1 3 一c z 第1 3 页 中北大学学位论文 满足行列式d e t ( m ) = 士夕。 对本原矩阵簇主要研究问题： ( 1 ) 继续寻找矩阵簇的本原条件； ( 2 ) 寻求影响本原矩阵簇本原指数大小的关键因素； ( 3 ) 找出本原指数的一般上界，并研究其极图的刻划； ( 4 ) 探索研究传统本原指数的一些性质在本原矩阵簇本原指数的推广； ( 5 ) 对一些特殊图的研究，找到其指数的范围。并对达到指数的上、下界的极图。 1 4本文的主要工作 本文主要内容为： 在第一章中，首先介绍了一些非负矩阵论和图论的相关基础概念和知识，由图与非负 矩阵的关系引入了有向图本原及其本原指数的相关概念，并且比较详细的介绍了图的本原 指数的研究成果以及以后所要考虑的问题。 第二章研究一类特殊双色双圈有向图，其基础有向图包含一个( ( t 一1 ) m + 1 ) 一圈和一 个( t i n + 1 ) 一圈。应用组合矩阵论和图论的方法得到这类图本原的条件和指数的界。最后得 到本原指数集并对达到指数上下界的极图进行刻划。 第三章研究一种利用n 阶方阵及其所确定的赋权有向图的关系解决矩阵运算的方法，使 其应用在第二章的计算当中。 第1 4 页 中北大学学位论文 第二章一类双色双圈有向图的本原指数 本章讨论一类双色有r e 图d m tm 2 , t 2 ) ，其基础有向图如图2 所示。 m + l m + 2 l m + l 们 图2 有向图d 对任意d d m t d 中只有2 个圈，分别为( ( t 一1 ) m4 - 1 ) 一圈和( t i n4 - 1 ) 一圈。故可设其 圈矩阵为 广1 m ：l 口6 i ，= ll ， l ( t 一1 ) m 4 - 1 一nt m + 1 一bl 其中j 【( t 一1 ) m + l 】o ( t 一1 ) m4 - l 。 2 1 指数的界 引理2 1 1 设d 是一个至少含有一条红弧和一条蓝弧的双色有向图，m 为其圈矩阵，则d 是 本原的当且仅当d 是强连通的i ：l c o n t e n t ( m ) = 1 。 定理2 1 1 双色有向图d d m t 是本原的当且仅当 a = ( t 一1 ) ( m 一1 ) 4 - 1 ，b = t ( m 一1 ) 4 - 1 。 证明：由引理2 1 1 ，若d 本原，有 d e t ( m ) = a ( t m4 - 1 ) 一6 ( t 一1 ) m4 - 1 】= 4 - 1 ， 则 6 = n + 高a 第1 5 页 中北大学学位论文 ( 1 ) 若6 = n + 可a j m 丽+ l ，设七1 = 可j a m 而+ l ，( k l = 1 ，2 ，) ，则n = 七1 ( t 一1 ) + 。 h = 1 ，a = t 一1 ( t 1 ) m + 1 ； k l i m + 2 ，( i + 1 ) m 】，( i = 0 ，1 ，2 ，) ，a t f 是正整数； k 1 = i m + 1 ，( i = 2 ，3 ，) ，a 是正整数，但a ( t 一1 ) m + l 。 ( 2 ) 若6 = o + f a 丽m - - 1 ，设七2 = f a 丽m - - i ，( k 2 = 1 ，2 ) ，则o = k 2 ( t 1 ) + 点警 k 2 b m ，0 + 1 ) m 一2 1 ，( i = 0 ，1 ，2 ，) ，口不是正整数； k 2 = m 一1 ，a = ( t 一1 ) ( m 1 ) + l ，符合题意； k 2 b m ，0 + 1 ) m 一2 1 ，0 = 2 ，3 ，) ，口不是正整数。 综上所述，使c o n t e n t ( m ) = 1 且满足 【( 一1 ) m + 1 j a ( t 一1 ) m + 1 的正整数a 只能 为( 一1 ) ( m 一1 ) + 1 ，从而b = t ( m 1 ) + 1 。 证毕。 根据定理2 1 1 ，可以得到d 本原的圈矩阵， m ：l ( 2 一1 ) ( m 一1 ) + l 。( m 一1 ) + 1l 。 【t - 1 t j 如果一条长度为f 的路，其弧全是红色( 蓝色) ，我们称之为z 长连续红弧( 蓝弧) 。 定理2 1 2 设d d 。，t ( m 2 ，t 3 ) ，则 2 t ( t 一1 ) m 2 + ( 2 t 一1 ) m e x p ( d ) 2 t 2 ( t 一1 ) m 2 2 t ( t 2 3 z + 1 ) m t ( 2 t 一3 ) 。 证明：先证明e x p ( d ) 2 t ( t 一1 ) m 2 + ( 2 t 一1 ) m 。 设( ，) 为一对非负整数，使得d 的每对顶点( i ，j ) 都有一条从i 到j 的( ，k ) - 途径。取i = 歹= m + 1 ，则存在非负整数i t 和u 使得有 hi 。 因为( t i n + 1 ) 一圈上有t 条蓝弧，所以其上必存在一条m 长连续红弧。取i 和j 分别为该m 长连 续红弧的起点和终点，那么从i 至：l j j 的每条途径都可以分解成从i 至：i j j 的弧和一些圈。因此 ”讹 第1 6 页 中北大学学位论文 有非负整数解。则 名= ： 一九广1 ： = ： 一 一。三，仇 。 再取i 和j 分别为m 长连续红弧的终点和起点，那么从i 到歹的路的分解为 。一：j l 或 一1 ：仇一1 ， 2 = 一：! l 一1 ) + 死眨 2 = 一。( m 一。 + m z 或 名= ： 一- 纩1 p ：i ! l 一。 “ u 一z m + 11 ll o l - ( t 1 ) mj ：= ： 一 f 1 一。，一u = ： 一 。一：；：+ 1 。 二! ：_ i ；：三二i 二1 ，：7 三m ： 一1 ，m + l m 十1 t m ，m 再证e x p ( d ) 2 t 2 ( t 一1 ) m 2 2 t ( t 2 3 t - b1 ) m t ( 2 t 一3 ) 。 ( 2 t 2 ( t 一1 ) ( m 一1 ) 2 + 2 t ( 2 t 一1 ) ( m 一1 ) 十2 t ，2 t 2 ( 一1 ) ( m 一1 ) + t ( 2 t 1 ) ) 一途径。 设p 巧为从涯好的最短路，记7 = r 巧) ，b = b ( p 巧) 。我们有 第1 7 页 中北大学学位论文 + c 铲c m 一，+ t 一打+ 陋c m 一1 ，+ 1 ，6 ， + ( ( t 1 ) ( m 1 ) + t + ( t 一1 ) r 一【( t 一1 ) ( m 一1 ) + 1 】6 ) l 。( m 一1 ) + 1 it 考虑以下两种情形： 情形1 ：1si j m ，显然0 b 2 。若b = 0 ，则0 r m 一1 ；若b = 1 ， 则0 r m 一2 ；若b = 2 ，贝0 0 r m 一3 。 因此 t 2 ( m 一1 ) + t t r + 【t ( m 一1 ) + 1 】6 0 且 t ( t 一1 ) ( m 一1 ) + t + ( t 一1 ) r 一【( 一1 ) ( m 一1 ) + 1 】6 0 ， 根据( 2 1 1 ) ，p , i n j 绕( ( t 一1 ) m + 1 ) 一圈t 2 ( m 一1 ) + t 次，绕( t m + 1 ) - - 圈t ( t 1 ) ( m 一1 ) + t 次 的途径为一条 ( 2 t 2 ( 一1 ) ( m 一1 ) 2 + 2 t ( 2 t 一1 ) ( m 一1 ) 十2 t ，2 t 2 ( t 一1 ) ( m 一1 ) + t ( 2 t 1 ) ) 一途径。 情形2 ：包含( ( t i ) m + 1 ) - m 上的点，显然o b t 。若6 = i ，0 r ( t 一1 ) m + 1 ，( i = 0 ，1 ，2 ，t 一1 ) ；若b = t ，0 7 ( t i ) m 因此 t 2 ( m 一1 ) + t t r + 陆( m 一1 ) 十1 】6 0 且 t ( t 1 ) ( m 一1 ) + t + ( t 一1 ) r 一【( t 一1 ) ( m 1 ) + l i b 0 ， 根据( 2 1 1 ) ，从谣归绕( ( 一1 ) m + i ) - m t 2 ( m 一1 ) + 次，绕( t m + 1 ) - 圈t ( t 一1 ) ( m 一1 ) + t o ： 的途径为一条 ( 2 t 2 ( t 一1 ) ( m 一1 ) 2 + 2 t ( 2 t 一1 ) ( m 一1 ) + 2 t ，2 t 2 ( t 1 ) ( m 一1 ) + t ( 2 t 一1 ) ) 一途径。 证毕。 第1 8 页 1 土+ d l卜 l r 6 r_j 射+ 一d m 一 以 卜 “ 2 ) “1 2 一 十 n 妒嘶 一 一 n tx 妒 1 2 中北大学学位论文 2 2极图刻划 在这部分，我们对达到指数上下界的极图进行刻划。因为( ( t 一1 ) m + i ) - 圈上有t 一1 条 蓝弧，所以我们分两种类型进行讨论： 类型1 ：t m + 1 _ m + 1 为蓝弧； 类型2 ：t m + 1 _ m + l 为红弧。 我们先对类型1 进行刻划并给出一些记号。为从i 到j 的最短路，= r ( p i j ) ，b = b ( p , a ， r ( 6 ) 眦，7 ( 6 ) 椭，分别是p 玎上红( 蓝) 弧长度的最大值和最小值。 引理2 2 1 设d d 州( m 2 ，t 3 ) ，当 ( i 一1 ) m + 1 _ 一i m 为m 一1 长连续红弧， i m + 1 _ 一( i + 1 ) m + l 为m 长连续红弧， ( i + 1 ) m + 2 _ _ ( i + 2 ) m + 1 为m 一1 长连续红弧，( i = 1 ，2 ，t 一1 ) ，其他全是蓝弧时，即在( t m + 1 ) 一圈上只有一条m 长 连续红弧时， e x p ( d ) = 2 t ( t 一1 ) m 2 + (