（运筹学与控制论专业论文）图的正交因子和随机正交因子分解.pdf

原创j 蛙声嬲 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 龟含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究终基羹要贡献的个人移集体，均毯在文中| 丛明确方式褥哽。本人完 全意识到本声明的法律责任赡本人承担。 论文作者签名：蛰甄 日期：迎；：延f 2 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校傈留袋向国家有关部f 了或袄- 构送交论文的复印件帮电子敝，允许论 文被套潮帮氆阕；本人授投出东大学可以将本学嫂论文懿全都或部分 内容编入有关数据库避行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 f 保密论文在解密盾应遵守此规寇) 论文作者签名：塑重一导师签名： 山东大学硕士学位论文 图的正交因子和随机正交因子分解 冯丽 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 中文摘要 本文考虑的图均为有限无向简单图对于一个图g ，我们用v ( c ) 和e ( g ) 分别表示它的顶点集和边集对任意的z y ( g ) ，我们用d g ( 石) 表示正在g 中 的次数设9 和，是定义在v ( g ) 上的两个整数值函数且对任意的正y ( g ) ，有 9 ( z ) ，( z ) 则图g 的一个( 9 ，) 一因子是指g 的一个支撑子图f 使得对任意的 。y ( g ) ，有g ( z ) d f ( t ) s ，( 芏) 如果对所有的z y ( g ) ，有9 ( 芷) = 口，( x ) = 6 ， 则该( g ，i ) - 因子称为g 的一个【o ，卅一因子；如果9 ( z ) = ，( z ) ，则该( g ，) 一因子 称为g 的一个，一因子；如果9 ( z ) = ，( 霉) = k ，则该( g ，) - 因子称为g 的一个 一因子如果一个图g 本身是一个白，) 一因子，则称g 为一个( 9 ，) 一图类似 地，可以定义【a ，6 】一图，一图和k 一图等令日是g 的一个子图，如果日本身 是一个( g ，) 一图，则称日是g 的一个( g ，) 一子图类似地可定义g 的 a ，讲一 子图，一子图和k 一子图图g 的一个( 9 ，) 一因子分解，= 日，b ，最 就 是将g 的边集e ( g ) 分成边不交的( g ，) 一因子f l ，如，最类似地，可以定义 【0 ，6 卜因子分解，一因子分解，后一因子分解等若日是图g 的一个子图，如果 g 的因子分解芦= 最，乃，最 满足f e ( h ) n e ( 墨) f = i ( 2 f 七) ，则称， 与日正交很明显，g 的因子f 如果有f e ( h ) n e ( f ) i = 1 ，则f 与日正交g 的有k 条边的子图称为g 的女一子图若是图g 的一个k r - 子图，g 的一个 ( g ，i ) - 因子分解，= f 1 ，如，f k ，如果满足i e ( h ) n e ( 只) j = r ( 1 i 七) ， 则称，与日r 一正交如果对边集e ( h ) 的任意划分 a 1 ，a 2 ，a ) 满足 j a i i = r 存在一个( g ，i ) - 因子分解，= f l ，尼，f k ) ，使得a 只，1 is k ， 则我们称g 有一个( g ，) 一因子分解随机r 一正交于日可以看出，随机1 一正 交等价于l 一正交，1 一正交也称为正交其它定义和术语可见文献 18 】 图的因子理论是图论中研究的主要问题之一自从t u t t e 分别于1 9 4 7 年和 1 9 5 2 年给出了因子理论的两个基本定理后，尤其是从l l o v d s z 在1 9 7 0 年给出了 ( g ，) 一因子存在性的判定准则后，对图的因子的研究才逐渐活跃起来图的正交 因子分解问题是近年来由b a l s p a c h 等人提出的新闻题本文主要讨论了图的正 交因子分解问题，对随机正交因子分解也稍有研究本文第一章简单介绍了因子理 论和正交因子分解理论的发展历史和背景；第二章给出了( m g + k 一1 ，m ，一女+ 1 ) 一 图中正交于r 个顶点不相交子图的边不交的( g ，) 一因子存在性的充分条件；第 三章研究了在二分图中存在与r 个顶点不交的k 一子图正交的( g ，) 一因子的一 1 山东大学硕士学位论文 个充分条件第四章对图g 存在与r 个边不交的k 一子图正交的( 9 ，) 一因子的 一个充分条件讨论；第五章研究了二分( m g + k ，m ，一) 一图g 中随机正交因子 分解存在性的充分条件 a l s p a c he ta 1 c 1 7 l 提出下面的问题：给出g 的子图日，是否存在的一个具 有某些性质的因子分解，正交于日? 刘桂真教授和李国君教授 1 9 】证明了对任 意( m g + m 一1 ，m ，一m + 1 ) - 图有一个( g ，i ) - 因子分解正交于k 个顶点不交 的g 的m 子图，并引用了如下结果 引理2 1 1 【2 0 1 设g = ( y ( g ) ，e ( g ) ) 是一个图，9 和，是定义在顶点集 v ( g ) 上的两个整数值函数，且对所有的x v ( g ) 有9 ( z ) ，( z ) ，则图g 有一 个( 9 ，) 一因子当且仅当对任意两个不交子集s 和? 有6 g ( s ，t ) 0 引理2 1 2 设g 是图，g 和，是定义在顶点集v ( g ) 上的两个整数值函 数，且对所有的z v ( a ) 有0 9 ( z ) ，( 。) d e ( x ) ，e 1 和易是e ( g ) 的不交 边子集，则g 有一个( g ，1 ) - 因子f 使得易目：f ) e 2 n e ( f ) = 0 当且仅当 对任意两个不交子集s 和t ，有 如( s ，t ) = d a s ( t ) 一g ( t ) + ( s ) 口+ 卢 成立 引理2 1 4 f 2 l 】对v ( a ) 的任意两个不交子集s ，t ，必有 5 a ( s ，丁m g ) = - ( t ) + 。( s ) + 等d g s ( 丁) + 去d g - t ( s ) 利用以上引理，我们得到以下几个结果 定理2 2 1 设图g 是( m g + k - l ，m ：- k + 1 ) - 图( 1 k m ) ，g 和，是定义 在顶点集v ( a ) 上的两个整数值函数，满足对所有的。v ( a ) 有r 譬( 。) ，( 。) ， 则g 有一个( p ，g ) 一因子日使得蜀e ( f 1 ) 且饬nf ( f 1 ) = 0 定理2 2 2 设g 是一个( m g + k 一1 ，m ，一k + 1 ) 一图( 1 k5m ) ，g 和，是 定义在顶点集v ( a ) 上的两个整数值函数，使得对所有的z y ( a ) 有rs9 ( z ) ，( 。) 设日1 ，尻，珥是g 的k 一子图，满足当i j 时，y ( 甄) n 矿( h j ) = o 则g 有k 一1 个边不交的( 9 ，) 一因子正交于皿( t = 1 ，2 ，r ) 2 山东大学硕士学位论文 对二分图，刘桂真教授【2 2 1 证明了对二分( m g + m 一1 ，m ，一m + 1 ) - 图g ， 如果对所有的x v ( a ) 有；冬g ( 。) ( 1 ) 成立，则g 有一个( g ，) 一因子分解 正交于g 的k 个顶点不交的m 一子图1 9 9 8 年她给出了一个图存在一个含有 e 。不含易的( 9 ，) 一因子的充要条件，这是我们主要结果证明的核心 引理3 1 1 p 2 】设g = ( x ，e ( g ) ) 是一个二分图，g 和，是定义在顶点集 y ( a ) 上的两个整数值函数，使得对所有的z v ( a ) 有0 9 ( z ) ，( 茁) 设置 和岛是边集e ( a ) 的两个不交子集，则图g 有一个( g ，f ) - 因子使得e l e ( r ) 且岛n e ( f ) = 0 当且仅当对任意两个不交子集s 垦x 和t y ， 且 1 l g = 7 1 0 ( s ，t ；9 ，) = f ( s ) 一g ( t ) + d e s ( t ) s + 3 t 仇g = t g ( s ，t ；g ，f ) = f ( t ) 一g ( s ) + d a t ( s ) o z t + 3 s 在此结果的基础上，我们有以下结论 定理3 2 1 设g 是二分( m g + k ，m ，一k ) 一图( 1 k m ) ，对所有的 x v ( g ) 有孚s9 扣) ，( z ) ，这里r 1 ，r 2 ，3 ，则g 有一个( p ，g ) 一因子f l 使得e l e ( 凡) 且e 2 n e ( f 1 ) = 0 定理3 2 2 设图g 是二分( m g + k ，m r - k ) - 图( 1 k m ) ，g 和，是定义在 顶点集y ( g ) 上的两个整数值函数，满足对所有的z y ( g ) 有孚s9 ( z ) ，( z ) ， r21 ，r 2 ，3 设皿，凰，匝( r 1 ，r 2 ，3 ) 是g 的r 个女一子图，且当i j 时，有v ( 娥) n y ( 易) = 0 则存在g 的子图r ，r 有( g ，) 一因子分解正交于 皿( = 1 ，2 ，r ) 刘桂真教授和李国君教授在【1 9 】提出了：若 h 1 ，h 2 ，凰) 是g 的边不交 的m 一子图，则情况会如何? 对此，我们有结果如下 定理4 2 1 设g 是( m g + k ，m ，一k ) - 图( 1sk m ) ，g 和，是定义在顶点 集y ( g ) 上的两个整数值函数，满足对所有的。y ( g ) 有2 r j 1s 口( 岳) ，( z ) ， 则g 有一个( p ，q ) 一因子f 1 使得e 1 e ( f 1 ) 且e 2 n e ( f 1 ) = o 定理4 2 2 设g 是一个( m g + k ，m l - 女) - 图( 1 茎k m ) ，g 和，是定义在顶 点集v ( g ) 上的两个整数值函数，满足对所有的z y ( g ) 有2 r 一 9 ( 口) ，( z ) 3 山东大学硕士学位论文 设日l ，飓，珥是g 的女一子图，满足当i j 时，e ( 凰) n e ( 马) = 0 则g 有女个边不交的( g ，) 因子正交于皿( i = l ，2 ，r ) 此外，在本文的第五章，我们还稍微讨论了图的随机正交因子分解，得到了 以下结论 定理5 2 1 设g = ( x ，y ) f ( g ) ) 是一个二分( r a g + k ，r a f k ) - 图( 1 m ) 且r 茎9 ( z ) ，( z ) ，则g 有一个( p ，q ) 一因子f 使得e l 冬e ( f 1 ) 且 岛n e ( f 1 ) = d 定理5 2 2 设g 是一个二分( m g + k ，, n f - k ) - 图( 1 曼 仇) g 和，定义在 v ( g ) 上的两个整数值函数，且对所有的z v ( g ) ，有rs9 ( z ) ，( ) ，h 是g 的 一个r j c 一子图贝4 g 有一个子图r ，兄存在一个( 9 ，r ) - 因子分解随机r 正交于日 全文共分五章 关键词：图；二分图；因子；正交因子；正交因子分解；随机正交因子分解； ( 9 ，f ) - 因子；( m 9 + k ，m ，一) 一图；m 一子图 4 山东大学硕士学位论文 0 r t h o g o n a lf a c t o r i z a t l 0 na n d r a n d o m i ? yo r t h o g o n a l f a c t o r i z a t l 0 no fg r a p h s f e n gl i ( i n s t o fm a t h & s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ) a b s t r a c t i nt h i s p a p e r ，a l lg r a p h su n d e rc o n s i d e r a t i o na r es i m p l e l e tgb eag r a p h w i t hv e r t e xs e tv ( g ) a n de d g es e te ( g ) f o re a c hv e r t e xoo fg ，d e n o t eb yd g ( o ) t h ed e g r e eo f 譬i ng l e tga n d | b et w oi n t e g e r - v a l u e df u n c t i o n sd e f i n e do i l v ( g ) s u c ht h a tf o re v e r yv e r t e x 茁o fg ，w eh a v e9 ( x ) ，( z ) t h e na ( g ，) 一 f a c t o ro fgi sas p a n n i n gs u b g r a p hfo fg s a t i s f y i n g9 ( 5 ) d f ( x ) ( z ) f o r a l l 。y ( g ) i f f o ra l l 。矿( g ) ，g ( x ) = 口，( x ) = b ，t h e na ( g ，) 一f a c t o ro f gi sa l s oc a l l e da n a ，6 】一f a c t o r ；i fg ( x ) = ，( z ) ，t h e na ( g ，) 一f a c t o ro fgi sa l s o c a l l e da n ，- f a c t o r ；i f9 ( ) = ，( z ) = ，w h e r e i sa ni n t e g e r ，t h e na ( 9 ，) 一f a c t o r o fgi sa l s oc a l l e dak - f a c t o r i np a r t i c u l a r i t y , i fgi t s e l fi s a ( g ，) 一f a c t o r ，t h e n gi sc a l l e da ( g ，) 一g r a p h s i m i l a r l y , w ec a nd e f i n e f a ，6 】一g r a p h ，一g r a p h a n d 一 g r a p he t c ，l e t 口b eas u b g r a p ho fg ，i fh i t s e l fi s ( 9 ，) 一g r a p h ，t h e nhi sc a l l e da ( g ，) 一s u b g r a p ho fg s i m i l a r l y ，w ec a nd e f i n et h e 【a ，胡s u b g r a p h ，f - s u b g r a p ha n d 一 s u b g r a p he t c a ( 9 ，) 一f a c t o r i z a t i o n ，= f l ，f 2 ，见) o fg i sap a r t i t i o no f e ( g ) i n t o e d g ed i s j o i n t ( g ，) - f a c t o r sf 1 ，f 2 ，- ，f k w ec a nd e f i n e o ，6 卜f a c t o r i z a t i o n ， ，- f a c t o r i z a t i o na n dk - f a c t o r i z a t i o nb ys u b s t i t u t i n g a ，h i - f a c t o r s ，一f a c t o r sa n dk f a c t o r sf o r ( g ，) 一f a c t o r si nt h ep r o c e e d i n gd e f i n i t i o n l e thb ea s u b g r a p ho f g a f a c t o r i z a t i o n 厂= r ，易，r ) o fg i so r t h o g o n a lt ohi fi e ( h ) n e ( 鼠) j = 1 ， l i k i np a r t i c u l a r ，af a c t o rf o f gi so r t h o g o n a lt ohi ff e ( h ) d e ( f ) f = l ，a s u b g r a p hw i t h 女e d g e s i sc a l l e da k - s u b g r a p h l e th b eak r s u b g r a p ho fa g r a p hg a ( 夕，) - f a c t o r i z a t i o n ，= f l ，f 2 ，f k ) i sr o r t h o g o n a lt oh i fi e ( h ) h e ( 只) l = rf o r1 i i f f o ra n yp a r t i t i o n a 1 ，a 2 ，- 一，a k ) o f e ( h ) w i t h a i i = rt h e r ei s a ( g ，) f a c t o r i z a t i o n ，= f 1 ，尼，最) o f gs u c ht h a ta e ，1si 七，t h e n w es a yt h a tgh a sa ( g ，) f a c t o r i z a t i o nr a n d o m l yr o r t h o g o n a lt oh n o t et h a t r a n d o m l y1 - o r t h o g o n a li se q u i v a l e n tt o1 - o r t h o g o n a la n d1 - o r t h o g o n a li sa l s oc a l l e d o r t h o g o n a l n o t a t i o n sa n dd e f i n i t i o n sn o tg i v e ni nt h i sp a p e rc a nb ef o u n di n 1 8 t h et h e o r yo fg r a p hf a c t o ri so n eo ft h em o s ti m p o r t a n tp r o b l e m so fg r a p h t h e o r y r e s e a r c ho i 1 f a c t o r sd i dn o tb e c o m e p o p u l a ru n t i la f t e rt u t t eg a v et h et w o 山东大学硕士学位论文 e s s e n t i a lt h e o r e m si n1 9 4 7a n d1 9 5 2 ，e s p e c i a l l ya f t e rl l o v d s zp o s e dt h es u f f i c i e n t a n dn e c e s s a r yc o n d i t i o nf o rag r a p ht oh a v e ( g ，) 一f a c t o r s o r t h o g o n a lf a c t o r i z a - t i o np r o b l e m sw e r ep r o v i d e db yb ，a l s p a c he t c i n1 9 9 2 ，i nt h i st h e s i s ，w em a i n l y d i s c u s so r t h o g o n a lf a c t o r i z a t i o np r o b l e m si ng r a p h s ，a n dm a k es o m er e s e a r c ho nr a n d o m l yo r t h o g o n a lf a c t o r i z a t i o n i nt h ef i r s tc h a p t e r ，w ei n t r o d u c et h eb a c k g r o u n d o ff a c t o rt h e o r ya n do r t h o g o n a lf a c t o r i z a t i o nt h e o r y i nt h es e c o n dc h a p t e r ，s o m e s u f f i c i e n tc o n d i t i o n sf o rt h ee x i s t e n c eo fe d g ed i s j o i n t ( g ，) 一f a c t o r so r t h o g o n a it o rv e r t e x d i s j o i n ts u b g r a p h si n ( m g + k 一1 ，m ，一+ 1 ) 一g r a p h sa r ep r e s e n t e d i n c h a p t e rt h r e e ，w ef o c u so nt h ee x i s t e n c eo fo r t h o g o n a l ( g ，) 一f a c t o r i z a t i o n si nb i p a r t i t e ( m g + ，m f 一) 一g r a p h s i nc h a p t e rf o u r ，w ep r o v i d eas u f f i c i e n tc o n d i t i o nf o r t h ee x i s t e n c eo fe d g ed i s j o i n t ( g ，) 一f a c t o r so r t h o g o n a lt ore d g e d i s j o i n ts u b g r a p h s i n ( m g + ，m f 一惫) g r a p h s 。i nt h el a s tc h a p t e r ，w ed i s c u s sr a n d o m l yo r t h o g o n a l ( g ，) 一f a c t o r i z a t i o no fb i p a r t i t e ( m g + k ，m 一) 一g r a p h s a l s p a c he ta 1 c 1 r l p r e s e n t e dt h ef o l l o w i n gp r o b l e m ：g i v e nas u b g r a p hh o f g d o e st h e r ee x i s taf a c t o r i z a t i o n o fgw i t hs o m ep r o p e r t i e so r t h o g o n mt oh j 。 l ia n dl i u ”】s h o wt h a te v e r y ( m g + m 一1 ，m ，一m + 1 ) 一g r a p hgh a sa ( g ，) 一 f a c t o r i z a t i o no r t h o g o n a lt o v e r t e xd i s j o i n tm s u b g r a p h so fg i nt h e i rp r o o f , t h e y u s e dt h ef o l l o w i n gr e s u l t s l e m m a2 1 1 d 。1l e tgb eag r a p ha n dl e tga n dfb et w oi n t e g e r - v a l u e d f u n c t i o n sd e f i n e do nv ( g ) ，s u c ht h a tg ( x ) ( x ) f o ra l lx y ( g ) t h e ng h a sa ( g ，) 一f a c t o ri f a n do n l y i f f o ra n yt w o d i s j o i n ts u b s e t ss a n dto fy ( g ) ，如( s ，t ) 0 l e m m a2 1 2 【2 1 】l e tgb eag r a p ha n dl e tga n d ，b et w oi n t e g e r v a l u e d f u n c t i o n sd e f i n e do nv ( a ) a n d0 g ( z ) ( x ) d a ( x ) f o ra l lx y ( g ) l e te 1 a n de 2b et w od i s j o i n ts u b s e t so fe ( g ) t h e ngh a sa ( g ，) - f a c t o rfs u c ht h a t e l e ( f ) a n de 2 n e ( f ) = 0 i fa n do n l yi f f o ra n yt w od i s j o i n ts u b s e t ssa n dt o f v ( a ) 略( s ，t ) = d a s ( t ) 一g ( t ) + ( s ) 。+ p l e m m a 2 1 4 【2 1 】f o r a n y t w o d i s j o i n ts u b s e t s s a n d to f y ( g ) ，6 a ( s ，r ；p ，g ) = n i ( t ) + 2 ( s ) + 2 导d g s ( t ) + 击d g r ( s ) b a s e do nt h e s el e m m a s ，t h ef o l l o w i n gr e s u l t sa x ea v a i l a b l e t h e o r e m2 2 1l e tgb ea n ( m 口+ 詹一1 ，m ，一k + 1 ) - g r a p h ( 1 k m ) ，l e t 6 山东大学硕士学位论文 ga n dfb et w oi n t e g e r v a l u e df u n c t i o n sd e f i n e do nv ( a ) s u c h t h a tr g ( x ) f ( x ) f o ra l l z v ( g ) ，t h e ng h a s a ( p ，口) 一f a c t o r 日，s u c h t h a t e 1 e ( e 1 ) a n d 岛n e ( f 1 ) = 0 t h e o r e m2 , 2 2l e tgb ea n ( m g + 一1 ，m ，一k + 1 ) 一g r a p h ( 1 k m ) ， a n dl e tga n d ，b et w op o s i t i v ei n t e g e r v a l u e df u n c t i o n sd e f i n e do nv ( a ) s u c ht h a t r g ( x ) ( x ) f o re v e r yx v ( g ) l e th 1 ，h 2 ，珥b ers u b g r a p h so f gs u c h t h a t | e ( 日1 ) = k ( 1 i r ) ，a n dy ( 皿) ny ( 马) = 0 ，w h e ni j t h e ngh a s k 一1e d g ed i s j o i n t ( g ，) 一f a c t o r so r t h o g o n a lt o 鼠f o r i = 1 ，2 ，r i nt h ec a s eo fb i p a r t i t eg r a p h s g u i z h e nl i u 2 2 】p r o v e dt h a t e v e r yb i p a r t i t e ( m 9 + m 一1 ，m y m + 1 ) 一g r a p hh a sa ( g ，) 一f a c t o r i z a t i o no r t h o g o n a lt okv e r t e x d i s j o i n tm - s u b g r a p h so fgi f ；9 ( z ) f o ra l l 。y ( g ) ，a n dk 1 i n1 9 9 8 ，s h e g a v ean e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o rab i p a r t i t eg r a p ht oh a v ea ( g ，) 一f a c t o r c o n t a i n i n ge xa n de x c l u d i n ge 2 ，w h i c hi se s s e n t i a lt ot h ep r o o fo fo u rm a i nr e s u l t s l e m m a3 1 1 【2 2 】l e tg = ( x ，y ，e ( g ) ) b eab i p a r t i t e g r a p ha n dga n d ，b e t w oi n t e g e r - v a l u e df u n c t i o n sd e f i n e do ny ( g ) ，s u c ht h a t0 g ( x ) f ( x ) f o r a l l z y ( g ) l e te 1a n de 2b et w od i s j o i n ts u b s e t so fe ( g ) t h e ngh a sa ( g ，) - f a c t o rfs u c ht h a te 1 e ( f ) a n d 历n e ( f ) = 0 i f a n do n l yi f f o ra l lt w o d i s j o i n t s u b s e t ss xa n dt yo fy ( g ) ， f i g = 7 l g ( s ，t ；g ，f ) = ( s ) 一g ( t ) + d a s ( t ) 0 5 + 岛 7 2 a = ，y 2 a ( s ，t ；g ，f ) = f ( t ) 一g ( s ) + d c r ( s ) a r + 卢s b a s e du p o n i t ，t h ef o l l o w i n gr e s u l t sa r ea v a i l a b l e t h e o r e m3 2 1l e tg = ( x ，e ( g ) ) b ea b i p a r t i t e ( m g + k ，m 一七) 一g r a p h ( 1 k m ) ，气三冬口( z ) ，( z ) ，w h e r er 1 ，r 2 ，3 ，f o ra l lz y ( g ) t h e ng h a sa ( p 】g ) 一f a c t o rf 1s u c ht h a te 1 e ( f 1 ) a n d e 2 n e ( f o = 0 t h e o r e m3 2 2l e tgb ea b i p a r t i t e ( m g + k ，m ，一女) g r a p h ( 1s 自 m ) ， a n dl e tga n dfb et w op o s i t i v ei n t e g e r - v a l u e df u n c t i o n sd e f i n e d0 1 2 v ( a ) s u c ht h a t 孚9 ( z ) ，( z ) f o re v e r y 。y ( g ) ，a n dr l ，r 2 ，3 l e t 儡，飓，珥b e 7 山东大学硕士学位论文 r s u b g r a p h so f g s u c ht h a t | e ( h d j = k ( 1 茎i r ) ，a n dv ( h i ) n v ( h j ) = 口，w h e n i j t h e nt h e r ee x i s t sas u b g r a p hr ，w h i c hh a sa ( 9 ，) 一f a c t o r i z a t i o no r t h o g o n a l t oh if o ri = 1 ，2 ，r i n 1 9 1 ，g u i z h e n l i ua n d g u o j u n l i a s k e d t h e f 0 1 1 0 w i n g q u e s t i o n s ：i f ( h 1 ，h 2 ， 凰) a r ee d g ed i s j o i n ts u b g r a p h s ， z , i l lt h er e s u l ts t i l lh o l d ? d o e s t h e r ee x i s tap o l y - n o m i a la l g o r i t h mf o rv e r i f y i n gt h a t ? f o ri t ，w eh a v et h ef o l l o w i n gr e s u l t s t h e o r e m4 2 1l e tgb ea n ( m g + k ，m f 一) 一g r a p h ( 1 m ) ，l e tga n d fb et w oi n t e g e r v a l u e df u n c t i o n sd e f i n e do nv ( a ) s u c h t h a t2 r i 1 兰g ( z ) ( x ) f o ra l l z y ( g ) ，t h e ng h a sa ，q ) 一f a c t o rf l ，s u c ht h a te 1 垦z ( f 1 ) a n d 局n e ( f 1 ) = 0 t h e o r e m4 2 2l e tgb ea l l ( m g + k ，m ，一女) 一g r a p h ( 1 曼七 m ) ，a n d l e t ga n dfb et w op o s i t i v ei n t e g e r v a l u e d f u n c t i o n sd e f i n e do nv ( a ) s u c ht h a t 2 r 一互1 9 ( z ) ，( z ) f o re v e r y 正y ( g ) l e th t ，4 2 ，耳b ers u b g r a p h s o f g s u c ht h a tl e ( 皿) 1 = k ( 1 i r ) ，a n de ( h i ) h e ( 妫) = 谚，w h e ni j ，t h e ng h a s ke d g ed i s j o i n t ( 9 ，) 一f a c t o r so r t h o g o n a lt o 风f o ri = 1 ，2 ，r i na d d i t i o n ，i nc h a p t e rf i v e ，w ea l s od os o m ew o r ko nr a n d o m l yo r t h o g o n a l f a c t o r i z a t i o na n do b t a i nt h ef o l l o w i n gr e s u l t s t h e o r e m5 2 1l e tg = ( x ，ve ( g ) ) b eab i p a r t i t e ( m g + k ，m ，一) 一g r a p h w i t h1 忌 m ，m 2a n dr5g ( x ) ，( 茁) t h e ng a d m i t sa 妇，口) 一f a c t o rfs u c h t h a te 1 e ( f 1 ) a n de 2 n e ( f 1 ) = 0 t h e o r e m5 2 2l e tgb eab i p a r t i t e ( m g + k ，m - 七) - g r a p h ( 1 k m ) ，l e t ga n dfb et w oi n t e g e r - v a l u e df u n c t i o n s d e f i n e do nv ( a ) s u c ht h a tr g ( x ) ，( z ) ， a n dl e thh ear k s u b g r a p ho fg t h e ng h a sas u b g r a p hr ，w h i c hh a sa ( g ，) 一 f a c t o r i z a t i o n sr a n d o m l yr - o r t h o g o n a lt o 日 k e yw o r d s ：g r a p h ；b i p a r t i t eg r a p h ；f a c t o r ；o r t h o g o n a lf a c t o r ；o r t h o g - o n a lf a c t o r i z a t i o n ；r a n d o m l yo r t h o g o n a lf a c t o r i z a t i o n ；( m g + k ，m ，一女) g r a p h ； m s u b g r a p h 8 第一章引言 图的因子理论是图论的一个重要分支，是图论中研究最活跃的课题之一对 因子理论的研究可追溯到一个世纪以前1 8 5 9 年，k e i s s 1 】证明了图。是1 一 可因子化图，1 8 9 1 年，j p e t e r s e n 2 】在考虑h i v e r t 【3 j 于1 8 8 9 年提出的一个代数 因子问题时，将其化为图的因子分解问题并且证明了每一个2 一连通的立方图有 1 一因子以及图g 是2 一可因子化图当且仅当g 是一个2 d - 正则图1 8 9 8 年， p e t e r s e n 4 给出了一个非平面，3 一正则，无割边的特殊图，该图无1 一因子分 解，这就是p e t e r s e n 图k 6 n i g 5 j 和h a l l 6 】分别于1 9 3 1 年和1 9 3 5 年得到著名的 k s n i g h a l l 定理，该定理解决了二分图的1 一因子存在性问题而t u t t e 7 】在 1 9 4 7 年给出的1 一因子存在性定理奠定了因子理论的基础1 9 5 2 年，t u t t e i s 】 给出了图有，一因子充要条件1 9 7 0 年，l l o v h s z 9 l 得到了图有( g ，) 一因 子的充要条件从此，因子理论的研究活跃起来后来，k h e i n r i c h ，刘桂真等 人【l o 】以及p f t a n s t e e 1 1 】在加上某些限制条件后，简化了l o v d s z 定理的表达 形式，并得到了一个图存在带有某些性质的( g ，) 一因子的充要条件从此，对 图的具有某些特殊性质的因子的研究逐渐多了起来关于因子方面的结果，可 参见j a k i y a m a 和m k a n o 1 2 j 发表在j o fg r a p ht h e o r y 上的一篇综述性文章 图的因子分解和正交因子分解问题有着广泛的实际应用背景，它与图论的 其它分支以及组合数学的某些分支密切相关例如图的边染色问题实际上也是 图的因子分解问题；拉丁方和r o o m 方的设计可以转化为图的正交因子分解等 可以说，自从有了对图的因子的研究就有了对图的因子分解的研究但这方面的 结果并不是很多m k a