（应用数学专业论文）矩阵对与矩阵簇的本原指数.pdf

中北大学学位论文 摘要 非负矩阵组合理论 1 】是研究那些仅依赖于矩阵的零位模式，而与矩阵元素本身数值大 小无关的性质，它与图的一些性质有密切联系，在信息科学，通信网络，计算机科学等许多 学科中都有具体的应用。 本原矩阵的本原指数及广义本原指数是非负矩阵组合理论的重要研究内容，到目前为止， 许多问题已得到解决。而在新的背景下，对非负矩阵对的本原指数的研究应运而生。事实 上，非负矩阵对可以与一个双色有向图建立一一对应关系，这样就可以把矩阵的问题转化 为图的问题进行研究。本文主要研究了两类特殊双色有向图，主要内容为： 第一章概述了图论和非负矩阵组合理论这两门学科的发展及研究内容，并介绍了一些 基本概念以及本原指数的国内外研究概况，提出本文所做的工作。 第二章研究一类特殊双圈双色有向图，其未着色有向图包含一个( m + 亡) 一圈和( m + t + 1 ) 一圈，应用组合矩阵论和图论的方法得到了这类图为本原的条件和指数的界，给出了本原 指数集并对达到指数上下界的极图进行了刻划。 第三章研究另一类特殊双圈双色有向图，其未着色有向图包含一个( 2 m + 1 ) 一圈和( m + 1 ) 一圈，给出这类图本原的条件和本原指数集。 关键词：本原指数，双色有向图，极图，本原指数集 第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 xd e m e n t i th 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 ya l r e a 8s u c h a si 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 l ei m - p o r t a n tr e s 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 t i v em a t r i xp a i r sc a n l ei n t ob e i n g i nf a c t ，t h e r ei sa o 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 o 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 n t ot h ep r o b l e mo fg r a p h i c st os o l v e t 妇p a p e rs t u d i e st w oc 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 nc h a p t e rl ，6 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 dc 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 l 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 ha l 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 , ac l a s so fs 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 e u n c o l o r e dd i g r a p hc o n s i s t so f o n e ( m + t ) 一c y c l ea n do n e ( m + + 1 ) 一c y c l e u s i n gt h em e t h o d o fc o m b i n a t 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 nt h ee x p o n e n ta x 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 s t h a tm e e tt h eu p p e rb o u n da n dt h el o w e rh o u n da l ec h a r a c t e r i z e d i nc h a p t e r3 , a n o t h e rc l a s so fs 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 dd i g r a p hc o n s i s t so fo n e ( 2 m + 1 ) - c y c l ea n do n e ( m + 1 ) - c y c l e t h e nt h e p r i m i t i v ec o n d i t i o n sa n dt h ee x p o n e n ts e ta r eg i v e n k e yw 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 第1 i 页 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行 研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：二罄l 谨l 一日期：_ 坦写l 羔l 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包括：学校 有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、 缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借 阅；学校可以学术交流为目的，复制赠送和交换学位论文：学校可以公布学 位论文的全部或部分内容( 保密学位论文在解密后遵守此规定) 。 签名：盔圣! 迪 导师签名： 日期：巡茎：羔z 一一 日期：丑啤上互l 中北大学学位论文 第一章引言 i i图论与非负矩阵组合理论 图论是组合数学中的一个重要分支，到现在大概只有二百多年的历史。 图论开始的大多数问题起源于游戏，最有代表性的工作是著名的瑞士数学家欧拉发表 予1 7 3 6 年的哥尼斯堡七桥问题。他的那篇论文被公认为图论历史上第一篇论文。1 8 4 7 年， 基尔霍夫研究电网络发现了图论新的应用提出了树的概念，它可以用来解决优化中的最小 连接问题。1 8 5 7 年，凯莱在有机化学领域里发现了树并研究了树的计数问题。1 8 5 9 年，哈 密顿发现了与图有关的难题，成为哈密顿问题，它可以用来解决旅行售货员问题。另外，工 作分配问题，邮路问题，最优路线问题等都可以用图论的方法解决。1 8 7 8 年，“图 这个词 第一次出现在的英国自然杂志中，图论作为数学的一个新分支已基本形成。1 9 3 6 年，匈 牙利图论学家柯尼希写了关于图论的第一本专著。 之后，由于生产管理、军事、交通运输、计算机和通讯网络等方面许多离散型问题的出 现，图论的发展大大加快。图论在许多领域，诸如物理学、化学、运筹学、计算机科学、信息 论、控制论、网络理论、社会科学以及经济管理各个方面都有广泛的应用。因此，受到世界 数学界和工程技术界越来越广泛的重视。 非负矩阵组合理论是研究那些仅依赖于矩阵的零位模式，而与矩阵元素本身数值大小 无关的性质，它与图的一些性质有密切联系，在信息科学，通信网络，计算机科学等许多学 科中都有具体的应用。在非负矩阵组合理论的研究中，矩阵所表现出来的组合性质，仅与矩 阵元素分布的零位模式有关，而与元素数值大小无关。因此在研究非负矩阵的组合性质的 时候，可以把一个非负矩阵转化为一个( 0 ，1 ) 矩阵来研究。而( 0 ，1 ) 矩阵与有向图可以建立一 一对应关系，这样就可以用图论的方法解决矩阵的问题。在下节，我们会介绍转化规则。 1 2本原矩阵的提出背景及研究现状 1 2 i 本原矩阵 本原矩阵的的研究来源于对非负矩阵的研究，非负矩阵理论是组合数学的一个重要研 究方向。每个元素都非负的矩阵称为非负矩阵。许多与非负矩阵相关的概念是在研究有限 第l 页 中北大学学位论文 马尔可夫链中提出的，如在文献 2 】中考虑了有限马尔可夫链，从而提出了佗阶非负矩阵的本 原指数的概念： x k = 血七一1 ( 七1 ) ， 其中a 是礼阶非负矩阵且初值x o 是非零非负向量。对所有充分大的k ，使得0 ，满足这样 的条件就可以区分马尔可夫链。易证当且仅当存在一个正整数z 使得a z20 ，则对每个非零 非负向量初值黝都存在一个k 使得对所有k k 都有z 知0 。t i , 阶非负方阵a 称为本原的，如 果存在正整数k 使小的每个元素为正数，记为小 o 。使a i , 0 成立的最t b k 称为a 的本原 指数，记为7 ( a ) 或e x p ( a ) 。 由于本原方阵的本原性及其本原指数只与方阵的零元素位置分布有关，而与非零元素 的具体数值无关。所以可以假设所有非零元素均为1 ，即所谓的( 0 ，1 ) 或布尔一方阵。下面我们 看两个具体的例子： 设方阵a = 11 0 0 0 0 l1 0 0 ll 01 o0 阵a 是本原的，且，y 似) = 3 。 设方阵b = 0l0 0 01 100 ，则a 2 = ，则b 2 = 11 11 11 l1 o 01 1o0 010 1 1 01 0 0 11 ，= ，伊= 11 l1 l1 11 ol0 0 01 10 o 11 1l 11 l1 。所以矩 = b 。显然不存在 正整数k ，使b 七 0 ，所以b 是不本原的。 矩阵a 可以与它所对应的伴随有向图d 似) 建立一一对应关系，即矩阵a = ( ) 中元素 值非零当且仅当从i 到j 有一条弧。例如：a 1 2 0 表示从顶点l 到顶点2 有一条弧；a 1 2 = 0 表示 从顶点1 n 顶点2 没有弧；a 1 1 0 表示从顶点1 到顶点1 有一条弧，即顶点1 有环。利用这种对 应关系，则上例中方阵a 所对应的伴随有桃f l d ( a ) 如图1 1 所示。 图1 1 第2 页 中北大学学位论文 方阵b 所对应的伴随有向图d ( 口) 如图1 2 所示a l 2 3 图1 2 根据这种对应关系，称d ( a ) 为a 的伴随有向图，a 为d ) 的邻接矩阵。若a 是本原方阵， 贝i j d ( a ) 称为本原有向图。换言之，有向图d 称为本原的，如果d 的邻接矩阵a 是本原的。对 于( o ，1 ) 方阵a 的本原性及其本原指数的研究可以转化为研究有向图d ( a ) 的本原性及其本原 指数这样一个等价的图论问题了。 关于本原矩阵的本原指数的研究最早始于1 9 5 0 年w i e l a n d t 的工作 3 】，给出了n 阶本原 指数的一般性上界e x p ( a ) 一1 ) 2 + 1 。w i e l a n d t 所研究的图如图1 3 所示。 n1 礼一 图1 3w i e l a n d t 图 2 3 随着对本原指数的继续研究得到了一些重要的成果，在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 似) 或e x p ( d ) 的研究主要集中在以下四个方面 4 】： ( 1 ) 点指数：设d 是本原有向图，顶点i 的“点指数”e x p d ( i ) 是最小整数k ，使得从点i 到 每一点j 有长为k 的途径。 ( 2 ) 第一类广义本原指数：对本原有向图d 中的顶点 i = 1 ，2 ，n ) 按下面方式排序 e x p d ( 1 ) e x p n ( 2 ) e x p d ( 扎) 第3 页 中北大学学位论文 则称e x p d ( 七) 为d 的第k 个广义本原指数。 ( 3 ) 第二类广义本原指数：设d 是n 阶本原有向图，1 k 佗一1 ，则称 f ( d ，k ) = m 溉 唧d ( s ) l s y ( d ) ，i s i = 七) 为d 的k 重下广义指数。 ( 4 ) 第三类广义本原指数：设d 是礼阶本原有向图，1 k n 一1 ，则称 f ( d ，k ) = m a x e x p d ( s ) i s y ( d ) ，1 8 l = 忌) 为d 的k 重上广义指数。 目前国内外关于7 ( a ) 或e x p ( d ) 的研究，相当大部分的问题已得到或接近完全解决( 【1 2 】 1 3 】 【1 4 】【1 5 】 1 6 】 17 】【1 8 】 1 9 】 2 9 】 3 q 】) 。 1 。2 2 本原矩阵对与双色本原有向图 n 阶本原矩阵对的本原指数提出于如下背景 5 1 - 考虑2 维离散动力系统 z ( + l ，k + 1 ) = 血( 九，k + 1 ) + b x ( h + 1 ，七) ，h ，k z ，h + k 0 。( 1 2 2 1 ) 其中4 和b 是佗阶非负矩阵，初始条件x ( h ，一 ) z ) 是仃维非负向量。对非负整数h 和k ，定 义a 和b 的( 危，k ) 一h u r w i t z 乘积为所有h 个a 和k 个b 的乘积之和，记为似，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 ) 式的解是始终严格正的【6 】。 如果存在非负整数h 和k ，使得对 + k 0 ，有( a ，b ) ( 乒) 0 ，则称矩阵对( a ，b ) 是本原 的的，并且将h + k 的最小值定义为本原矩阵对( a ，口) 的本原指数，记为e x p ( a ，b ) 。 设d 是一个有向图，d 的一条长为z 的途径是指连续的顶点序列i l ，i 2 ，i l + l ，其中对 所有的k = 1 ，2 ，z ，d 中有从让到i 南+ 1 的弧。如果i 1 ，i 2 ，i l + l 互不相同，则称该途径是 一条长为z 的路。如果i l = i t + a ，则称为一条闭路或圈 1 】。如果d 是包含红弧和蓝弧的有向 图，则称d 是一个双色有向图。佗阶矩阵对与双色有向图可以建立相应的对应关系。对每一 对非负矩阵对( a ，b ) ，其伴随有向图，记为d ( a ，b ) 。显然d ( a ，b ) 具有礼个顶点，设其顶点集 第4 页 中北大学学位论文 为y = 1 ，2 ，纷 。矩阵a = ( ) 中元素值非零当且仅当d 中由顶点i 到顶向有一条红弧； 矩阵b = ( ) 中元素值非零当且仅当d 中由顶点i 到顶点歹有一条蓝弧。根据这种一一对应关 系，我们可以在双色有向图和它的伴随非负矩阵对之间建立联系，通过研究双色有向图的问 题去解决非负矩阵对的问题。我们称双色有向图d 是本原的，如果其伴随非负矩阵对( a ，b ) 是 本原的，且d 的本原指数e x p ( d ) 既为( a ，b ) 的本原指数e x p ( a ，b ) 。双色有向图d 是强连通 的，如果d o e 每一对顶点( i ，j ) 都存在从i 至j j j 的途径。d 中的一条途径u ，用，) 和6 0 ) 分别表 示u 中红弧和蓝弧的条数，称u 为一条p ) ，6 ) ) 一途径，u 的分解为向量( r 0 ) ，6 p ) ) 或 。 一个双色有向图d 是本原的，当且仅当存在非负整数h 和k ，且h + k 0 ，使得d 中的每 一对顶点( z ，歹) 都存在从i 到j 的( ，k ) - 途径，h + 七的最小值定义为双色有向图d 的本原指数， 记为e x p ( d ) 。( h ，七) _ 途径是指从i 到j 的途径中包含h 条红弧和k 条蓝弧。 设c = 饥，仡，m ) 是d 的圈的集合，定义d 的圈矩阵 肚| - a l0 , 2 一a l 柚- 1 a l j l6 l6 2 幻一l 现i 其中a i ，b i ( 1 i z ) 表示圈m 中的红弧和蓝弧的数目。m 是一个2 z 矩阵，它的第i 列是m 的 分解。m 的容度( 记为c o n t e n t ( m ) ) 定义为0 如果m 的秩小于2 ，否则定义为m 的所有非零2 阶 子式的最大公因子。 对矩阵对( 双色有向图) 本原性及本原指数的研究，是一个新的领域，国内外研究此内容 的文献不多，近期得到的一些成果及重要结论见文献阴 2 3 】【2 4 1 【2 5 】【2 6 】【5 】【6 】( 2 7 】【3 3 】 3 6 】 3 7 3 8 。 例如：在文献【7 】中，得到了n 阶非负本原矩阵对本原指数最大值的范围是 r n 3 5 n 23 n 3 + 2 舻一2 佗， 【r r j 且得到了三个等价结论： 设，b ) 是扎阶非负本原矩阵对，且4 ，b 均是非零矩阵。设m 是d ( a ，b ) 的圈矩阵，则以 下结论是等价的。 ( 1 ) ，b ) 是本原的； ( 2 ) d ( a ，b ) 是强联通的，且 = 矛， ( 3 ) d ( a ，b ) 是强联通的，r c o n t e n t ( m ) = 1 。 第5 页 中北大学学位论文 在文献 2 3 】【2 4 】f 3 3 】对未着色图为图1 4 ( 其中s 0 ，t o ) 的双色有向图的本原性及本 原指数进行研究，得到了一些重要结论。 图1 4d 的未着色图 在文献【2 3 】中考虑了t = 1 的情形，本原时对应的圈矩阵为 m 一 n ：l 佗：2 ， 文中给出了指数上下界和指数集，主要结论如下： 定理1 2 1 若双色有向图d 是本原的，r n _ 1o2 _ _ s 一( s + 1 ) _ ( 8 + 2 ) 中包 含一条蓝弧，则2 n 2 3 n + 1 e x p ( d ) 2 舻一2 n + 2 s n s 。 定理1 2 2 若双色有向图d 是本原的，r n 一1 _ 2 _ 一s 一( s 十1 ) 一( s + 2 ) 中不 包含蓝弧，贝l | e x p ( d ) = 2 n 2 4 n + 1 。 定理1 2 3 若双色有向图d 是本原的，8 = 0 r n _ 1 _ 2 _ _ s _ ( s + 1 ) _ ( s 十2 ) 中 包含一条蓝弧，贝j j e x p ( d ) = 2 n 2 3 n + 1 ，此时双色有向图d 为w i e l a n d t 图。 定理1 2 4 若双色有向图d 是本原的，s 1 r n _ 1 _ 2 _ _ s _ ( s - i - 1 ) _ ( s + 2 ) 中 包含一条蓝弧，则d 的指数集是 2 n 2 + 2 ( k 一1 ) 亿一七i 忌= 0 ，1 ，s u 2 n 2 3 n + l 。 在文献 2 4 】中考虑了t = 2 的情形，本原时对应的圈矩阵为 m = 一口二1 ， 其中礼s 士4 ，钆= 2 q 幸1 。文中给出了指数上下界并刻划了极图，主要结论如下； 定理1 2 5 若双色有向图d 是本原的，则 。，。，it n a - - 2 n 2 + l ，( s q 一2 ) 2 舻墙+ 2 t 一1 ，则e x p ( d ) ( n a ) ( 2 b n 一1 ) 。 定理1 2 1 1 若双色有向图j d 是本原的，且a ( n t ) 一b n = 1 。 ( 1 ) 若6 = 1 ，贝t j e x p ( d ) = 垒掣当且仅当t _ ( t + 1 ) _ _ 死_ 1 为蓝路， 且他圈上的a 长红弧连续。 ( 2 ) 若b 2 ，贝t j e x p ( d ) ( 佗一n ) ( 2 轨+ 1 ) + 礼当且仅当礼圈上的a 长红弧连续。 定理1 2 1 2 若双色有向图d 是本原的，且。何一t ) 一b n = - 1 。 ( 1 ) 若n a t 一1 ，贝1 e x p ( d ) = 一n ) ( 2 轨一1 ) + n 当且仅当t _ ( t + 1 ) 一一 礼呻l 为红路，且n 圈上的佗一a 长蓝弧连续。 ( 2 ) 若礼一a t 一1 ，贝l j e x p ( d ) = m 一口) ( 2 轨一1 ) 当且仅当礼圈上的他一n 长蓝弧连续。 最近，文章【3 4 】将双色图本原指数的概念做了推广提出了双色图的三类广义指数，并 对w i e l a n d t 图做了进一步研究，给出了w i e l a n d t 图的三类广义指数。为便于描述，我们用原 文的图形及标号方式( 见图1 5 ) 。 第7 页 中北大学学位论文 图1 5w i e l a n d t 图 设d ( 。) 为z 本原有向图，其顶点集v ( d ( o ) = 口1 ，7 1 2 ， 。对任一地y ( d ( ) ) ，点指 数饧( z ) 陬) 定义为m l + m 2 + + m l 的最小正整数，使得仇到d ( ) 任一项点都有一条( m l ，r n 2 ， ，m 1 ) 一途径；对任一x y ( d ( ) ) ，集指数e x p d ( t ) ( x ) 定义为p 1 + 耽+ + a 的最小正整数， 使得对任一d ( n ，x 中至少有一个顶点到为一条l ，) 2 ，鼽) 一途径。 ( 1 ) 第k 个第一类广义指数：设d ( ) 为n 阶k 本原有向图。按下面方式对扎个顶点进行排序 ，y d ( o ( v 1 ) s “f d ( 1 ) ( u 2 ) 饧( i ) ( ) ， 则称佃( t ) ( 仇) 为d ( ) 的第后个第一类广义指数，记为e x p d ( ) ( 忌) 。 ( 2 ) 第k 个第二类广义指数：设d ( o 为n 阶忌本原有向图，且1 k n 。定义 ，( d ( n ，k ) = m i n e x p d ( z ) ( x ) i x y ( d ( ) l x l = 七， 称，( d ( n ，七) 为d ( ) 的第k 个第二类广义指数。 ( 3 ) 第k 个第三类广义指数：设d ( ) 为佗阶k 本原有向图，且1 k n 。定义 f ( d ( n ，k ) = m 口z e x p d ( 1 ) ( x ) l x y ( d ( ) )i x i = k ， 称f ( d ( o ，七) 为d ( ) 的第k 个第三类广义指数。 根据文献 3 4 】，双色本原w i e l a n d t 图有两种类型： 类型1 - 啦一或_ 一1 是蓝弧，移l _ 一l 是蓝弧，其它全是红弧； 类型2 ：路径一l _ 一2 _ 一u 1 上仅有一条蓝弧，其它全是红弧。 以下是主要结论； 定理1 2 1 3 设孵为n 阶双色本原w i 妇l d t 图。若孵是类型1 且u 1 _ 和钞1 _ 一1 是蓝 弧，那么对1 k n ，有 e x p w 擎) ( k ) = ，y 嘏) ( 仇) ；舻一2 n 4 - k 。 第8 页 中北大学学位论文 定理1 2 1 4 设胖为扎阶双色本原w i e l a n d t 图。若瞻是类型l 且_ 一l 和啦一一l 是 蓝弧，那么对1 k n ，有 e x p w a 2 ) ( k ) = 仉许) ( ) = n 2 2 n + k + 1 。 定理1 2 1 5 设胖为死阶双色本原w i e l a n d t 图。若谢2 是类型2 ，设_ 吻一l 为蓝弧，2 j 他一1 ，那么对l k n ，有 叩钟) ( 膏) = 1 砰) ( ) = 矛一2 n + k j + 1 。 定理1 2 1 6 设- 渚为n 阶双色本原w i e l a n d t 图。若弼( 2 是类型1 且移1 _ v j f l l v l _ 一l 是蓝 弧，则有 ( 1 ) ，( 仇沓) ，k ) = n 一1 銎k n ，且 ( 2 ) ，( 耐2 1 ，七) r t 2 2 k n + 2 k l2 k 与 。 定理1 2 1 7 设孵为n 阶双色本原w i e l a n d t 图。若孵是类型l 且一v n 一1 和仇一一1 是 蓝弧，则有 ( 1 ) ，( w 沓) ，k ) = 死等sk n ，且 ( 2 ) ，( w 磐) ，k ) r t 2 2 k n + 2 k2 七1 n - 广1 。 定理1 2 1 8 设w 5 2 为扎阶双色本原w i i e k d t 图。若l 砰是类型2 ，设一一1 为蓝弧，2 j n 一1 ，则有 ( 1 ) ，( w 謦) ，k ) = 佗一1 n + 2 l k n ，且 ( 2 ) ，( w 磐) ，k ) n 2 2 k n + 佗+ 2 k 一12 k 等。 定理1 2 1 9 设孵为佗阶双色本原、i e l a n d t 图。若孵是类型l 且钉1 _ 和t ，1 一一l 是蓝 弧，那么对2 0 的o t l + q 2 + + q 七 的最小值定义为本原矩阵簇a 的本原指数。 设c l ，c 2 ，吼表示k 种不同的颜色，矩阵簇a 的的多色有向图d ( a ) 具有几个顶点1 ，2 ， ，礼允许有环，且对所有顶点对( i j ) ，由顶点i 到j 有一条c t 颜色的弧当且仅当a l 的( i j ) 元素是1 # ) 表示k 1 向量，它的第i 个坐标表示在u 上颜色为q 的弧的个数。 对每一顶点对( u ，v ) ，a ( - ，2 ，“) 的( u ，v ) 元素是正当且仅当d ( a ) d o 存在从u 到t ，且# p ) = ( i l ，i 2 ，i k ) t 的途径。 k = 1 时，矩阵簇的本原概念即为传统的本原矩阵的概念；k = 2 时，矩阵簇的本原概念 即为本原矩阵对的概念。因此，非负本原矩阵簇( 多色本原有向图) 及矩阵对的本原指数的概 念是传统本原指数( 单个本原矩阵的本原指数) 概念的推广。 关于非负本原矩阵簇的研究，国内外这方面的文献相当少，只取得的少部分成果。例如： 在文献【3 9 】中，给出了n 阶非负本原矩阵簇的本原指数最大值估计为o ( 矿“) 。在文献 9 】中， 证明了任意本原有向图均存在2 着色是2 本原的。进一步，利用反证法对k 4 时，通过构造 例子证明了存在k 圈k 色本原有向图，但不是k 本原。最后给出了含有三个圈的三色有向图的 本原条件的一个猜想： 第1 0 页 中北大学学位论文 若g 是含有三个圈的本原有向图，三个圈g ，g ，g 的圈长分别为z 1 ，1 2 ，如，令z l ，1 2 ，如的最 大公因数是夕，则三色有向图g 所对应的矩阵 m = = 满足行列式d e t ( m ) = 士9 。 口 z z l a z b 暑， z 2 一b 一矽 c 名 1 3 c z 1 3 本文的主要工作 本文主要研究了两类特殊双圈双色有向图，主要内容为： 第二章研究一类特殊双圈双色有向图，其基础有向图包含一个( m + ) 一圈和( m + t + 1 ) 一圈，应用组合矩阵论和图论的方法得到这类图本原的条件和指数的界，给出了本原指数 集并对达到指数上下界的极图了进行刻划。 第三章研究另一类特殊双圈双色有向图，其基础有向图包含一个( 2 m + 1 ) 一圈和( m + 1 ) 一圈，给出了这类图本原的条件和本原指数集。 第n 页 中北大学学位论文 第二章一类双圈双色有向图的本原指数及指数集 本章讨论一类双色有向图d m ，t ( m 2 , t 1 ) ，其未着色有向图如图2 1 所示。对任意d d m ，t ，d 中只有2 个圈，分别为( m + t ) - m 和( m + t + 1 ) 一圈。故可设其圈矩阵为 m = m + ：一口m + ：l 一6 ， 其中 ( m + t ) 口m + t 。 m 一2m 一12 m + t2 m + t 一1 图2 1d r 的未着色图 2 1指数的界 + t + 3 + t 一2 定理2 1 1 双色有向图d d m ，t 是本原的当且仅当n = m 牛t 1 ，b = m + t 。 证明：d e t ( m ) ：l 口6 i ：口( m + t + 1 ) 一6 ( m + 亡) 。因为d 是强连通 im + t 一口m + t + 1 一bl 的，故d 本原当且仅当c o n t e n t ( m ) = 1 ，i 郭i d e t ( m ) = 4 - 1 。从而6 = n + 黟。因为 ( m + t ) 。 a m + t ，所以a 葛m + t 一1 , b 苇m + t 。 证毕。 根据定理2 1 1 ，可以得到d 是本原时的圈矩阵， 叶叶- t o 下面对口蚶中的本原双色有向图d 分两种类型进行讨论： 第1 2 页 中北大学学位论文 类型1 ：只有一条蓝弧在m _ m + 1 _ 一m + t 上，其它全是红弧； 类型2 ：有一条蓝弧在m + t l _ _ m 上，另一条蓝弧在m + t _ m + t + 1 一一 m 上，其它全是红弧。 定理2 1 2 设d t 是类型l ，贝l | e x p ( d ) = 2 ( m + 亡) 2 1 。 证明：先证明e x p ( d ) 2 ( m + ) 2 1 。设( ，七) 为一对非负整数，使得d 的每对顶点( ，歹) 都 有一条从i 到j 的( ，l ，七) 一途径。取i = 歹= m ，则存在非负整数u 和口使得 ：m 1 【移j ”m 名 名= ”矿” 一。：讣。 最后取i 和歹分别为蓝弧的终点和起点，那么从i 到歹的路的分解为 m + ：一1 或 m j 。 ，故 ”一。卜 ” 有非负整数解。则 石= ”一。 _ 州一墨叫。 或 石= ”= ”旧。卜 第1 3 页 1j 九 七 -ljl 中北大学学位论文 所以秒m + t 一1 。从而 e x p ( d ) m = 再证e 印( d ) 1 m 2 ( m + t ) t ) 2 2 ( m + 亡) ，2 ( m - t - t ) 一1 ) 一途径 然0 b 1 。考虑以下两种情形： l 。 + 显 t h - f - 次( 仇+ t ) - 圈，m + 2 + 0 2 卅- 2 ( m 2 ( m t 1 “j o + ) 一 l i 沿黝鳓，经过，- 次( m - i - 1 ) 一r i ! t x ( m + 亡+ 1 ) 一圈的途径的分解为 叶：。 + ( 2 ( m - l - t - 1 ) - r ) = 2 ( m 芝麓删 o 证毕。 定理2 1 3d ，t 是类型2 ，贝l j 2 ( m + t ) 2 + m + _ _ e x p ( d ) 2 ( r e + t ) 2 + 2 m ( m + t ) + m i 。 证明：先证明e 印( d ) 2 ( r e + t ) 2 + m + t 。设( 危，七) 为一对非负整数，使得d 的每对顶点( t ，j ) 都 有一条p , i 到歹的( ，詹) 一途径。取i = j = m ，则存在非负整数u 和u 使得 ”m 再取i 和歹分别为( m + t + 1 ) 一圈上蓝弧的起点和终点，可以得到让m + t 。最后取i 和歹分别 为( m 十t + 1 ) - 圈上蓝弧的终 e x p ( d ) h + k - - 1 1 m ： 仇+ tm + t + 1 ： = 2 c m + t ，2 + m 十亡。 i g i 正e x p ( d ) 2 ( m + t ) 2 + 2 m ( m + t ) + m 一1 。只需证明d 的每对顶点( 瓦歹) 都有一条 从i 到歹的( 2 ( m + t ) 2 + 2 m ( m + t ) 一3 m 一2 t ，4 m 十2 t 一1 ) 一途径。设为从t 到歹的最短路， 6 溉) ，则 + t + r c m + 。6 ， m + 二一1 + ( 2 r e + t - 1 - r + ( r e + t - 1 ) b ) m - t = ! ! e _ _ _ _ 。_ _ - _ _ _ _ - - _ - _ _ _ - - _ _ _ - - - - - _ _ _ _ _ - _ _ _ _ _ - _ _ _ _ _ _ _ _ _ - - _ - _ _ - _ 。_ - - - - - _ _ _ _ _ _ - - _ _ _ 一! ! 第1 4 页 一 亿 b 2 (、扎 萨 m 引 刚 碳矧 和 勒| i = 脏 10j，糟 一吁 j嗪 t 一一r r 制“隋 i | m +廓妒 ， m 力记 rlkp ，献路 + 啦最 汁 啪慵 州 每瑚 m 噬倒亡日口，0= m 甑 叼 r，l _ = 一n 叉 小譬 k一 2 m l i 列 1 曼 l i 则缴1 m 到 m o 啦 一 一汁 z - 2 龇 “ g k 为 时 一 乩黝 懈 一 “盼卜 1 叶 鳓。 妨 勺嬲江1 v i r h 了 ； 蚴鳓叶 嵝纵卜玖 融旧 哪 那 仉 舌 * l 荨 蚪 册 i l 耽敞斗胞情卜情 一p。l t r + + m1j 烈r l 瓯 一 “：、 u 移 而从 扎 十m 一 抄 到得以可点起 和点 i i m 6 q 、几 十 黝 “r 6 | i rl r记 中北大学学位论文 _ _ _ _ _ - _ _ _ _ _ 冒曩_ _ _ _ _ _ _ _ _ 蕾- _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ii c l2 ( m + z ) 2 十2 m ( m + t ) 一3 m 一2 ti 【4 m 栅一1j 。 考虑下面三种情形， 情形l ：顶点i 和j 都在( m + t ) 一圈上，此时0 b 1 , 0 ，l 7 n + t 一1 。故2 m + t + r 一 ( m + t ) 6 0 , 2 m + t 一1 一，+ ( m + t 一1 ) 6 0 。则从z 沿鳓到j ，经过2 m + 芒+ r 一( m + 亡) 6 次( m + ) 一圈，2 m + 亡一1 一r + ( m + t 一1 ) b x ( m + t + 1 ) 一圈为一条( 2 ( m 十) 2 + 2 m ( m + t ) 一3 m 一2 t ，4 m + 2 t 一1 ) - 途径。 情形2 ：顶点i 和j 都在( m + t + 1 ) 一圈上，此时0 b 1 , 0 r m + t 。故2 m + t + ，一 ( 7 n + t ) b 0 , 2 m + t 一1 一，- + ( m + t x ) b 0 。则从i 沼巾巧到歹，经过2 m + t + r 一( 7 7 1 , + 亡) 6 次( m + t ) 一圈，2 m + 亡一1 一r + ( m + t 一1 ) b 次( m + t + 1 ) 一圈为一条( 2 ( m + t ) 2 + 2 m ( m + t ) 一3 m 一2 t ，4 m + 2 t 1 ) 一途径。 情形3 ：顶点i ( 驹) 在1 _ 2 _ 叶m 一1 上，顶点j ( 或i ) 在r a + t + 1 _ _ 2 r a + t 上。 此时0 b 2 , t r 2 m + t 一1 。故2 7 n + 亡+ r 一( m + t ) 6 o ，2 m + 亡一1 一r + ( 仃l + t 一1 ) 6 0 。则 从i 沿到歹，经过2 m + t + r 一( m + t ) 6 次( m + ) 一圈，2 m + t 一1 一r + ( m + 一1 ) 6 次( 仇+ + 1 ) 一圈 为一条( 2 ( m + 亡) 2 + 2 m ( m + t ) 一3 m 一2 t ，4 m + 2 t 一1 ) - 途径。 证毕。 2 2 指数集及极图刻划 本节将给出。类型2 的指数集，并对指数达到上下界的极图进行刻划。 引理2 2 1 设d d m t 是类型2 ，0 z m 一2 ，1 可m ，且暑， z 。如果z _ z + 1 和m + t + y _ m 十+ 秒+ l 是蓝弧( 若z = 0 ，规定z = r n + t ；若可= m ，规定m + t + y + l = 仇) ， 其它都是红弧，那么e x p ( d ) = 2 ( m + t ) 2 十2 ( y z ) ( 仇+ t ) 十 一z ) 一1 。 i 正d f l ：先证明e x p ( d ) 2 ( r e + t ) 2 + 2 ( 矽一z ) ( m + 亡) + ( 耖一z ) 一1 。设( 允，后) 为一对非负整数，使 得d 的每对顶点( z ，歹) 都有一条从i n j 的( 九，七) 一途径。取i = 歹= m ，则存在非负整数u 和u 使 得 ”m ” 再取i = z + 1 ，歹= m + t + ，那么从i 到j 的每条途径都可以分解成从i 到