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

中北大学学位论文 摘要 图论是组合数学中的一个重要分支。在许多领域，诸如物理学、化学、运筹学、计算机 科学、信息论、控制论、网络理论、社会科学以及经济管理都有广泛的应用。 矩阵a 可以与它所对应的伴随有向图d ( 以) 建立对应关系，因此可以利用图论的知识来 解决非负矩阵的一些问题。本文主要研究了具有一定代表性的一类含有两个圈的双色有向 图本原指数问题。 主要内容为： 第一章概述图论的发展，介绍一些基本知识以及本原指数的国内外研究概况，提出本 文的所做的工作。 第二章考虑一类特殊双色有向图d ，d 的未着色图含有m + n 个顶点且包含两个圈，圈 长分别为m 和n ，其中m 孔。证明了_ d 的本原性，借助逆矩阵找到了d 的指数上界，最后刻 划了极图。 第三章考虑了一类特殊的双色有向图，它的未着色图有r e + n - 3 个顶点，包含一个m 一圈 和一个舻圈，给出了本原条件和指数上界，并对极图进行了刻划。 关键词：本原指数，本原条件，双色图，指数上界，极图 第1 页 中北大学学位论文 a b s t r a c t g r a p ht h e o r yi sab r a n c ho fc o m b i n a t o r i a lm a t h e m a t i c s i th a sb e e nw i d e l ya p p l i e d i nm a n yd i f f e r e n tf i e l d s ，s u c ha sp h y s i c s ，c h e m i s t r y , o p e r a t i o nr e s e a r c h ，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 s ，n e t w o r kt h e o r y , s o c i a ls c i e n c ea sw e l la se c o n o m i c a lm a r l - a g e m e n t t h em a t r i xa c 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 d g 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 f g r a p ht h e o r y i nt h i sa r t i c l e w ec o n s i d e rac 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 s 诵t ht w o c y c l e s i t sp r i m a r yc o v e r a g ei s ： i nc h a p t e rl ，f i r s t l y , w eo u t l i n et h eh i s t o r yo fd e v e l o p m e n to ng r a p ht h e o r y s e c o n d l y , w ei n t r o d u c es o m ee l e m e n t a r yk 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 f t h e p 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 sdw h o s eu n c o l o r e dd i g r a p h h a sm+nv e r t i c e sa n dc o n s i s t s o fo n em - c y c l ea n do n en - c y c l e ，w h e r em 礼s o m e p r i m i t i v ec o n d i t i o n sa r ep r o v e d w ef i n dau p p e rb o u n do nt h ee x p o n e n t sb 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 w o - c o l o r e dd i g r a p h 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 h o s eu n c o l o r e dd i g r a p hh a s 竹l + n 一3v e r t i c e sa n dc o n s i s t so fo n em - c y c l ea n do n en - c y c l e w eg i v es o m ep r i m i t i v e c o n d i t i o n sa n dau p p e rb o u n do nt h ee x p o n e n t s a tl a s t ，w eg i v et h ec h a r a c t e r i z a t i o n so f e x t r e m a lt w o - c o l o r e dd i g r a p h s k e yw o r d s ：e x p o n e n t ，p r i m i t i v ec o n d i t i o n ，t w o - 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 第1 i 页 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行 研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：盈虚日期：2 边喹盂剧旦 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包括：学校 有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、 缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借 阅；学校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学 位论文的全部或部分内容( 保密学位论文在解密后遵守此规定) 。 签名：塾虚签名：蚴 导师签名： 日期：2 翌笪垒屋! 里 日期：皇盟垒姻! 鱼 中北大学学位论文 第一章引言1 弗一早 ji 苗 1 1图论的发展 图论是数学中的一个重要分支，它以图为研究对象。图论中的图是由若干给定的点及 连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点 代表事物，用连接两点的线表示相应两个事物之间具有这种关系。它的产生和发展历经了 二百多年的历史，大体上可以划分为三个阶段。 第一阶段是从1 7 3 6 年到1 9 世纪中叶。这时的图论处于萌芽阶段，多数问题是围绕着游戏 产生的，最有代表性的工作是著名的瑞士数学家l e u l e r 于1 7 3 6 年的k s n i g s b e r g 七桥问题。 他的那篇论文被公认为图论历史上第一篇论文。 第二阶段是从1 9 世纪中叶到1 9 3 6 年。这个时期中图论问题大量出现，如四色问题和h a m i l t o n 问题。同时出现了以图为工具去解决其他领域中的一些问题的成果。例如：“图”这个词 第一次出现在1 8 7 8 年的英国自然杂志中等。图论作为数学的一个新分支已基本形成。 第三阶段是1 9 3 6 年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面许 多离散型问题的出现，大大促进了图论的发展。图的理论及其在物理、化学、运筹学、计算 机科学、网络理论等几乎所有学科领域中各方面应用的研究都得到极大发展。 图论在许多领域，诸如物理学、化学、运筹学、计算机科学、信息论、控制论、网络理 论、社会科学以及经济管理各个方面都有广泛的应用。因此，受到世界数学界和工程技术界 越来越广泛的重视。 1 2本原矩阵及双色本原有向图的提出背景及概念 非负矩阵的组合理论是自上世纪5 0 年代以来兴起并发展迅速的一个数学分支，是组合 数学的一个重要研究方向。它用矩阵论和线性代数来证明组合性定理及对组合结构进行 描述和分类。同时，也把组合论的思想和论证方法用于矩阵的精细分析及揭示阵列的内在 组合性质。非负矩阵组合理论是研究那些仅依赖于矩阵的零位模式，而与元素本身的数值 无关的性质，它与图的某些性质有密切联系。非负矩阵，是符号模式矩阵的中的一种特殊 矩阵，扎阶定号无向图( 双向有向图) 。有向图s 称为定号图是指在图s 中的每一条弧标上特 第1 页 中北大学学位论文 定的符号”l 、一l ”或”+ 、一”。广义定号图s 是指在图s 中的每一条弧标上特定的符号”1 、一 1 、# ”或”+ 、一、# ”，其中# 为不定元，s 是矩阵a 的伴随有向图，即矩阵a = ( a 巧) 中元素符号 对应于s 中弧的符号。例如：a 1 2 0 表示从顶点1 到项点2 有一条符号为”+ ”的弧；a 1 2 0 。 使a 七 o 成立的最小尼称为a 的本原指数，记为，y ( a ) 或e x p ( a ) 。 本原矩阵是指单个矩阵的本原情况。 由于本原方阵的本原性及其本原指数只与方阵的零元素位置分布有关，而与非零元素 的具体数值无关。所以可以假设所有非零元素均为1 ，即所谓的( o ，1 ) 或布尔一方阵。下面我们 看两个具体的例子： 设方阵a = 11 00 00 o0 l1 01 ，贝, i j a 2 = l1 11 1l ll 01 0 o 110 0i i11l 1 的每个元素都大于零，所以矩阵4 是本原的，且，y ( a ) = 3 。 设方阵b = 010il0 o1 oo1 10 0 ，则b 2 = 10o o10 ，a 3 = ，b 3 = 22 2 2 1l 2 2 010 0 o1 1oo l2 11 11 12 。显然a 3 中 = b 。显然b 不可能 存在b 七 0 ，所以b 是不本原的。 矩阵a 可以与它所对应的伴随有向图d ( a ) 建立一一对应关系，即矩阵a = ( ) 中元素 值非零或零对应于d 中有没有弧。例如：a 1 2 0 表示从顶点l 到项点2 有一条弧；a 1 2 = 0 表示 从顶点1 到顶点2 没有弧；a l l 0 表示从顶点l 到顶点1 有一条弧，即顶点1 有环。利用这种对 应关系，则上例中方阵a 所对应的伴随有向图d ( 4 ) 如图1 2 1 所示。 第2 页 中北大学学位论文 图1 2 1 方阵b 所对应的伴随有向图d ( b ) 如图1 2 2 所示。 2 3 图1 2 2 若a 是本原方阵，贝i j d ( a ) 称为本原有向图。换言之，有向图d 称为本原的，如果d 的邻 接矩阵a 是本原的。对于( o ，1 ) 方阵a 的本原性及其本原指数的研究可以就可以转化为研究有 向图d ( a ) 的本原性及其本原指数这样一个等价的图论问题了。 孔阶本原矩阵对的本原指数提出背景f 2 2 】： 考虑2 维离散动力系统 z ( h + 1 ，k + 1 ) = a x ( h ，k + 1 ) + b x ( h + 1 ，七) ，h ，k z ，h + 后0 。( 1 2 1 ) 其中a 和口是n 阶非负矩阵，初始条件z ( h ，一九) ( z ) 是n 维非负向量。对非负整数h 和尼，定 义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 1 ) 式的解是始终严格正的 2 8 1 。 如果存在非负整数h 和k ，使得对h + k 0 ，有( a ，b ) ( ，七) 0 ，则称矩阵对( a ，b ) 是本原 的的，并且将h + k 的最小值定义为本原矩阵对( a ，b ) 的本原指数，i 己为e x p ( a ，b ) 。 设d 是一个有向图，d 的一条长为2 的途径是指连续的顶点序列1 ，l ，忱，仇+ l ，其中对 所有的i = 1 ，2 ，l ，d 中有从仇到仇+ l 的弧。如果 l ，v 2 ，v l + l 互不相同，则称该途径是 一条长为f 的路。如果u 1 = 研+ 1 ，则称为一条闭路或圈f 6 】。如果d 是包含红弧和蓝弧的有向 第3 页 中北大学学位论文 图，则称d 是一个双色有向图。n 阶矩阵对与双色有向图可以建立相应的对应关系。对每一 对非负矩阵对( 月，b ) ，其伴随有向图，记为d ( a ，b ) 。显然d ( a ，b ) 具有顶点1 ，2 ，佗，矩 阵a = ( o 巧) 中元素值非零或零对应于d 中有没有红弧，如果 0 ，则从顶点l 到顶点j 存在 一条红弧：矩阵b = ( 岵) 中元素值非零或零对应于d 中有没有蓝弧，如果b i j 0 ，则从顶 点i 到顶点j 存在一条蓝弧。 根据这种一一对应关系，我们可以在双色有向图和它的伴随非负矩阵对之间建立联 系，通过研究双色有向图的问题去解决非负矩阵对的问题。我们称双色有向图d 是本原 的，如果其伴随非负矩阵对( a ，j e 7 ) 是本原的，r d 的本原指数e 坤( d ) 既为( a ，b ) 的本原指 数e x p ( a ，b ) 。双色有向图d 是强连通的，如果d o e 每一对顶点( i ，j ) 都存在从i 至：u j 的途径。d o e 的一条途径u ，用r ( w ) n l b ( w ) 分别表示中红弧和蓝弧的条数，称u 为一条p ) ，6 ) ) _ 途径，u 的 分解为向量( r ) ，6 ) ) 或 ir ( u ) i l6 ( u ) l 一个双色有向图d 是本原的，当且仅当存在非负整数h 和后，且h + 七 0 ，使得d 中的每 一对顶点( i ，j ) 都存在从i n j 的k ) - 途径，h + 后的最小值定义为双色有向图d 的本原指数， 记为e x p ( d ) 。( h ，知) 一途径是指从i 至：l j j 的途径中包含h 条红弧和岛条蓝弧。 设c = ，y l ，能，m ) 是d 的圈的集合，定义d 的圈矩阵 r1 m ：i 吼眈啦- 1 铆l ， lb l6 2 b t 一1b li 其中啦，b i ( 1 i c ) 表示圈m 中的红弧和蓝弧的数目。m 是一个2 x 矩阵，它的第i 列是m 的分 解。 f 的c o n , t e n t ( i ? _ 为c o n t e n t ( m ) ) 定义为0 如果m 的秩小于2 ，否则定义为m 的所有非零2 阶 主子式的最大公因数。 关于本原矩阵a 的本原指数的研究最早始于1 9 5 0 年w i e l a n d t 的工作，给出了n 阶本原指 第4 页 中北大学学位论文 数的一般性_ j _ 二界e x p ( a ) ( n 1 ) 2 + l 。w i e l a n d t 所研究的图如图1 2 3 所示。 图1 2 3w i e l a n d t 图 一1 2 随着对本原指数的继续研究得到了一些重要的成果，在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 ) 的研究主要集中在以下四个方面 2 1 】： ( 1 ) 点指数：设是有向图d ，顶点i 的“点指数”e x p o ( i ) 是最小整数k ，使得从点i 到每一 点，有长不小于k 的途径。 ( 2 ) 第一类广义本原指数：对于有向图d 中的顶点 i = 1 ，2 ，佟 进行适当排序后有， e x p d ( 1 ) e x p d ( 2 ) e x p d ( n ) 贝j j e x p d ( 尼) ( d 中第七小的点指数) 为d 的第k 个广义本原指数。 ( 3 ) 第二类广义本原指数：设d 是本原有向图，1 k 佗一1 ，则称 i ( d ，k ) = m i n e x p d ( s ) l s y ( d ) ，i s i = 南) 为d 的k 重下广义指数。 ( 4 ) 第三类广义本原指数：设d 是本原有向图，l k n 一1 ，则称 f ( d ，k ) = m a x e x p d ( s ) l scy ( d ) ，1 8 i = 后 为d 的k 重上广义指数。 关于第一类广义本原指数已取得大量成果。我们的工作主要集中在广义本原指数的研 究，取得了一些很好的成果，解决了若干特殊类型矩阵的广义本原指数问题，包括广义本原 第5 页 中北大学学位论文 指数的最大值、最小值、指数集及极矩阵的刻划。在广义本原指数的研究中的一个问题是研 究各类本原有向图的广义本原指数的上界和指数集；另一个问题是研究各种特殊本原矩阵 类的指数集。目前国内外关于7 ( a ) 或e x p ( d ) 的研究，相当大部分的问题己得到或接近完全 解决( 【1 1 】【1 2 】f 1 3 】【1 4 】【15 】【1 6 】f 1 7 】f 3 1 】【3 2 】) 。 我们将7 ( a ) 或e x p ( d ) 推广到本原矩阵对的研究，这是一个全新的领域，国内外研究此 内容的文献不多，只有近期得到了一些成果及重要结论( 【2 2 】【2 3 】【2 4 】【2 5 h 2 6 】【2 7 h 2 8 】 【2 9 3 4 1 1 3 5 1 1 3 6 3 7 】1 3 8 】) 。例如：在文献【2 2 】中，得至1 t n 阶非负本原矩阵对本原指数最大值的 范围是 n s - 二5 n 2 ，3 n 3 + 2 丁n z 一- 2 n j , ，二，虿一j 且得到了三个等价结论： 设( a ，b ) 是n 阶非负矩阵对，且a ，b 均是非零矩阵，m 是( a ，口) 的伴随有向图d ( a ，b ) 的圈矩阵，则下列结论是等价的： ( 1 ) ( a ，b ) 是本原的： ( 2 ) d ( a ，口) 是强联通的，i t = 矛， m x ：z z c = z 2 ， ( 3 ) d ( a ，b ) 是强联通的，且c o n t e n t ( m ) = 1 。 在1 文献 2 3 2 4 3 4 】对未着色图为图1 2 4 ( 其中s 0 ，t o ) 的双色有向图的本原性及 本原指数进行研究，得到了一些重要结论。 图1 2 4d 的未着色图 在文献【2 3 】中考虑了t = 1 的情形，此时本原的情况下所对应的圈矩阵 m = 一讲 找到了指数上界并刻划了竹一1 2 _ _ s _ ( s + 1 ) _ ( s + 2 ) 中包含一条蓝弧的 第6 页 指数集，得到以下主要结论： 定理1 2 1f 2 3 若双色有向图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 。 定理1 2 2 【2 3 若双色有向图d 是本原的，r n _ 1 2 _ _ s _ ( s + 1 ) 一( s + 2 ) 中 不包含蓝弧，贝j e x p ( d 1 = 2 n 2 4 礼+ l 。 定理1 2 3 【2 a 若双色有向图d 是本原的，s = 0 r n _ 1 _ 2 _ 一s 一( s + 1 ) _ ( s + 2 ) 中包含一条蓝弧，贝u e x p ( d ) = 2 n 2 3 n + 1 ，此时双色有向图d 为w i e l a n d t 图。 定理1 2 4 【2 3 】若双色有向图d 是本原的，s 1 r n _ l _ 2 一_ s _ ( 8 + 1 ) _ ( s + 2 ) 中包含一条蓝弧，则d 的指数集g 2 n 2 + 2 ( 七一1 ) n - k k = 0 ，1 ，s ) u 2 扎2 - 3 n + l 。 在文献 2 4 1 中考虑了t = 2 的情形，此时本原的情况下所对应的圈矩阵 m ：l 叶1 g l ， i qq 一1 l 其中钆8 + 4 ，n = 2 q + 1 。找到了指数上界并刻划了极图，得到以下主要结论： 定理1 2 5 【2 4 】若双色有向图d 是本原的，则 。，。，f j n s - 2 。n 2 + 1 ，( 7 2 ) 2 矿“时2 e x p ( 驯 ( s # 3 ) n 2 - ( 3 s + 8 ) n + s + 3 ；s s q - - z ；。 定理1 2 6 【2 4 】若双色有向图d 是本原的，贝j j e x p ( d ) = 2 n 2 6 n + 2 当且仅当d 中存在一 条2 长的红路。 定理l 。2 7 【2 4 】若双色有向图d 是本原的，且s q 一2 贝t j e x p ( d ) = 芷业2 当且仅当枷园上 存在一条q + l 长的红路。 定理1 2 8 【2 4 】若双色有向图d 是本原的，且s q - i 则e x p ( d ) = ( s + 3 ) n 2 一( 3 s + 8 ) n + s + 3 当 且仅当d 中存在一条s + 3 长的红路，且所有红弧不间断。 在文献【3 4 】中考虑了t 3 ，s = o 的情形，此时本原的情况下所对应的圈矩阵 m = 死一a n n b 亡一6 ， 其中罟a 孔。给出了本原条件，找到了指数上界并刻划了极图，得到以下主要结论： 定理1 2 9 【3 4 若双色有向图d 是本原的，f i a ( n t ) 一b n = l 。 ( 1 ) 若6 = l ，则n 是奇数，t = 扎一2 ，口= 丁n + l ，j | e x p ( d ) 2 n 2 丁+ 3 n - - 1 。 第7 页 中北大学学位论文 ( 2 ) 若b 2 ，贝l j e x p ( d ) ( 扎一a ) ( 2 t m + 1 ) + 7 ；。 定理1 2 1 0 f 3 4 若双色有向图j 7 ) 是本原的，且a ( n t ) 一b n = 一1 。 ( 1 ) 若n a t l ，贝l j e x p ( d ) ( 佗一口) ( 2 轨一1 ) + 佗。 ( 2 ) 若n a t 一1 ，贝l j e x p ( d ) ( n q ) ( 2 6 扎一1 ) 。 定理1 2 1 1 【3 4 】若双色有向图d 是本原的，且口( n t ) 一b n = l 。 ( 1 ) 若6 = 1 ，贝j j e x p ( d ) = 丛芋当且仅当t _ ( t + 1 ) _ 一n _ l 为蓝路， 且孔圈上的a 长红弧连续。 ( 2 ) 若6 2 ，贝l j e x p ( d ) ( n 一口) ( 2 概+ 1 ) + n 当且仅当佗圈上的b 长红弧连续。 定理1 2 1 2 【3 4 1 若双色有向图d 是本原的，且a ( n t ) 一b n = 一l 。 ( 1 ) 若n a t 一1 ，贝i j e x p ( d ) = m a ) ( 2 b n 一1 ) + 佗当且仅当t 一( t + 1 ) 一一 佗_ 1 为红路，且孔圈上的礼一a 长蓝弧连续。 ( 2 ) 若n a t 一1 ，贝l j e x p ( d ) = ( 佗一a ) ( 2 b n 一1 ) 当且仅当n 圈上的礼一口长蓝弧连续。 在文献| 2 5 1 中对以下图1 2 5 进行了讨论，得到了以下重要结论， 图1 2 5 中由两个x x 向n ( n 3 ) 圈构成的双色有向图d ，且d 至少有一条蓝弧和一条红 弧。 图1 2 5 双向圈d 显然d 有两个伽圈和n 个2 圈，且d 的严格圈矩阵是以下矩阵的子矩阵 r1 l lo 2ab l il ， i 120 几一a 佗一bl lj 其中a 和b 是非负整数。 定理1 2 1 3 【2 5 】设d 是如图1 3 3 所示的孔阶双色双向圈，则 ( 1 ) 如果在d 中没有一个单色的2 一圈，则d 是本原的当且仅当n 是奇数，且每个加圈上红 弧的个数为掣或学。 ( 2 ) 如果在d 中至少有一双色2 圈和一单色2 一圈，则d 是本原的当且仅当n 是奇数。 第8 页 ( 3 ) 如果在d 中没有双色2 - 圈，则d 不本原。 由定理1 2 1 3 可知，d 是本原的当且仅当n 为奇数，且d 对应的严格圈矩阵m 7 为下列矩 旧n - - i 卦h a 计 ：兰他一a 口礼二6 ， ：兰丢仡二a 讫二6 。 定理1 2 1 4 【2 5 】图d 为如图1 2 5 所示的死阶本原双色双向圈，设馆= 2 q + lf i ：l1 口叶1l ，贝j j e x p ( d ) s2 ( q 2 + 口) = 下n 2 - - 1 。 l - 1 g + l 口 j 定理1 2 1 5 【2 5 】图d 为如图1 2 5 所示的扎阶本原双色双向圈，令珏= 2 9 + l 且 m ，：l 12口6 l ，贝j j e x p ( d ) 6 q 一1 ：3 n 一4 。 l - 1 0n o 佗一bj 定理1 2 1 6 【2 5 】图d 为如图1 2 5 所示的n 阶本原双色双向圈，设n = 2 口+ l 且 ：l 1 0 n6 l ，贝l j e x p ( d ) 轴一1 ：轨_ 4 0 【1 2 佗一口n b j 定理1 2 1 7 【2 5 】图d 为如图1 2 5 所示的n 阶本原双色双向圈，设他= 2 q + 1 且 ：l 1 02。6 l ，贝l j e x p ( d ) 6 q - 1 ：轨“ i 12 0n 口住一b l lj 定理1 2 1 8 2 5 图d 为如图1 2 5 所示的扎阶本原双色双向圈，设礼= 2 9 + 1 3 ，那么 ( 1 ) 如果佗25 ，贝j e x p ( d ) 2 ( q 2 + q ) = 华，且等号可以成立。 ( 2 ) 如果竹= 3 ，贝1 e x p ( d ) 5 ，且等号可以成立。 1 3本原矩阵簇与多色本原有向图 珏阶本原矩阵簇的本原指数提出背景【8 】 类似于2 维离散动力系统，可以将一个纯阶珏簇矩阵a = ( a 1 ，a 2 ，a 七) 考虑为维离散 动力系统z ( n ，i 2 ，i 是) ( i 1 ，i 2 ，i k z g i l + i 2 + + l 鬼2o ) 。该系统由初始条件 和递归公式 z ( i l ，i 2 ，i 七) ( n + i 2 + + i k 0 ) 第9 页 中北大学学位论文 a ：( i l + 1 ，t 2 + l ，歃+ 1 ) = a l z ( i l ，i 2 + 1 ，i 七+ 1 ) + a 2 z ( i l + 1 ，i 2 ，i 3 + 1 ，t 七+ 1 ) + + a k x ( i l + 1 ， 2 + 1 ， 七) 所控制，其中x ( i l ，i 2 ，i 豇) 是死维非负向量。 设a = ( a l ，a 2 ，a 七) 为佗阶非负矩阵簇，q = ( o t l ，a 2 ，口七) 是k 维非负整数组，a 表 示所有q 1 个a 1 、q 2 个a 2 、o t 七个a 之和。例如： a ( 1 , 1 , - - 3 ) = e a n a 2 a 让。 如果存在七维非负整数组o t ，使得a q 0 ，则a 是本原的，使得 0 的o t l + o t 2 + + a 耙 的最小值定义为本原矩阵簇a 的本原指数。本原矩阵簇即是本原矩阵对的推广形式。 一个着k 种颜色的有向图g 是由k 簇子图g l ，g 2 ，g 七组成的，其中g hg 2 ，g 知将g 中的弧分割成七个非空子集。我们认为g f 在g 中着第i 种颜色，类似于g 是本原的观点，我们 可以说着k 春e l , 颜色的g 1 ，g 2 ，g 知是七本原的，如果存在一组正整数r l ，r 2 ，使得g 巾的 任意顶点对( 乜，u ) ，有从珏到u 的途径，即恰好有玩条弧着第i 种颜色，其中i = l ，2 ，忌。 我们可以利用矩阵来判断一个特殊的着七种颜色的有向图是否k 本原。假设一个本原有 向图g 是由k 种颜色g l ，g 2 ，g 七组成的，g 中的圈用c l ，c 2 ，c l 表示，建立尼x2 矩阵，则 圈矩阵 a f = m l l m 1 2 m t ( t 一1 ) r o l l m 2 1 m 2 2 m 2 ( t 一1 ) m 2 1 i n k li n k 2 m k ( t 1 ) k u 其中m i j ( 1st 尼，1 歹f ) 表示圈勺中着第沸p 颜色的数目。m 的c 觎e 佗( 记为c 帆e 疵( m ) ) 定义为0 如果m 的秩小于忌，否则定义为m 的所有非零七阶主子式的最大公因数。 显然，七= 1 时即为本原矩阵的概念；后= 2 时即为本原矩阵对的概念。因此，非负本原 矩阵簇是本原矩阵对和本原矩阵的推广。 令g 是一个本原有向图且g l ，g 2 ，g 凫是g 的惫种颜色，那么g 是惫本原的当且仅当矩 阵m 的七x 七阶子式是互素的【9 】。例如：有向图g 的圈矩阵 r1 m ：l1 2 ”2i ，= f 。 l ， f 58 1 3 一歹l 第1 0 页 中北大学学位论文 其中歹0 。那么此时圈矩阵 彳的2 阶主子式为别为一2 ，3 一町和1 0 - l o j 。显然，一2 和3 6 j 互 素，因此有向图g 是2 本原的。 本原矩阵簇关于非负本原矩阵簇的研究，国内外这方面的文献相当少，只取得的少部分 成果。例如：在文献f 8 1 中，给出了n 阶非负本原矩阵簇的本原指数最大值估计为o ( n 1 ) 。在 文献【9 1 中，证明了任意本原有向图均存在2 着色是2 本原的。进一步，利用反证法对k 4 时， 通过构造例子证明了含有k 个圈的本原有向图着克种颜色不是k 本原的。最后给出了含有三个 圈的三色有向图的本原条件的一个猜想： 若g 是含有三个圈的本原有向图，三个圈c 1 ，q ，g 的圈长分别为z l ，f 2 ，z 3 ，令f l ，f 2 ，1 3 的最 大公因数是g ，则三色有向图g 所对应的矩阵 m = 满足行列式d e t ( m ) = 夕。 口 z z 1 一a x b 可 1 2 b y c z z 3 一c z 1 4本文主要的工作 本文研究2 本原的的本原指数，即研究双色有向图本原指数，选取了几类具有一定代表 性的特殊有向图，分别选取了含有两个不同圈的双色有向图，进行了分别的研究。 内容如下： 第二章考虑一类特殊双色有向图d ，d 中含有( 2 n t 一2 ) 个顶点且包含两个圈，圈长分 别为馆和n t ，其中亡( n 一2 ) 。证明了d 的本原性，并且找到了d 的指数上界，最后刻划了 极图。 第三章考虑了一类特殊的双色有向图，它的未着色图有m - t - n - - 3 个顶点，包含一个m 一圈 和一个俨圈，给出了本原条件和指数上界，并对极图进行了刻划。 在结束语中，概括了本文研究的问题，解决了的问题，并且提出了本文可以继续探讨的 问题。 第1 1 页 中北大学学位论文 第二章一类双色有向图的指数上界 设d 是一个有向图，d 的一条长为z 的途径是指连续的顶点序列1 ，l ，v 2 ，仇+ l ，其中对 所有的 = 1 ，2 ，f ，d o e 有从v i 到仇+ 1 的弧。如果 l ，忱，v t + l 互不相同，则称该途径是 一条长为f 的路。如果u l = 切+ 1 ，则称为一条闭路或圈。如果d 是包含红弧和蓝弧的有向图， 则称d 是一个双色有向图 本章研究一类特殊双色有向图d ，它的未着色有向图如图2 所示。d 中含有( 2 n t 一2 ) 个 顶点且包含两个圈，圈长分别为n 和n t ，其中t ( 佗一2 ) ，则d 的圈矩阵可写为 4 6 l ， n t bl j + 3 佗一t 一4 n 一2 佗一12 n t 一22 n t 一3 图2 未着色有向图d 2 1本原条件 ( 2 1 ) 引理2 1 1 一个至少包含一条红弧和一条蓝弧的双色有向图d 是本原的，当且仅当d 是强连 通的，且c o n t e n t ( m ) ：1 定理2 1 2 双色有向图d 是本原的，当且仅当o ( 佗t ) 一b n ：士1 1。i 证明：显然，d 是强连通的，d e t ( m ) ：j 口 6 i ：口( n 一) 一b n ，由引理2 1 1 可 l n on t b l 得，d 是本原的当且仅当c o n t e m ( z ) = 1 ，且o d e t ( m ) = - t - 1 。定理得证 第1 2 页 n 口 一n p。l | |m n 一 0 n 一2 中其 中北大学学位论文 引理2 1 3 若双色有向图d 是本原的，则g c d n ，n t = l ，其中g c d n ，n t ) 表示扎与n 一的 最大公因数 证明：因为d e t ( m ) = 理得证 n an t b ab nn t = 士l ，所以g c d n ，佗一t ) = 1 引 唯 陲善 ( 2 2 ) ( 2 3 ) 瞄- 皿4 ， 玑x i + + ，1 一- - 坎x i ：= 礼n 一。t = 。，士，土2 ( 2 5 ) 二，且对于 = 0 ，i l ，4 - 2 ，有而1 和钆佗成立 i ) 当茁t = 1 时，( 礼一亡) 1 一n y i = 1 ，h 1 n y i = n t 一1 ，n o 犰= 竺 1 ，这与玑是 整数解矛盾； i i ) 当以= 竹时，m t ) 扎一n y i = 1 ，即n ( 死一t 一欢) = l ，而协= 孔一t 一磊1 ，同理矛盾 所以戤1 且觑n ，( 2 5 ) 式成立 第1 3 页 中北大学学位论文 由( 2 5 ) 式得，存在唯一的整数i ，设为西，使得 2 ( n - - z t 如) x i o 礼- - 一n y l i 。= l ， 则l = ( n - t ) 。z i 0 - 1 钆一t 1 又因为( n t ) z 幻一n = 1 ，所以札( z 钿一纨。) = 1 + 纽i 。，则 1 x i o - - = 半g 取z 南= a ，y i 。= b ，则( 2 2 ) 式成立 ( 2 ) 因为n ( n t ) 一b n = 1 ，显然有- a ( n t ) + b n = - 1 ，取 a = 竹一d ，5 = 礼一t b ( 2 6 ) 则有 - 1 = 一( 佗一a ) ( 佗一t ) + ( 扎一t 一6 ) 钆= - n ( n t ) + a ( n t ) + 钆( 他一t ) 一b n 艮p a ( n t ) 一b n = 一1 根据( 2 6 ) 式，显然有1 五n 一2 ，1sb n t 一1 所 以o a b = 礼一a 一( n t b ) = t 一( a b ) t 一1 ，即( 2 3 ) 式成立 ( 3 ) m ( 2 6 ) 式得，a + 五= n ，b4 - b = n t 设5 = a ，则有( b b ) n = 2 ，显然矛盾， t i p ( 2 4 ) 式成立引理得证 定理2 1 5 若双色有向图d 是本原的且圈矩阵为( 2 。1 ) 式，其中等a 钆那么a ，6 是唯一的， 且a ，6 满足以下关系式 a ( n t ) 一b n = 1 或a ( n t ) 一b n = - 1 詈 口锄 ( 2 7 ) 1 b 扎一t 一1 1 a bst 下面对双色有向图d 分两种类型讨论：类型1 ，弧礼_ 1 是红的；类型2 ，弧n _ l 是蓝的 第1 4 页 中北大学学位论文 2 2指数上界 定理2 2 1 若双色有向图d 属于类型1 ，且本原，则 e x p ( d ) 礼( n - t - b ) ( 0 + 卜1 ) 札( n “) ( 2 俨卜n _ ( 炉( 礼一) 幻岫= ib n ( 2 n t 一口一b ) 一n ( n t b ) + ( 傩一t ) ( n a ) ( n + b 一1 ) ，n ( n t ) 一研 = 一1 证明：根据定理2 1 5 ，可设d 的圈矩阵为( 2 1 ) 式且满足( 2 7 ) 式对d 中的任意一对顶点( i ，歹) ， 记是从涯吣的最短路，r ) = r ，b ( p u ) = s 则r a + b 一1 ，s 2 n t a b 考虑下 面两种情况： 情况一： a ( n t ) 一b n = 1 只需证明对d 的任意一对顶点( i ，j ) ，都有一条( n 一t 一6 ) ( n + b 一1 ) + 6 ( n ( 2 他t a b ) 一( n 一口) ) ，( n 一口) ( 礼一t 一6 ) ( n + b 一1 ) + ( 扎一t b ) ( a ( 2 n t a b ) 一( 他一口) ) ) 一途径 取p l = ( 礼- t - b ) ( a + b - 1 ) 一( n - t - b ) r + b s ，p 2 = a ( 2 n 一一a b ) 一( n a ) + ( n 一口) r a s 因此，从顶点i 出发，沿到顶点j ，转舻圈p 1 次，转( n t ) 一圈，2 次的途径有分解 ： + p t n a 口 + p z n b 。一6 = l 口( 孔一t 一6 ) ( o + b 一1 ) + b ( a ( 2 n t a b ) 一( n o ) ) i i ( 铭一o ) ( 礼一t 一6 ) ( o + b 一1 ) + ( n 一一6 ) ( 口( 2 礼一t o b ) 一( n o ) ) i 显然，p l 0 ，p 2 0 当r = a + b 一1 时，s o ；s = 2 n t a 6 时，r 1 此 时，必包含弧n _ 1 以e x p ( d ) sa ( 他一t 一6 ) ( g + b 一1 ) + 6 ( o ( 2 礼一t a - 一b ) 一 ( 几一n ) ) + ( 佗一口) ( n t 一6 ) ( o - 4 - b 一1 ) + ( n t b ) ( a ( 2 n t a b ) 一( 他一8 ) ) = n ( n t 一6 ) ( 口+ b 一1 ) + n ( 佗一t ) ( 2 n t a b ) 一( n o ) ( n 一亡) 情况二： 口( n t ) 一i r n = 一1 只需证明对d 的任意对顶点( i ，歹) ，都有一条( a ( b ( 2 n t a b ) 一( n t 一6 ) ) + 6 ( n 一 ) ( o + b 一1 ) ，( 佗一a ) ( b ( 2 n t a b ) 一( 佗一t 一6 ) ) + ( 扎一t 一6 ) ( 佗一n ) ( o + b 一1 ) ) 一途径 取p l = b ( 2 n t a - b ) 一( n 一一b ) + ( n t