（应用数学专业论文）基于图因子分解的几个问题.pdf

国防科学技术大学研究生院学位论文 摘要 图的因子理论是图论的重要分支之一，是图论研究中的最活跃的课题之一特别是图 的因子分解研究是一个引人注目的课题，它在网络设计和计算机科学中有着广泛的应 用目前，关于图的因子分解已有很多结论本文主要基于图的因子分解的如下几个问题 作了一些工作 1 完全图的因子分解问题本文研究了完全图的分支因子分解，分别给出了完全图k 。 的 局，品1 ) 因子分解、2 s 因子分解和当一，m 为合数时的 蠡k 曩卸1 ) ，) 或 恐。，卜1 m 因子分解、局。或以因子分解，以及完全图尬一l 的飓一l 因子分解和当”寸坍为合数时 的耳。或咙+ ，因子分解 2 图中具有推广的正交慨力因子分解一，正交b 力因子分解的子图问题本文在已 有结论的基础上作了进一步研究并改进了结果，证明了每个( 坍驴矾矿娜图g 含有一个子 图r ，使得且有一个b ，) 因子分解，正交于g 的任意给定的有打条边的子图，其中脚，t 和，是正整数且七 掰，占，1 本文还介绍了寻找( 厅学均，够如) 图中具有，正交嘛力因子 分解的子图的多项式算法 3 有向图的因子问题一方面，本文考虑了允许每个顶点上至多关联一条环但不含有 重弧的有向图，讨论了此类有向图的最小出入度条件与 ，川困子、带【口，川界的( 厂。；，+ ) 因 子以及七因子的存在性问题，并且举例说明在一定条件下所得结果是最好的：另一方面， 本文运用网络流知识讨论了有向图含有留，厂；矿，厂+ ) 因子、( ，。；，+ ) 因子的充要条件，并且 给出了求有向图中的瞎，厂；矿，+ ) 因子、( 厂；，+ ) 因子的多项式算法 4 无向图的定向问题本文运用网络流方法研究了图的定向问题，给出了图有俘，广； g + ，厂+ ) 定向( 定向图) 、( 厂；，+ ) 定向( 定向图) 的充要条件，并且给出复杂性为c 咿肼) 的 多项式算法求出图的 ，厂；矿，+ ) 定向的，或者判断出该图无俘，厂；矿，+ ) 定向 关键宇：图；有向图；因子：因子分解；流；多项式算法 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t t 1 l ef a c t o rm e o r yo fg m p h si s eo fn l em o s ti m p ( 咀a i l tb r a i l c h e so fg r a p h1 1 1 e o r y ii n p a n i c u l 甄t h es t i l d yo f f k t o r i z a t i o n si n 脚l l si sv e un o t i c e a b l ea l l dv e 巧l l s e f i l li i ld e s i 印o f n e t w o r k sa n dc o m p m e rs c i e n c e s of h r ，m a n yr e s u l t so nt l l ee x i s t e n c eo ff k 州z a t j o n si i lg r a p h s h a v e b e e np r o p o s e d i n l i sp a p e r ，t h em a i nc o n t r i b u t i o n sc a nb es 啪m a r i z c d 龃f o l l o w s f i r s t l y s o m ep r o b i e m so n 蠡c t o r i z a t i o n si nc o m p l e t eg r a p h sa r es m d i e d ag r e a tm a l l yn e w c o m p o n e n tf a c t o r i z a t i o n so fc 伽叩l e t e 肼p l l sa r ep r e s e n t e d w bp u tf 0 删a 盖乏，孓1 ) 一 f a c t o r i z a t i o na i l da2 i f a c t o r i z a t i o no f 如，a n da i l 飓肿l - f a c t 嘶z a t i o no f 娲时1 w h c n 盯_ r 川 i sac o m p o s i t en 啪b e r w e 垂v ea ( 局，墨_ 一1 西o r ( 岛。，( r - i 抑) - 州z a t i o n ，a n o r 以一 f 2 址t o r i z a t i o no f 如，a n da 仆1o r + l 一t o r i z a 廿o no f 局# 1 s e c o n d l y ，w ei n v e s t i g a t e 也ep m b l 咖o fs u b g m p l l s 埘t l lg e i l e r a l i z c do n h o g o n a lb ，) f 砬t o r i z a 6 0 n si 矗，0 r m o g o n a l 噱，) - f h c t 嘶刎o n si ng r a p h s 柚di m p m v em e p r e v i o u sr e s l l i t s n i sp r o v e dt l l a t 缸a n ys u b 铲a p h 日谢t l l 扫e d g e so fa i l ( 删油，够打) g m p hg ，t l l e r cc x i s t sa s u b g r a p hrw i t hab 厂) - f 诎o r i z a t i o n 卜o n h o g o n a lt ohw b e r e 埘，七a n d ，a f ep o s 试、屯i n t e g e r s w i t l l 肛锄a n d 反v ) r l f o ra l lv 取g ) f u m l e 加o r e ，i ti ss 1 1 0 w n 廿l a tt l l e r ea r ep o l y n o m i a l a l g o r i 也m sf b f6 n d i n gt h ed e s h df 如t o d 删o n s t h ，c h a p t e r4i sd e v o t e dt ot h ep r o b l 眦o f f a c t o r si nd i g r a p h s o nm eo n eh a n d ，w e d i s c l l s sn l em i l l i m 啪o u t d e g r e ea i l dt 1 1 em i l l i m u mi n - d e g r c ec o n d m o n sf o rad i g r a 】出t 0h a v ea 1 1 【口，6 】- f a c t o r ，a np ，6 】b o u n d e d ( ，；，+ ) - f a c t o fo ra 缸f a c t o rr e s p e c d v e l y a nd i 弘l p h sc o n s i d e r e d i nt l l i s c t i o na r ef i n i t ew i t h o u tm l l l t i p l ea r c sb u t 也ee x i s t e n c eo fa tm o s to n el o o pi n c i d e mo n 锄yv e r t e xi sp o s t i l l a 刚t h e 佗s l l l t si i lt l l i sc h 印t e ra r eb e s tp o s s i b l ei ns 哪es e n o n 也e “h e r h a n d ，w e 西v cn e c c s s a r ) r 锄ds 嘶c i e n tc o n d i t i o n sf o r 也ee x i s t e n c eo f ( 厂；厂 一f a c t o r so r 留，厂； g + ，+ ) 加t o r si nd i 黟a p h sa c c o r d i n gt ol l l e1 l l e o r yo f n e 帆o r k 丑o w s p o l y n o m i a la l g o r i 蚰sa r e p m v i d e d t of i n da i l ( 厂；，+ ) 一f 配t o r0 ra 留，厂；g 十，+ ) f a c t o r mad i 聊h f i n a l l y 血eo r i e n t i n gp r o b l 锄o f u n d i i e c t c dg r a p h sc a nb ed e a l t 诵mb yn o w sm e t l l o d s w c p r e s e n tn e c e s s a r ya n ds 谢五c i e n tc o n d i t i o l l sf 撕a 芦a p ht oh a v e 谚，；g + ，+ ) 一o r i e n 僦o no ra g ，厂；矿，+ ) 一o r i e n t c dg r a p h ，( 厂；，+ ) 一o r i e n t a t i o no ra i l ( 厂；，+ ) 一o “e n t e dg r a p h m o r c o v c r a p o l y n o m i a la l g o r i t h i n 、 d l i c he i m e rf i n d s 俘，厂；旷，+ ) - o r i e t a t i o no rs h o w st l l a to n ed o e sn o t e x i s tmd ( 刀2 研) o p e r a t i o n si sp r o p o s e d k e y w o r d s ：g r a p h ；d i 掣a p h ；f k t o r ；f 她t o r i z a t i o n ；n o w ；p o l y l l 哪i a la l g o r i t h m 第页 国防科学技术大学研究生院学位论文 图2 1 1 图2 _ 2 1 图2 2 2 图2 2 3 图2 2 4 图2 2 5 图2 2 6 图2 2 7 图2 2 8 图2 2 9 图5 - 2 1 图表目录 j 鼍j 9 尬，凰和凰的 恐，品1 ) 因子分解1 0 目，磁和风的2 晶1 因子分解1 1 玛的岛因子分解1 1 局8 的 ，玛，6 ) 因子分解1 2 局8 的因子分解一1 3 玛5 的壤因子分解1 4 恐4 的以因子分解1 5 恐4 的以因子分解1 5 蜀9 的3 组不同的分支因子分解1 6 发车安排示意图。4 4 第i i 页 独创性声明 y886 38 9 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特另4 加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目： 基王圈固王金整数且全回塑 学位论文作者签名：二组 日期：j 。5 年，1 月5 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借闭；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 基王图固王佥壁盟且尘问题 学位论文作者签名：鏖压! 酉! 作者指导教师签名：箱：丛 日期：) 弓年f f 月5 日 日期：渺，年”月加日 国防科学技术大学研究生院学位论文 第一章绪论 弘1 图论基本知识 1 1 1 图的基本概念 所谓一个图( 也称作无向图) g 是指一个有序三元组( h g ) ，顶g ) ，妫，其中以g ) o ， 以g ) n 联g ) = o h g ) 中的元素称为g 的顶点，而h g ) 则称为g 的顶点集；以g ) 称为g 的边集，其中的元素称为边；忱称为g 的关联函数，它是使g 的每条边对应于g 的无序 顶点对的函数 若图用g 表示，则它的顶点集和边集分别记为坎g ) ，耳回为了书写方便，以后我们 通常把图g = ( h g ) ，耳g ) ，砌简记为g = ( 坎回，以g ) ) ，此时以g ) 中的边只需要用它的两个 端点的无序对来表示一个图也可以用图形来表示，用小圆圈代表h g ) 中的元素，用小圆 圈和小圆圈之间的连线表示厨g ) 中的元素经常把一个图与它代表的图形等同起来，即把 代表图的图形也称为图 若口以g ) 且惦( 力= w ，则称8 连接和v ，或称p 与“及v 关联，而“和v 称为p 的 端点，也称”与v 是相邻的为了简单起见，把咖( p ) = w 记作p = 计，把g 中所有与顶 点v 相邻的顶点的集合称为v 的邻域，记为 k ( v ) 或( v ) 与同一个顶点关联的两条边称为是相邻的；两个端点重合的边称为环，端点不重合的 边称为连杆；连接同一对顶点的边称为重边( 或多重边、平行边) 显然“相邻”是指顶 点和顶点之间、边与边之间的关系，而“关联”是指顶点和边之间的关系若一个图既没 有环，也没有重边，则称这样的图为简单图；若图中允许含有重边，则称之为多重图；若 图中允许含有环和重边，则称之为伪图若图的顶点集及边集都只含有限个元素，则称之 为有限图，否则称之为无限图我们只讨论有限图 图g 的顶点数、边数分别用，( g ) 、占( g ) 表示，即有y ( g ) = i 矿( g ) i ，占( g ) = i e ( g ) | y ( g ) 又称为图g 的阶当只讨论一个图时，我们通常省略g ，用ne ，y ，s 来代替w g ) ， 以g ) ，y ( g ) ，占( g ) 图g 中顶点v 的度定义为与v 关联的边的数目( 与v 关联的每个环算 作两条边) ，记为如( v ) 用占( g ) 和( g ) 分别表示图g 中顶点度的最小值和最大值，即 占( g ) = i i l i n 叱( v ) i v y ( g ) ) ，( g ) = m a x 如( v ) i v 矿( g ) ，分别称为图g 的最小度和最 大度 定理1 1 1 ”( 握手引理) 。、如( = 2 ( g ) 若图g 和日满足y ( 日) 5 y ( g ) ，且e ( 日) s 五( g ) ，则称日为g 的子图，记为h g 若 y ( 日) = y ( g ) ，且e ( 日) = e ( g ) ，则称日与g 相等，记为日= g 若日g 且日g ，则 称h 为g 的真子图，记作日c g 若矿( h ) = 矿( g ) ，且e ( 日) e ( g ) ，则称h 是g 的支 撑子图；若去掉图g 中的一切环。并且对连接任何一对顶点的重边，除保留一条外，去掉 第1 页 国防科学技术大学研究生院学位论文 重边中余下的一切边，这样得到g 的一个简单支撑子图称为g 的基础简单图设矿为y ( g ) 的非空子集，以矿7 为顶点集，以 w e ( g ) i 材，v 矿 为边集的g 的子图称为图g 的由矿导 出的子图，记为g 【矿】，简称为图g 的导出予图；设占为e ( g ) 的非空子集，称顶点集为 ( v i v 为占中某条边的端点) ，边集为e 的g 的子图为g 的由e 导出的子图，记为g 陋】， 简称为g 的边导出子图 g 的一条途径是指一个有限的非空序列= q v l 乞v 2 唯，这里v l 矿( g ) ( 0 s j 后) ， p ，e ( g ) ( 1 s f 七) ，并且p 。= v i l v 。( 1 s f s | ) ，v o 称为的起点，h 称为矿的终点，其它 的顶点称为矿的内点，并把称为g 的( v 。，v 。) 途径，尼称为矿的长，有时把途径形简记 为形= kv l v 。如果途径的边互不相同，则称矿为迹：如果途径的顶点互不相同， 则称为链，特别地，单个顶点也称为一条链，长为七的链记作n 显然，链必定是迹， 然而迹却不一定是链如果途径的长至少为1 ，且起点与终点重合，则称之为闭途径；类 似地，可以定义闭迹；起点、内点均互不相同的闭迹称为圈；i l 圈是长为七的圈，记为c k 1 圈就是环，3 圈又称为三角形 如果图g 中存在( 地v ) 链，则称g 的两个顶点”和v 在g 中是连通的“连通”是顶点 集h 回上的一个等价关系利用图g 的连通性，则可在它的顶点集h g ) 上存在非空划分k ， k ，圪，即k n = a ( f ，= 1 ，2 ，) 且u ：，巧= y ( g ) ，使得两个顶点连通当且仅 当它们属于同一个k ，导出子图g 哦】，g 【】，g 圪】称为g 的连通分支，简称分支； 如果g 恰好只有一个连通分支，则称g 为连通图，否则为非连通图易知，g 是连通的当 且仅当g 中任何两个顶点之间都有链连接 设g 是一个图，m 量e ( g ) ，如果m 中的每条边都是连杆，且任意两条边都不相邻， 则称m 为g 的匹配g 的所有匹配中边数最多的称为最大匹配，若匹配m 满足i 肘 号， 则称为完美匹配 设g 是一个图，e 为图g 韵若干条边构成的集合，则g e 表示从g 中删去f 中一 切边后得到的g 的支撑子图：若e = p ) ，则g 一 e ) 简记为g p 设矿为h g ) 的非空真 子集，则g 一矿表示从g 中删去矿中一切顶点以及与矿中顶点关联的所有边后得到的图； 同样，g 一 y 简记作g v 显然，g 一矿= g 吵矿】与从图中删去边集相对应的是添加 边集用g + 8 表示在图g 中添加一条以图g 中的顶点”和v 为端点的边口后得到的图； 类似地可以定义g + e 设g i = ( k ，五) 与g 2 = ( k ，e 2 ) 是两个图称g j 与g 2 是点不交的( 或者不交的) 是指g 1 与g ：没有公共顶点，即巧n 巧= o ；如果g l 与g 2 没有公共边，即五n 易= o ，则称g l 与g 2 是边不交的g l 和g 2 的并图是指图( k u 吒，巨u e ) ，记作g 1 ug 2 ；特别地，若g l 和g 2 是点不交的，则把g l ug 2 记作g l + g 2 如果g l 和 至少有一个公共顶点，则定义 g l ng 2 = ( k n k ，县n 垦) ，称为g l 与 的交图 第2 页 国防科学技术大学研究生院学位论文 设g l 与岛是两个同阶的图，如果在g l 和g 2 的顶点集h g l ) 和h g 2 ) 之问存在一一对 应关系，使得连接g l 的任何一对顶点的边数等于连接g 2 的任何一对顶点的边数，即使得 对连接g l 中任何一对顶点，它们在g 1 中相邻当且仅当它们的对应点在g 2 中相邻，则称 g l 和g 2 是同构的，记作g l 兰g 设g 是一个p 阶图，g 的邻接矩阵( g ) = 0 0 是一个z ，x 矩阵，其中等于图g 中 第f 个顶点与第，个顶点之问的边数 1 1 2 有向图的基本概念 有向图与图类似，也是由顶点和边构成，只是有向图中的边是有方向的所谓一个有 向图d 是指一个有序三元组( h d ) ，4 ( d ) ，彩) ，这里h d ) o ，h d ) n a ( d ) = o h d ) 称为 d 的顶点集，其中的元素称为d 的顶点：彳( d ) 称为d 的弧集，其中的元素称为d 的弧； 锄称为d 的关联函数，它是使d 的每条弧对应于d 的有序顶点对的函数如果口是d 的 弧，且仍( 曲= ( ，v ) ，则称口连接”到v ；封称为口的尾，v 称为口的头为了简单起见， 把咖( = ( 材，v ) 记作口= ( 封，v ) ，把d = ( 比d ) ，丘d ) ，锄) 记作d = ( h d ) ，爿，这时只需把 k d ) 中的弧用它的尾和头的有序对来表示一个有向图也可以用图形来表示，顶点用小圆 圈表示，弧用从尾到头的标有箭头的线段表示 头和尾重合的弧称为环如果两条弧有相同的头和相同的尾，则称这两条弧为重弧既 没有环也没有重弧韵有向图称为简单有向图若有向图中允许含有重弧，则称为多重有向 图若有向图中允许含有环和重弧，则称之为伪有向图若有向图的顶点集及弧集都只含 有限个元素，则称之为有限有向图，否则称之为无限有向图我们只讨论有限有向图 如果把有向图d 的每条弧看作无向的边，即不记弧的方向，从而得到一个无向图，称 之为d 的基础图反之，给定一个图g ，如果对g 的每条边都规定一个方向，则称给了g 一个定向由g 的一个定向所得到的有向图，称为g 豹定向图，记作石如果把g 的每条 边w ，换为一对方向相反的弧( 甜，和“m ，则称所得的有向图为与g 对应的对称有向图， 记作g 如果g 是完全图，贝0 称8 为完全对称有向图 利用有向图的基础图，图的每个概念均可以自动搬到有向图上来例如，设g 是d 的 基础图，d 中的圈是指d 中这样的一些顶点和弧构成的序列：使这些顶点和弧相对应的边 构成g 的圈由于在有向图中，“方向”是很重要的，因此接下来介绍有向图中与方向有 关的一些概念 设v 是有向图d 的一个顶点，d 中以v 为头的弧称为v 的入弧；以v 为尾的弧称为v 的出弧：v 的入弧总数记作靠( v ) ，称为v 的入度；v 的出弧总数记作靠( v ) ，称为v 的出 度此外用占一( d ) ，_ ( d ) 和矿( d ) ，a + ( d ) 分别表示d 中顶点的最小入度、最大入度和最小 出度、最大出度，分别称 ( v ) = 扣矿( d ) i ( ，v ) 爿( d ) ) 和；( 1 ，) = 扣矿( d ) i ( v ，村) 一( d ) ) 为v 在d 中的入邻域和出邻域，且令；t v 】= ；( v ) u v ) ，去【v 1 = ；( v ) u v 。仍用y ( d ) 和( d ) 表示有向图d 的顶点数( 又称阶) 和弧数 第3 页 国防科学技术大学研究生院学位论文 定理1 1 2 1 1 l 对于任何有向图d ，有，州d ) 畦( v ) = 。啪) 靠( v ) 有向图d 中的有向途径是指一个有限的非空序列矿= v o 口1 h 吒v 2 唧唯，其中的项交替 地为d 的顶点和弧，并且q = ( v j - 1 ，v j ) ( 1 f i ) ，v 。称为矿的起点，v 。称为彤的终点，把 矿称为d 的有向( v 。，v 。) 途径，j 称为的长同图的途径一样，也常把有向途径矽简记 作= v 1 唯有向迹是指弧互不相同的有向途径同理有向闭途径、有向闭迹、有向 链、有向圈等可以类似地定义有向链又称为路，有向圈又称为回路，长度为_ j 的回路称 为j 】 回路 对w ，丁矿，定义( s ，丁) = ( “，v ) 0 l “s ，v r 若s 为矿的非空真子集，r = y s ， 则称假d 为d = ( 以一) 的截集 设d 是一个”阶有向图，d 的邻接矩阵4 c d ) = ( 蝴是一个矩阵，其中的等于有向 图d 中以第f 个顶点为尾、第，个顶点为头的弧的数目 1 1 3 几类重要的图和有向图 空图：任何一个顶点都是孤立点的图 完全图；任何两个相异顶点间均有边的简单图用岛表示以阶完全图 正则图：每个顶点的度都相等的图每个顶点的度都为七的正则图称为七正则图 二部图：如果坎g ) 可以划分为两个子集x 和y ，即x n y = a 且鼻u y = y ( g ) ，使g 的每条边的一个端点在工中，另一个端点在】，中二部图记作g = ( 置e 毋 完全二部图：若中每个顶点与y 中每个顶点之间恰有一条边，且工o ，】，a ， 则称二部图g = 伐y ；d 为完全二部图若陋i = m 及| y i = ”，则记这样的完全二部图为如， 七部图：顶点集可分解为_ | 个子集巧，k ，k ，使任何一条边的两个端点均不同在 任一个子集k 中的图( 1 j 七) ，记为g = ( k ，吒，吒；e ) 完全七部图：顶点集可分解为七个非空子集k ，k ，k ，且每个顶点与不在同一 子集中的所有其它顶点均相联接的简单膏部图若还满足| _ 他( 1 s i 七) ，则这样的完全 | 部图记作，：，。 七星；以v 为中心的七星( 记作最( v ) 或s ) 是指g 中一个具有七条边和n 1 个顶点的 子图，使其中一个顶点v e y 的度为i ( 称v 为星吼( v ) 的中心) ，其余顶点的度数皆为1 ； 显然完全二部图k 。即为七星，3 星k ，为爪 j 正则有向图：每个顶点的出度和入度都是k 的有向图 二部有向图：如果y ( d ) 可以划分为两个子集j 和y ，使d 的每条弧的头和尾不同时 在x 或】，中二部有向图记作d = ( x ，r 彳) 有向h 舢i l t o n 图：若有向图d 中存在包含一切顶点的回路c ，则称d 为有向h 锄i 】t o n 图，c 称为d 的h a m i l t o n 回路若有向图d 中存在包含一切顶点的路尸，则p 称为d 的 h a m i l t o n 路 第4 页 国防科学技术大学研究生院学位论文 关于有向h 锄i l t o n 图，有如下定理 定理1 1 3 1 1 l ( n a s h w i m a m s 。1 9 6 0 ) 设d 是一个y 2 阶的简单有向图，若 m m 占一( d ) ，艿+ ( d ) ) 号， 则d 是有向h 锄i l t o n 图 完全二部对称有向图：若将完全二部图j 已。中的每条边“v 换为一对方向相反的弧 ，v ) 和( v ，”) ，则称所得的有向图d 是完全二部对称有向图，记作疋。 1 2 图的因子问题中的一些基本知识 图的因子问题是图论中的重要问题之一，其理论和应用日趋成熟图g 的一个因子是 指满足某些给定条件的g 的支撑予图我们说g 是因子f 的和，若g 是这些因子的边不 相交的并这样的一个并称为g 的一个因子分解一般的，图中存在两种因子，一种是度 因子，另外一种是分支因子如果给定的条件与顶点的度有关，那么称g 的因子为g 的度 因子例如，1 因子属于度因子的范畴一个一因子是一个行度正则的因子若g 是几个胛 因子的和，它们的并称为g 的一个n 因子分解，而g 本身称为是万可因子化的如果给定 的条件涉及到g 的因子钓各分支与某些给定的图之间的同构关系，那么称g 的因子为g 的分支因子 设翻，口) 是一组连通图的集合，g 是一个图图g 的一个埘，e ) 因子f ，是指g 的一个支撑子图f ，满足f 的每个分支都同构于即，b 中的某一个图特别地，记图g 的即 因子为4 因子例如，g 的一个n 因子是指g 的一个的支撑子图f ，满足f 的每个 分支都同构于有4 个顶点的链p 4 注意到，图的1 因子和n 因子是等价的如果图g 的 边集能划分成埘个边不交的翻，曰 因子只，局，r ，则称f = 凡，f 2 ，晶) 是g 一个的 4b ) 因子分解特别地，记g 的钮) 因子分解为4 因子分解如果图g 的边集 能划分成肌个边不相交的蜀，易，厶的和，并且满足( 矿，巨) 兰( 矿，臣) 兰兰( y ，e ) ， 则“矿，e ) ii - 1 ，2 ，埘) 称为g 一个的同构因子分解易见，同构因子分解是一种特殊的 分支因子分解 图的正交因子分解是图的因子理论的重要分支之一设g 是一个图，g 和厂是定义在 坎g ) 上的两个非负整数值函数且对每个“矿( g ) 有g ) ，( ) ，则g 的一个b 厂) 因子是g 的一个支撑子图f 满足对每个“矿( g ) 有g ( “) 出( ”) s ，( 甜) 特别地，若g 本身是一个 慷，) 因子，则称之为噱，) 图。若g 的边集能划分成小个边不相交的噱，) 因子f l ，f 2 ， 死，则称f - 饵，e ，) 是g 的一个( 毋，) 因子分解，也说g 是可b ，) 因子分解的设 f = 饵，最，e 是g 的一个b ，) 因子分解，日是g 的一个有研r 条边的子图，如果对所有 的1 f 肼有i e ( 日) n e ( f ) l _ ，那么称f ，正交于日；特别地，当，= 1 时称f 正交于且此 外，称f 是g 的一个，正交协，) 因子分解；特别地，当，= l 时称f 为g 的一个正交b ，) 因子分解；当r 2 时，我们又称r 正交b ，) 因子分解为推广的正交嘶，) 因子分解 第5 页 国防科学技术大学研究生院学位论文 设g 是一个图，s 和丁是坎g ) 的两个不相交子集，用g s 表示从图g 中去掉顶点集s 以及与s 有关联的所有边所得到的g 的子图，用( s ，丁) 表示g 中连接s 和r 的边集合， 即令臻( s ，丁) = “v e ( g ) i “s ，v 丁) ，且记( s ，r ) = i ( 只丁) i 对任意函数，记 ，( s ) = 。，( “) 且记，( a ) = o 设c 是g 一( s u 丁) 的一个分支，g 和，是定义在矿( g ) 上 的非负整数值函数，如果对每个“y ( c ) 有g ( 封) = ，( “) ，那么根据( 丁，y ( c ) ) + ，( c ) ) 的 奇偶性称c 是g 一( s u 丁) 的奇分支或偶分支若分支c 既不是奇分支，也不是偶分支，则 称c 是g 的中分支用k ( s ，丁) 表示g 一( s u 丁) 的奇分支的数目由( s ，丁) 的定义易见： 当对每个“矿( g ) 有g ( “) 厂( “) 时，( s ，丁) = 0 为了方便起见，记 ，( s ) = 。，( 甜) ，g ( r ) = 。g ( “) ， 如( r ) = 。，如( 材) ，d = 矿( g ) ( s u r ) ， e ( s ) = m ，e ( g ) i “，v s ) ，五( r ) = l n ，e ( g ) | 材，v e 丁 ， 并且令 晚( s ，r ；g ，) = 电s ( r ) 一g ( r ) + ，( s ) 一( s ，r ) l o v 矗s z 口】于1 9 7 0 年得到了下面的结果 引理1 上1 嘲设g 是一个图，g 和，是定义顶点集h g ) 上的非负整数值函数且对每个 ”y ( g ) 有g ( 甜) ，( ) ，则g 有噱，) 因子当且仅当对坎g ) 的任意两个不相交的子集s 和 r ，有既( s ，r ；g ，厂) o 现设s 和丁是h g ) 的两个不相交子集，巨和e 2 是以g ) 的两个不相交子集记 = 局n e ( s ) ，耳= 巨n e ( s ，d ) ， e = 乓n e ( r ) ，e = 岛n e ( 丁，d ) ， 两= g 【u 茸】，= g 【丘u e 】， 并令 口= ，f ；骂) = 2 慨l + i 茸卜( s ) ， = 尾( s ，r ；易) = 2 i e i + i 互i = d 乩( r ) ， = g ( s ，r ；乓，易) = c 咕( s ，r ；巨) + 屁( s ，r ；最) = 口+ 声 原晋江在文献【3 】中用引理1 2 1 证明得到下面的结果，并由李国君和刘桂真在文献【4 】 中给出了新的证明 引理1 2 2 m 设g 是一个图，g 矛v 是定义在联g ) 上的非负整数值函数且对每个“r ( g ) 有o 蔓g ( “) 厂( “) s 如( “) 设e l 和易是耳g ) 的两个不相交子集，则g 有一个b 力因子f 使得巨e ( f ) 且如n e ( f ) = o 当且仅当对h g ) 的任意两个不相交子集s 和l 有 芘( s ，丁；g ，厂) g ( s ，；互，毛) 第6 页 国肪科学技术大学研究生院学位论文 关于一般的二部图( 允许含有重边，二部图显然不含有环) 的因子问题，有下面的重要 引理 引理1 2 3 i s j 设g = ( 置ed 是一个二部图，g 和是定义在职回上的非负整数值函数 且对每个”e 矿( g ) 有g ( “) 厂( “) ，则g 有国，) 因子当且仅当对s x ，v r y ，下列 两式成立： ，( s ) + ( z s ，丁) g ( 丁) 0 ， ，( 7 ) + ( s ，j ，r ) g ( s ) o 1 3 图因子分解的发展概述 图的因子理论是图论的一个重要分支，是图论研究中最活跃的课题之一，它在网络设 计等实际问题中有广泛的应用例如，计算机网络中的文件传输问题可以转化为图的( d ，) 因子分解问题对因子理论的研究最早可以追溯到一个世纪以前1 8 9 1 年，p e t e r s e n 在考 虑h i l b e r t 于1 8 8 9 年提出的一个代数因子分解问题时，将其转化为图的因子问题并且证明 了任何一个含有至多两条割边的3 正则图有1 因子1 8 9 8 年，p 酏懿e n 给出了一个非平面、 3 正则、无割边的特殊图，该图无l 因子分解，这个图就是著名的p e t e r s e n 图k 6 1 1 i g 和 h a l l 分别于1 9 3 1 年和1 9 3 5 年得到著名的k 6 1 1 i g h a l l 定理该定理解决了二部图的l 因子 的存在性问题而l 因子的存在性问题是由t l m e 于1 9 4 7 年给出的，这一定理奠定了因子 理论的基础1 9 5 2 年，t u 廿e 又给出了图有厂因子的充要条件1 9 7 0 年，l l o v 缸z 得到了 图有弛，) 因子的判断准则，即有名的乜，) 因子定理从此，因子理论的研究活动活跃起 来此外，尽管图的因子问题中的很多结论可以推广到某些局部有限的无限图，例如，i - u n e s 的1 因子定理，t u 她s 的，因子定理和l o v & s z s 的晾厂) 因子定理都可以稍微改变条件从而 推广到局部有限的无限图中但是，本文我们只考虑有限图 图的b 厂) 因子分解理论是图的因子理论的重要分支之一，它是1 9 9 1 年才提出来的， 这方面的结果已有很多国内，刘桂真和闫桂英等人对图的缸，) 因子分解问题进行了深入 的研究 图的正交因子分解问题也是九十年代提出的新问题，有关这方面的结果可参见文献 【6 】图的正交因子分解有两种类型，即a l s p a s h 等人提出的下面两个问题： ( 1 ) 给定图g 的一个因子分解n 是否存在g 的一个具有某种性质的子图与f 正交 ( 2 ) 给定图g 的一个子图b 是否存在g 的一个具有某种性质的因子分解与日正交 一般地，统称上述两种类型的问题为图的正交因子分解问题这些问题的研究在组合 设计中有重要的应用例如，拉丁方和r 0 0 m 方等组合设计问题可化为图的正交因子分解 问题关于第一个问题，文献【6 】研究了与七因子分解正交的子图文献【7 】研究了与2 因子 分解正交的匹配存在的条件关于第二个问题，主要针对g 是一个( 嘲叶坍1 ，够m + 1 ) 图做 了些研究，文献 8 】研究了与匹配正交的因子分解问题文献【9 】研究了与星正交的因子分解 问题文献【1 0 】研究了与任意子图正交的因子分解问题在文献【1 0 】中，李国君和刘桂真证 第7 页 国防科学技术大学研究生院学位论文 明了：若g 是( 删叶m 1 ，j ，! ，锄+ 1 ) 图，日是g 的任意一个具有m 条边的子图，则g 有睡，) 因子分解与日正交但若g 是一个( 以舭1 ，够斛1 ) 图( 1 s 七 哟，而日是g 的任意一个 具有七条边的子图，则当1 s g 时g 是否具有一个子图r ，使得尺有一个b 力因子分解 与日正交呢? 闫桂英和潘教峰在文献【1 1 】中作为猜想提出该问题，并证明了当g l ，5 时，这样的子图曰是存在的通过对该问题的研究，文献【1 2 】最终证明了对任意的g ，及 子图日，该猜想都是成立的李国君和刘桂真在文献【1 3 】中证明了猜想成立，得到了更一 般的结论，证明了每个( m i 旷虹彤娜图含有一个子图显，使得月有一个噱力因子分解r 正 交于g 的任意给定的有妇条边的子图，其中m ，后和，是正整数且_ j m ，g ， 第8 页 国防科学技术大学研究生院学位论文 第二章完全图的分支因子分解 2 1 引言 分支因子概念的提出时间并不久，在这个领域的结果也并不多，在1 8 4 7 年，k i r l 柚 研究了为可以分解成三角形，r e i s i s 于1 8 5 9 年证明了偶数阶完全图恐。存在1 因子分解近 年来，许多学者研究了完全二部多重图五e 。的0 因子分解，j 0 。表示完全二部无向图， 五玩。表示完全二部多重图，它是将如。的每条边重复a 次所得到的图当卅= h 时，称 a k 。为平衡完全二部多重图k u s h i o 在1 9 8 8 年完全解决了巧，的忍因子分解问题， h w a n g 于1 9 9 3 年完全解决了j r 坍，的昱，因子分解问题，d u 于2 0 0 3 年给出了五疋，存在b p 因子分解问题的充要条件本章主要讨论了完全图的因子分解，给出了完全图的新的分支 因子分解 令表示七星，用2 最表示将两个_ j 星s 的中心连接一条边之后得到的图令皿。 表示在2 、最一。中添加一个新的顶点，并且将此新顶点和构造2 最一的两个最一，星的中心分 别连接一条边所得到的2 时1 阶简单图，如岛表示下面的7 阶简单图： o 、户 夕弋7 。 图2 1 1z ，7 设y ) 是。) ，的顶点集的二分化，疗= ，埘，其中1 ) | i = r ，| y | = ( m 1 ) ，r 2 ， 辨2 用以和占二+ ，分别表示由两个完全二部图群胁1 ) ，按照如下规则构造的简单图：在 两个完全二部图群。) ，的两个x 中任意两个顶点之间添加一条边得到图以，再在a 玉的 基础上添加一个新的顶点并且将它和上述两个x 中的每个顶点连接一条边得到图占二。 2 2 完全图新的分支因子分解 关于完全图的因子分解已经有以下两个结论： 引理2 2 1 川完全图如是1 可因子化的 引理2 2 2 | l l 完全图恐州是玎个生成圈的和 引理2 2 1 说明完全图恐。存在憨因子分解即岛因子分解引理2 2 2 说明完全图恐l 是2 可因子化的，也即琏一l 存在c 2 。因子分解，且此因子分解中含有即个c 2 。因子 下面我们继续研究完全图的其他的因子分解 引理2 2 3 如是一个1 因子和一个晶1 因子的和，即如存在 飓，l 因子分解 第9 页 国防科学技术大学研究生院学位论文 证明设矿( 局。) = v 0 ，v i ，v ：，v 2 。) ，令岛= v + io s ，玎一1 ) ，定义 e = h l + i v ( f _ l “+ j ) 。o d 2 。i 七= 0 ，以，1 ，以一1 ) ，v 1 f s 玎 另记只表示如的由最导出的支撑子图( o f s 村) 易得 e ( 恐。) = u 乙骂= u 二e ( 鼻) ； 骂n 日= o ，v o f ，疗 不难看出，f 0 有一个连通分支且每个分支均和恐同构，每个e 有两个连通分支且每 个分支均和l 同构( 1 f 一) 故r 是如的1 因子而每个f f 均是如的品i 因子( 1 s f s 门) 显然，毋的选取方法给出了默的一种恰当划分，使得完全图j 是一个l 因子即 岛因子f 0 和力个1 因子f l ，足，b 的和由此可得，如有一个 局，晶1 因子分解 即 届，e ，e ，只 口 例2 - 2 1 以j 臼，酝岛为例，下图2 2 1 中的( ，( 6 ) 和( 0 分别表示当月= 2 ，3 ，4 时j 【厶 的 恐，墨1 ) 因子分解 培o 0 吩 v o o ov l m d 川 v l o 川b 也d _ 。b