（应用数学专业论文）完全图k2n的三角形谱.pdf

苏州大学学位论文使用授权声明 删 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文 论文作者签名： 导师签名： 盂鱼茎星日 扭日 期：上9 蚀0 牛。乙 1 。一 完全图鲍n 的三角形谱 摘要 摘要 设f 是恐n 的一个1 一因子对f 的任意一个2 一因子分解歹= f 1 ，乃，r 一。) ，令魂是包含在冠中的三角形数，6 = 盈，则称，是包含占 个三角形的2 一因子分解完全图鲍n 的三角形谱是指集合( 2 n ) ，这里a ( 2 n ) = 6i 存在j v 的一个2 一因子分解，其包含6 个三角形) 令 ) = = ：然 _ 1 轴若：2 n 州- 2 , 删4 ( r o o y d x 其中 = 荸 在本文中，我们考虑如何确定恐n 的三角形谱的问题我们证明了除去 一些小数值的例外和一些可能的例外，a ( 2 n ) = p z x ( 2 n ) 关键词：2 一因子分解；不完全2 一因子分解；三角形谱 作者：孟献臣 指导教师t 杜北梁( 教授) 嘭回回 以甜甜 m m m 2 4 o 兰 兰 三 n n 住 2 2 2 若若若 a b s t r a c tt h et r i a n g l es p e c t r u mf o rc o m p l e t eg r a p hk 轨 t h et r i a n g l es p e c t r u mf o rc o m p l e t eg r a p h 礼 a b s t r a c t s u p p o s ef i sa1 - f a c t o ro fk 2 g i v e na na r b i t r a r y2 - f a c t o r i z a t i o n 厂= 毋，易， ，r 一1 ) o fk 2 竹f ，l e t 况b et h en u m b e ro ft r i a n g l e sc o n t a i n e di nra n dl e t 占= 最 t h e n 手i ss a i dt ob ea2 - f a c t o r i z a t i o nw i t h 黾t r i a n g l e s t h et r i a n g l es p e c t r u mf o r c o m p l e t eg r a p h 恐ni st h es e t0 fa u6s u c ht h a tt h e r ee x i s t sa2 - f a c t o r i z a t i o nw i t h6 t r i a n g l e s ，d e n o t e db yz x ( 2 , 0 l e t w h e r e p a ( 2 , 0 = ：苏阶i f2 n 圳= 2or 4 ( r o o d6 ) ， i 虹学丑i f2 n 三2 ( m o d6 ) ， i 3一 、 ”， m 2 = 学i f2 n 三4 ( 删6 ) ， i 呈掣i f 2 n 三0 ( m o d6 ) i nt h i sp a p e r ，w ec o n s i d e rt h ep r o b l e mo fe s t a b l i s h i n gt h et r i a n g l es p e c t r u mf o r c o m p l e t eg r a p h 鲍n w ep r o v e dt h a ta p a r tf r o ms o m es m a l le x c e p t i o n sa n ds o m e p o s s i b l ee x c e p t i o n s ，a ( 2 n ) = p ( 2 n ) k e yw o r d s ：2 - f a c t o r i z a t i o n ，i n c o m p l e t e2 - f a c t o r i z a t i o n ，t r i a n g l es p e c t r u m i i w r i t t e nb ym e n gx i a n c h e n s u p e r v i s e db yp r o f d ub e i l i a n g 目，录 第一章引言1 第二章辅助设计3 第三章主要构造8 第四章主要结果1 3 参考文献2 1 附录2 3 致谢2 5 完全图鲍。的三角形谱第一章引言 第一章引言 若h 是完全图的生成子图，则称h 是的因子若生成子图h 是 2 一正则图，则称h 是的2 一因子的2 一因子分解是指的边集 的一个划分厂= f 1 ，恳，r 一1 ) ，这里只是的2 一因子更正式地，设x 是一个钆元集，是x 上的完全图，t 是边不重的2 一因子的集合，并且 t 构成的边集的一个划分，则称二元组( x ，t ) 是的2 一因子分解显 然，存在的2 一因子分解当且仅当n 为奇数 偶数阶完全图鲍。不存在2 一因子分解，但是若将鲍n 的边集去掉一个l 一因子，情况就不同了，从而我们有如下的定义设x 是一个2 n 元集， 是x 上的完全图，f 是一个l - 因子，t 是边不重的2 一因子的集合，并且 t 构成鲍n f 的边集的一个划分，则称三元组( x ，t ，f ) 是恐n f 的2 一因子 分解在本文中为了简便，我们将鲍n f 的2 一因子分解写成鲍n 的2 一因 子分解 当是偶数时，对于如何确定鲍n 一，或甬的2 一因子分解所包含的k 一圈数的集合的问题，人们已经做了很多工作对于一。的情况，d e j t e r ， l i n d e r 和r o s & f 8 】完全确定了鲍n t 的2 一因子分解所包含的4 一圈数的集合； a d a m s ，b i l l i n g t o n 和l i n d e r 【1 1 完全确定了配n 一1 的2 一因子分解所包含的6 一圈 数的集合；k u c u k c i f c if 1 5 】完全确定了鲍舻1 的2 一因子分解所包含的8 一圈 数的集合对于的情况，a d a m s ，b i l l i n g t o n ，d e j t e r 和l i n d e r 2 】完全确定了 的2 一因子分解所包含的4 一圈数的集合；k u c u k c i f c if 1 4 完全确定了 的2 一因子分解所包含的8 一圈数的集合( 有2 个可能的例外) 当k 是奇数时，对于如何确定甬一1 或鲍n 的2 一因子分解所包含的k 一圈数的集合的问题，已知的结果不多对于鲍n 一1 的情况，d e j t e r ，f r a u n e k ， m e n d e l s o h n 和r o s a 【7 】对n 三1 ，2 ( m o d3 ) 的情形确定了恐n 一1 的三角形谱，即 鲍n 一，的2 一因子分解所包含的3 一圈数的集合( 除去一些小数值的例外和一 些可能的例外) ；s u i 和d u 【17 】对n 兰0 ( r o o d3 ) 的情形确定了配n 一1 的三角形 谱( 除去一些小数值的例外和一些可能的例外) 对于硷n 的情况，如何确定 鲍n 的2 一因子分解所包含的k 一圈数的集合，这仍然是一个尚待解决的问 题 本文考虑的2 一因子分解所包含的3 一圈数的集合对鲍n 的任意 第一章引言 完全图鲍n 的三角形谱 一个2 一因子分解厂= f 1 ，毋，r 一1 ) ，令民是包含在冠中的三角形数， 6 = 反，则称歹是包含6 个三角形的2 一因子分解完全图的三角形谱 是指集合z x ( 2 n ) ，这里a ( 2 n ) = ( 占l 存在的一个2 一因子分解，其包含5 个 三角形) 经过简单的计算可知，m a xa ( 2 n ) n ，这里 ft ( n - 1 ) ( 2 n - 5 ) 若2 n 暑2 ( r o o d6 ) ， -7 h 一 、”， m 2 n = 下2 ( n - 1 ) ( n - 2 ) 若2 n 兰4 ( r o o d6 ) ， i 掣若2 n 兰0 ( m o d6 ) iq佃 一 u ， 令 = 苏。叫若：若2 n - 2 。, 4 ( r o o d 6 ) 则显然有a ( 2 n ) cp ( 2 n ) 在本文中，我们证明了除去一些小数值的例外和一些可能的例外，a c 2 n ) = p ( 2 竹) 定理1 1 若2 n 4 且2 n 2 8 ，3 0 ，3 4 ，3 6 ，3 8 ，4 0 ，4 8 ，5 2 ，5 8 ，6 0 ，7 6 ，则 f p ( 2 竹) 1 )若2 n = 6 ， ( 2 n ) = p z x ( 2 n ) 1 7 ，1 8 ，2 0 ) 若2 n = 1 2 ， 【p z x ( 2 n )其它 2 完全图鲍n 的三角形谱 第二章辅助设计 第二章辅助设计 在本章中，我们将介绍一些辅助设计和基本结果，这些设计和结果我们 将在后面用到设k 是一个正整数集，x 是一个口元集，舀是x 的子集的 集合，b 中的元素称为区组若对任意b 召，都有i b i k ，且x 中任意一对 不同的点恰好包含在唯一的区组中，则称二元组( x ，b ) 是指数为1 的成对平 衡设计( p b d ) ，记为b 1 ；口) i x i = t ，被称为p b d 的阶 设k 和m 是正整数集，可分组设计( g d d ) g d ( k ，1 ，m ；v ) 是一个三元组 ( x ，g ，召) ，这里 1 x 是一个t ，元集( x 的元素被称为点) ， 2 夕是x 的一个划分，夕中的元素被称为组，且对任意g 夕，都有i c l m ； 3 召是x 的子集的集合，召中的元素被称为区组，且对任意b b ，都有 l b i k ； 4 对任意b 1 3 与任意g g ，都有i bng i l ； 5 x 中任意两个来自不同组的点恰好包含在唯一的区组中 若g 包含如个大小为讹的组，15t s ，且口= 名1 盹，则称此g d d 的型为 仇t ，m 挚m 设( x ，召) 是一个成对平衡设计b ( k ，1 ；u ) ，尹c 召，若p 构成x 的一个划分， 则称p 是( x ，召) 的一个平行类若能将召划分成平行类，则称设计( 置召) 是 可分解的g d d ( k1 ，m ；口) 是可分解的是指它的关联p b db ( kum ，1 ；v ) 是可 分解的，并且9 是其中一个平行类 我们习惯上将b ( 尼) ，1 ；v ) 简记为b ( k ，l ；t ，) ，将g d ( 【尼) ，1 ，伽) ；u ) 简记为g d ( k ， l ，r e ；v ) 若kgk ，则b ( k u k + ) ，1 ；) 表示设计b ( k u k ，1 ；v ) 恰包含一个大小为 k 的区组；若kek ，则b ( k u k 】，1 ；t ，) 表示设计b ( kl ；t ，) 至少包含一个大小 为k 的区组对于g d d ，我们引入类似的记法如果对任意b 8 有l b l k ， 我们将g d d ( x ，9 ，召) 简记为k g d d 如果k = 【惫) ，也可记为七一o d d 关于成对平衡设计，我们有下面的结果 引理2 1 ( 1 ) ( 【1 0 】) 若口兰1 ，4 ( r o o d1 2 ) ，则存在b ( 4 ，1 ；u ) 3 第二章辅助设计完全图鲍n 的三角形谱 ( 2 ) ( | 4 】) 若口兰7 ，1 0 ( , n o d1 2 ) 且口2 2 ，则存在b ( 4 ，7 ) ，1 ；t ，) ( 3 ) ( 【1 3 】) 若u 三l ，4 ( r o o d1 2 ) 且4 0 ，则存在b ( 【4 ，1 3 ) ，l ；口) 关于可分组设计，我们有下面的结果 引理2 2 ( 1 ) ( 【6 】) 若让 4 ，则存在型为铲的4 - g d d ( 2 ) ( 9 】) 若m = 9 或1 5 ，3 u 一32m 且( u ，m ) ( 7 ，1 5 ) ，则存在型为铲m 1 的 4 一g d d 可分解b ( 3 ，1 ；t ，) 也称为k i r k m a n 三元系，记为k t s ( v ) k t s ( v ) 存在当且 仅当口三3 ( r o o d6 ) k t s ( v ) 的平行类的个数是孚设口三0 ( r o o d6 ) ，则n e a r l y k i r k m a n 三元系是指型为2 羞的可分解3 - g d d ，记为n k t s ( v ) 若存在n k t s ( v ) ， 则显然有地( 秽) 关于n e a r l yk i r k m a n 三元系，我们有 引理2 3 ( 1 1 3 ，5 ，1 2 】) 存在n k t s ( v ) 当且仅当 三0 ( m o d6 ) 且 1 8 设( x ，9 ，8 ) 是一个g d d ，如果能将召划分成带洞平行类，其中每个带洞 平行类构成x g ( g 9 ) 的一个划分，则称这个g d d 是f r a m e 可分解的如 果一个f r a m e 可分解g d d 的所有的区组长均为3 ，则称这个g d d 是k i r k m a n f r a m e ，即3 - f r a m e 在k i r k m a nf r a m e ( x ，9 ，尽) 中，对每个组g g ，恰好有 i v 个 带洞平行类划分x g k i r k m a nf r a m e 中的组也被称为洞 k i r k m a nf r a m e 是由 s t i n s o n 正式引入的 关于k i r k m a nf r a m e ，我们有 引理2 4 ( 【1 6 】) 若 4 ，g 是偶数，且9 m 1 ) 兰0 ( r o o d3 ) ，则存在型为g u 的 k i r k m a nf r a m e 引理2 5 ( f 16 】) 设存在型为g l t * 9 2 t 2 鲕t ，l 的k g d d ，且对每个后k ，存在型 为胪的k i r k m a nf r a m e ，则存在型为( 的1 ) 。z ( 慨) 。2 ( ) 的k i r k m a nf r a m e 引理2 6 ( 1 ) 若m = 1 8 或3 0 ，6 u 一6 m ，且( t ，m ) ( 7 ，3 0 ) ，则存在型为1 2 u m l 的 k i r k m a nf r a m e ( 2 ) 若t 4 ，则存在型为1 2 u 的k i r k m a nf r a m e 4 完全图k 2 n 的三角形谱第二章辅助设计 证明对引理2 2 ( 2 ) 中的4 - g d d 应用引理2 5 ，其中h = 2 ，我们可以得到( 1 ) 第 二个结果可以直接从引理2 4 得到 下面我们将对一些较小的阶2 n 给出的三角形谱a ( 2 n ) 对2 n = 4 ，显 然有( 4 ) = o ) ，该设计仅包含一个4 一圈 引理2 7 ( 6 ) = o ，2 ) 证明p ( 6 ) = 1 0 , 4 】 3 ) 容易看出1 彰( 6 ) 从引理2 3 可以得到4 窖( 6 ) 下面 我们来说明 o ，2 ) c ( 6 ) 0 ( 6 ) ：( 1 ，2 ，3 ，4 ，5 ，6 ) ；( 1 ，3 ，5 ，2 ，6 ，4 ) 2 ( 6 ) ：( 1 ，2 ，3 ) ( 4 ，5 ，6 ) ；( 1 ，4 ，2 ，5 ，3 ，6 ) 弓i 理2 8 ( 8 ) = 【0 ，3 1 证明我们先给出设计3 ( 8 ) ： h i = ( 1 ，2 ，3 ) ( 4 ，8 ，5 ，6 ，7 ) ，日2 = ( 1 ，4 ，6 ) ( 2 ，5 ，3 ，8 ，7 ) ，3 = ( 1 ，5 ，7 ) ( 2 ，4 ，3 ，6 ，8 ) 在设计中做一些替换，我们可以得到剩下的设计将凰替换成( 1 ，6 ，2 ，7 ，8 ，3 ， 5 ，4 ) ，可以得到2 ( 8 ) 继续将日1 替换成( 1 ，8 ，4 ，7 ，6 ，5 ，2 ，3 ) ，可以得到1 ( 8 ) 继续将日3 替换成( 1 ，2 ，4 ，3 ，6 ，8 ，5 ，7 ) ，可以得到0 ( 8 ) 为了给出下面的设计，我们引入一类具有特殊性质的2 一因子分解设 ，是的一个2 一因子分解，其中礼是奇数且n 7 如果存在一个点。，使 得厂的每个2 一因子中都有一个三角形包含点z ，则称尸是的一个2 一因 子分解记宰( n ) = 6 存在的一个2 一因子分解歹，使得6 ( 芦) = 6 ) 关于( 几) ，我们有 引理2 9 ( 【17 】，【7 】) ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) 。( 7 ) = 3 ) ， ( 9 ) = 4 ，6 ，8 ，1 2 ， ( 1 1 ) = 5 ，6 ，7 ，8 ，9 】i ， ( 1 3 ) ) 【6 ，1 1 ，1 4 ，1 5 ，1 6 ，1 7 ，1 8 ， ( 1 5 ) = 【7 ，3 5 】 3 4 ) ， l ( 2 7 ) d 【1 3 ，n 7 1 4 ，1 6 ，1 1 6 ) 引理2 1 0 若艿( n ) ，其中住是奇数，则6 一警m + 1 ) 5 n 1 第二章辅助设计 完全图k 轨的三角形谱 证明设厂是( 在集合x 上) 的一个2 一因子分解，且厂的每个2 一因子中 都有一个三角形包含点z 设( z ，口，6 ) 是任意一个包含点。的三角形，添加一 个新点0 0 ，使它变成( z ，口， 6 ) 这样一来，点集扩大了，但2 一因子的个数并 没有变，我们就得到了+ ，( 在集合xu o o 上) 的一个2 一因子分解经过 计算，我们得到6 一学+ 1 ) 引理2 1 1z x ( 1 0 ) = 【0 ，8 】 证明对引理2 9 中的岔( 9 ) 应用引理2 1 0 ，我们可以得到 o ，2 ，4 ，8 ) cz x ( 1 0 ) 剩 下的数值可以从设计7 z x ( 1 0 ) 得到 7 z x ( i o ) ：日1 = ( 1 ，2 ，3 ) ( 4 ，5 ，6 ) ( 7 ，8 ，9 ，1 0 ) ，i 2 = ( 1 ，4 ，7 ) ( 2 ，5 ，8 ) ( 3 ，9 ，6 ，1 0 ) ， 月3 = ( 1 ，5 ，9 ) ( 2 ，6 ，7 ) ( 3 ，4 ，1 0 ，8 ) ，t t 4 = ( 1 ，6 ，8 ) ( 2 ，4 ，9 ，7 ，3 ，5 ，1 0 ) 将日l 替换成( 4 ，5 ，6 ) ( 1 ，3 ，2 ，9 ，8 ，7 ，1 0 ) ，可以得到6 z x ( 1 0 ) 将日3 替换成 ( 1 ，5 ，7 ，6 ，2 ，9 ) ( 3 ，4 ，1 0 ，8 ) ，可以得到5 ( 1 0 ) 继续将日2 替换成( 1 ，7 ，2 ，5 ，8 ，4 ) ( 3 ，9 ，6 ， 1 0 ) ，可以得到3 a ( 1 0 ) 继续将研替换成( 1 ，2 ，3 ，6 ，5 ，4 ，7 ，8 ，9 ，1 0 ) ，可以得到 1 z x ( 1 0 ) 这就完成了证明 引理2 1 2z x ( 1 2 ) = 【0 ，1 6 证明p ( 1 2 ) = 【0 ，2 0 】 1 9 l 由引理2 3 知，2 0gz x ( 1 2 ) 对于数值1 7 和1 8 ，我们通 过计算机搜索得到1 7 ，1 8gz x ( 1 2 ) 对引理2 9 ( 3 ) 中的a ( 1 1 ) 应用引理2 1 0 ，可 以得到【o ，4 】ca ( 1 2 ) 下面我们给出两个设计1 5 z x ( 1 2 ) 和1 6 ( 1 2 ) 1 5 z x ( 1 2 ) ： h 1 = ( 1 ，2 ，3 ) ( 4 ，5 ，6 ) ( 7 ，8 ，9 ) ( 1 0 ，1 1 ，1 2 ) ，t 2 = ( 1 ，4 ，7 ) ( 2 ，5 ，1 0 ) ( 3 ，8 ，1 1 ) ( 6 ，9 ，1 2 ) ， - 1 3 = ( 1 ，5 ，8 ) ( 2 ，4 ，1 2 ) ( 3 ，9 ，1 0 ) ( 6 ，7 ，1 1 ) ，t t 4 = ( 1 ，6 ，l o ) ( 2 ，9 ，1 1 ) ( 3 ，4 ，8 ，1 2 ，5 ，7 ) ， - 5 = ( 2 ，6 ，8 ) ( 1 ，9 ，4 ，1 0 ，7 ，1 2 ，3 ，5 ，1 1 ) ； 1 6 z x ( 1 2 ) ： g 1 = ( 1 ，2 ，3 ) ( 4 ，5 ，6 ) ( 7 ，8 ，9 ) ( t o ，1 1 ，1 2 ) ，g 2 = ( 1 ，4 ，7 ) ( 2 ，5 ，1 0 ) ( 3 ，8 ，1 1 ) ( 6 ，9 ，1 2 ) ， g 3 = ( 1 ，5 ，8 ) ( 2 ，7 ，1 2 ) ( 3 ，6 ，1 0 ) ( 4 ，9 ，1 1 ) ，g 4 = ( 1 ，9 ，l o ) ( 2 ，4 ，8 ) ( 3 ，5 ，1 2 ) ( 6 ，7 ，1 1 ) ， g 5 = ( 1 ，1 1 ，2 ，6 ，8 ，1 0 ，7 ，5 ，9 ，3 ，4 ，1 2 ) 对这两个设计做些替换，我们可以得到剩下的设计将日3 依次替换 成( 1 ，5 ，8 ) ( 3 ，9 ，1 0 ) ( 2 ，7 ，6 ，1 1 ，4 ，1 2 ) 和( 1 ，5 ，9 ，3 ，1 0 ，8 ) ( 2 ，7 ，6 ，1 1 ，4 ，1 2 ) ，可以得到1 3 ，1 1 ( 1 2 ) 继续将日1 依次替换成( 1 ，2 ，4 ，5 ，6 ，3 ) ( 7 ，8 ，9 ) ( 1 0 ，1 1 ，t 2 ) 和( 1 ，2 ，4 ，5 ，6 ，3 ) ( 7 ，1 1 ，1 2 ， 1 0 ，9 ，8 ) ，可以得到9 ，7 z x ( 1 2 ) 继续将飓替换成( 1 ，4 ，7 ) ( 6 ，9 ，1 2 ) ( 2 ，3 ，8 ，1 1 ，1 0 ，s ) ，可 6 完全图鲍n 的三角形谱 第二章辅助设计 以得到5 n ( 1 2 ) 将g 4 依次替换成( 1 ，9 ，1 0 ) ( 2 ，4 ，8 ) ( 3 ，7 ，6 ，1 1 ，5 ，1 2 ) 和( 1 ，9 ，2 ，8 ，4 ，1 0 ) ( 3 ，7 ，6 ，1 1 ，5 ，1 2 ) ， 可以得到1 4 ，1 2 ( 1 2 ) 继续将g 3 依次替换成( 1 ，5 ，8 ) ( 3 ，6 ，1 0 ) ( 2 ，4 ，9 ，1 1 ，7 ，1 2 ) 和 ( 1 ，6 ，1 0 ，3 ，5 ，8 ) ( 2 ，4 ，9 ，1 1 ，7 ，1 2 ) ，可以得到1 0 ，8 a ( 1 2 ) 继续将g 2 替换成( 1 ，4 ，7 ) ( 2 ，5 ， 1 0 ) ( 3 ，1 1 ，8 ，1 2 ，9 ，6 ) ，可以得到6 ( 1 2 ) 这就完成了证明 7 第三章主要构造完全图恐。的三角形谱 第三章主要构造 在本章中，我们将给出一些递归构造第一个构造是g d d 构造 构造3 1 设( 以夕，b ) 是可分组设计g d ( k , 1 ，m ；u ) 若对每个k k ，存在鲍七+ 1 的2 囊一因子分解，且对每个g 夕，存在鲍| g i + 2 的2 一因子分解，则存在鲍： 的2 一因子分解进一步，若对每个区组b 召有如a ( 2 吲+ 1 ) ，且对每个 组g 夕有如( 2 1 g l + 2 ) ，则b 蓐( 曲一l b i ) + g g 晒a ( 2 u + 2 ) 证明令v = u x 1 ，2 ) u o o 。，0 0 2 ) 我们将( z ，i ) 简记为戤对一个给定的点z u ， 令俨是9 中包含点z 的组，研，磁，露是召中所有包含点z 的区组令 乃。是点集俨= 俨 1 ，2 ) u o o l ，0 0 2 ) 上的完全图鲍i g i + 2 的一个2 一因子分 解，其中艿( 凡) = 6 e - 令碍是点集露- 砑 l ，2 ) u o o l 上的完全图鲍i b i + l 的一个2 一因子分解，其中占( 碍) = 啦，t = 1 ，2 ，q 将集合俨中的元素重 新排列，我们可以假定( o o - ，0 0 2 ) 是1 一因子中的一条边将集合群中的元 素重新排列，我们可以假定砰中的每个2 一因子均有一个三角形包含点o o 。， 并且这个三角形中的另外两个点是y 。，y 2 ，这里y 群设2 一因子分解碍中 包含三角形1 ，钆z 2 ) 的2 一因子是砰因为琢中2 一因子的个数是i 俨i ， 所以我们可以记琢= 硌：秒g 霉) 从而f 霉= ( u 耳 ( 。o ，钆。2 ) ) ) u 瑶。是 1 s t s 口 勇+ 2 ( 在集合y 上) 的一个2 一因子，- = p ：。u ) 是恐u + 2 的一个2 一因 子分解经过计算，我们得到b b ( 6 b i b d + g 印配a ( 2 u + 2 ) 我们的第二个构造是f r a m e 构造 构造3 2 若存在型为夕u 的k i r k m a nf r a m e ( x ，夕，b ) ，且存在+ 2 的2 一因子分 解，则存在u + 2 的2 一因子分解进一步，如果盈0 + 2 ) ，1 i 缸，则 掣+ 1 l u 氏a ( g u + 2 ) 证明令v = x u o o l ，0 0 2 对每个组g 9 ，恰有1 个带洞平行类皿，玩，h 鲁 构成x g 的划分设乃是点集g u 【o o 。，0 0 2 ) 上的完全图+ 2 的一个2 一因 子分解，其中6 ( y a ) = 晒显然有i 危i = g 将集合g u o o 。，o o z ) 中的元素重新 排列，我们可以假定( o o - ，0 0 2 ) 是1 一因子中的一条边将乃的g 个2 一因 子填入g 个带洞平行类中，我们可以得到u + 。( 在集合y 上) 的g 个2 一因 8 完全图鲍n 的三角形谱 第三章主要构造 子从而，= 乃u ( u 凰) ：g 9 ) 就构成了u + 2 的2 一因子分解经过 1 墨 计算，我们得到掣+ g 岔晒( 鲫十2 ) 下面我们将介绍f r a m e 构造的推广为了这个目的，我们需要引入不完 全2 一因子分解的概念设x 是一个2 n 一元集，ycx 是一个t u 一元集( 叫是 偶数) ，f 是x y 的一个1 一因子，屡是x 上的一些圈的集合若召满足下面 两个条件： 1 召构成鲍n ( u f ) 的边集的一个划分， 2 召能划分成佗一詈个x 上的平行类( 也是2 一因子) 和詈一1 个x y 上的带 洞平行类， 则称四元组( x ，y , b ，f ) 是虼。f 的不完全2 一因子分解 设歹= r ，r 一号，r 一詈+ l ，晶一，) 是f 的不完全2 一因子分解，其中 洞的大小为令瓯表示包含在最中的三角形的个数，5 = 盈，则称厂是 包含5 个三角形的不完全2 一因子分解我们记( 2 n ；伽) = 6i 存在恐n f 的 不完全2 一因子分解( 洞的大小为叫) ，其包含6 个三角形) 引理3 3 2 3 ，删 4 3 ) c ( 1 8 ；6 ) 证明取点集x = 1 ，2 ，1 8 ) ，洞为y = 1 3 ，1 4 ，1 8 ) 我们首先考虑设计4 4 n ( z 8 ；6 ) ( 1 ，1 2 ，1 3 ) ( 2 ，4 ，1 4 ) ( 3 ，8 ，1 7 ) ( 5 ，9 ，1 5 ) ( 6 ，1 0 ，1 8 ) ( 7 ，1 1 ，1 6 ) ， ( 1 ，1 1 ，1 4 ) ( 2 ，6 ，1 5 ) ( 3 ，5 ，1 6 ) ( 4 ，7 ，1 8 ) ( 8 ，1 0 ，1 3 ) ( 9 ，1 2 ，1 7 ) ， ( 1 ，1 0 ，1 5 ) ( 2 ，9 ，1 8 ) ( 3 ，1 2 ，1 4 ) ( 4 ，l l ，1 7 ) ( 5 ，7 ，1 3 ) ( 6 ，8 ，1 6 ) ， ( 1 ，9 ，1 6 ) ( 2 ，1 1 ，1 3 ) ( 3 ，4 ，1 5 ) ( 5 ，1 0 ，1 7 ) ( 6 ，7 ，1 4 ) ( 8 ，1 2 ，1 8 ) ， ( 1 ，6 ，1 7 ) ( 2 ，1 0 ，1 6 ) ( 3 ，1 1 ，1 8 ) ( 4 ，9 ，1 3 ) ( 5 ，8 ，1 4 ) ( 7 ，1 2 ，1 5 ) ， ( 1 ，5 ，1 8 ) ( 2 ，7 ，1 7 ) ( 3 ，6 ，1 3 ) ( 4 ，1 2 ，1 6 ) ( 8 ，1 1 ，1 5 ) ( 9 ，1 0 ，1 4 ) ， h 1 = ( 1 ，2 ，3 ) ( 4 ，5 ，6 ) ( 7 ，8 ，9 ) ( 1 0 ，1 1 ，1 2 ) ，也= ( i ，4 ，8 ) ( 2 ，5 ，1 2 ) ( 3 ，7 ，l o ) ( 6 ，9 ，1 1 ) 将玩替换成( 1 ，4 ，8 ) ( 3 ，7 ，l o ) ( 2 ，5 ，1 1 ，9 ，6 ，1 2 ) ，可以得到4 2 a ( 1 8 ；6 ) 将日2 替 换成( 1 ，7 ，3 ，1 0 ，4 ，8 ) ( 2 ，5 ，1 1 ，9 ，6 ，1 2 ) ，可以得到4 0 a ( 1 8 ；6 ) 将日1 和日2 替换成 ( 1 ，2 ，3 ) ( 4 ，5 ，6 ) ( 7 ，8 ，9 ，1 1 ，1 2 ，1 0 ) 和( 1 ，4 ，8 ) ( 2 ，5 ，1 1 ，1 0 ，3 ，7 ，9 ，6 ，1 2 ) ，可以得到3 9 a ( 1 8 ；6 ) 将玩和日2 替换成( 1 ，2 ，3 ) ( 4 ，5 ，6 ) ( 7 ，8 ，9 ，1 1 ，1 2 ，1 0 ) 和( 1 ，4 ，8 ，2 ，5 ，1 2 ，6 ，1 1 ，1 0 ，3 ，9 ，7 ) ， 可以得到3 8 n ( 1 8 ；6 ) 将凰和日2 替换成( 1 ，2 ，3 ) ( 4 ，5 ，6 ，9 ，1 1 ，1 2 ，1 0 ，7 ，8 ) 和 ( 1 ，4 ，6 ，1 2 ，2 ，5 ，1 1 ，i 0 ，3 ，7 ，9 ，8 ) ，可以得到3 7 ( 1 8 ；6 ) 将日1 和日2 替换成( 1 ，2 ，3 ，7 ， 9 第三章主要构造完全图k 的三角形谱 8 ，9 ，6 ，5 ，1 1 ，1 2 ，1 0 ，4 ) 和( 1 ，3 ，9 ，7 ，1 0 ，1 1 ，6 ，4 ，5 ，1 2 ，2 ，8 ) ，可以得到3 6 z x ( 1 8 ；6 ) 这样， 我们就得到 3 6 ，4 4 4 1 ，4 3 cz x ( 1 8 ；6 ) 其次考虑设计4 1 z x ( 1 8 ；6 ) 设计由日1 ，日2 和下面的6 个平行类组成 ( 1 ，6 ，1 4 ) ( 2 ，1 0 ，1 5 ) ( 3 ，8 ，1 8 ) ( 4 ，1 1 ，1 6 ) ( 5 ，7 ，1 7 ) ( 9 ，1 2 ，1 3 ) ， ( 1 ，1 0 ，1 7 ) ( 2 ，6 ，1 3 ) ( 3 ，5 ，1 6 ) ( 4 ，9 ，1 8 ) ( 7 ，1 l ，1 4 ) ( 8 ，1 2 ，t 5 ) ， ( 1 ，5 ，1 8 ) ( 2 ，7 ，1 6 ) ( 3 ，6 ，1 5 ) ( 4 ，1 2 ，1 7 ) ( 8 ，1 1 ，1 3 ) ( 9 ，1 0 ，1 4 ) ， ( 1 ，9 ，1 6 ) ( 2 ，1 1 ，1 8 ) ( 3 ，1 2 ，1 4 ) ( 4 ，7 ，1 5 ) ( 5 ，1 0 ，1 3 ) ( 6 ，8 ，1 7 ) ， ( 1 ，1 1 ，1 5 ) ( 2 ，9 ，1 7 ) ( 3 ，4 ，1 3 ) ( 5 ，8 ，1 4 ) ( 6 ，1 0 ，1 6 ) ( 7 ，1 2 ，1 8 ) ， ( 2 ，4 ，1 4 ) ( 3 ，1 1 ，1 7 ) ( 5 ，9 ，1 5 ) ( 1 ，1 2 ，1 6 ，8 ，1 0 ，1 8 ，6 ，7 ，1 3 ) 对日l 和仍作与前面类似的替换，我们得到 3 3 ，4 1 4 0 ，3 8 ) cz x ( 1 8 ；6 ) 最后考虑设计3 2 z x ( 1 8 ；6 ) 设计由研，日2 和下面的6 个平行类组成 ( 1 ，5 ，1 3 ) ( 2 ，4 ，1 4 ) ( 3 ，6 ，1 5 ) ( 7 ，1 l ，1 6 ) ( 8 ，l o ，1 7 ) ( 9 ，1 2 ，1 8 ) ， ( 1 ，6 ，1 4 ) ( 2 ，7 ，1 3 ) ( 3 ，5 ，1 6 ) ( 4 ，1 2 ，t t ) ( 8 ，1 1 ，1 8 ) ( 9 ，加，1 5 ) ， ( 1 ，9 ，1 6 ) ( 2 ，6 ，1 7 ) ( 3 ，8 ，1 3 ) ( 4 ，1 1 ，1 5 ) ( 5 ，1 0 ，1 8 ) ( 7 ，1 2 ，1 4 ) ， ( 1 ，1 2 ，1 5 ) ( 2 ，1 0 ，1 6 ) ( 3 ，1 l ，1 7 ) ( 4 ，9 ，1 3 ) ( 5 ，8 ，1 4 ) ( 6 ，7 ，1 8 ) ， ( 1 ，1 0 ，6 ，8 ，1 5 ，2 ，9 ，1 7 ，5 ，7 ，4 ，1 6 ，1 2 ，1 3 ，1 1 ，1 4 ，3 ，1 8 ) ， ( 1 ，1 1 ，2 ，1 8 ，4 ，3 ，1 2 ，8 ，1 6 ，6 ，1 3 ，1 0 ，1 4 ，9 ，5 ，1 5 ，7 ，1 7 ) 对日1 和凰作与前面类似的替换，我们得到【2 4 ，3 2 3 1 ，2 9 】cz x ( t s ；6 ) 在附录中，我们给出了2 3 ，2 9 ，3 1 z x ( 1 8 ；6 ) 这就完成了证明 构造3 4 设( 阢9 ，b ) 是一个型为夕i - 毋咖的k i r k m a nf r a m e ，i v i = t 若对 一个固定的o ，存在棚的2 一因子分解；对每个1 i m ，存在玩+ t c ， 的不完全2 一因子分解，其中洞的大小为叫是偶数) ，则存在玩枷的2 一因子分解进一步，若( + 硼) 且盈慨+ ；t t j ) ( 1 i m ) ，则 1 9 仇 t i 优( t 一吼) + 1 9 m 屯盈一+ ( t + 叫) 证明令v = c r u o o t 摧1 对每个大小为吼的组q ，除了一个大小为的组 瓯外，在岛所对应的警个带洞平行类中填入玩扣( 在集合g ；u o o t ) 饕，上) 的不完全2 一因子分解中的学个平行类对于剩下的组瓯，在g 。所对应的 粤个带洞平行类中填入如帅( 在集合瓯u o o t ) 鉴，上) 的2 一因子分解中的 孚个2 一因子这样我们就得到了y 上的詈个2 一因子再将妫。佃的不完 全2 一因子分解中所有等一1 个带洞平行类并上玛。佃的2 一因子分解中余 下的詈一1 个2 一因子，我们得到甄的罟一1 个2 一因子这样我们就得到了 甄的+ 筹一1 个2 一因子，它们构成了甄的2 一因子分解经过计算，我 完全图k 矗的三角形谱 第三章主要构造 们得至i j l g m t l 吼( u 一骁) + 1 t mt i & 一+ 吃( + t ) ) 为了证明下面的构造，我们需要k o t z i g 和r o s a 的结果 引理3 5 ( 1 1 】) 可以将完全三部图，仉，m 分解成m 个边不重的2 一因子的充 要条件是m 2 ，6 构造3 6 设s 兰3 ( m o d6 ) 且t 兰0 ( m o d2 ) ，缸2 ，6 若对任意1 i s ， 盈( 钍) ，则幽6+ 1 沁魂( u s ) 若对任意1 i 8 ，氏( u + 1 ) ，则 兰2 6 苎= 型+ 1 t 上的一个2 一因子分解尸= t 毋= f + i ( m o di i ) ：t z 1 1 ) ，其中 f ：( 0 0 ，i o ，5 0 ) ( o l ，1 1 ，5 1 ) ( 6 0 ，8 0 ，9 1 ) ( 4 0 ，7 0 ，2 1 ) ( 9 0 ，6 1 ，8 1 ) ( 2 0 ，4 1 ，7 1 ) ( a ，3 0 ，1 0 1 ，b ，1 0 0 ，3 1 ) 这个2 一因子分解给出了6 6 ( 2 4 ) 令g ：( 6 0 ，s o ，9 1 ) ( 4 0 ，7 0 ，2 1 ) ( 9 0 ，6 1 ，8 1 ) ( 2 0 ，4 1 ，7 1 ) ( o o ，l o ，5 0 ，5 1 ，1 1 ，0 1 ) ( a ，3 0 ，i 0 1 ，b ，1 0 0 ，3 1 ) ， g = g + t ，t z 1 1 将昂，毋，易依次替换成g o ，g 1 ，g 2 ，可以得到6 4 ，6 2 ，6 0 a ( 2 4 ) ( 3 ) 考虑鲍4 在z 1 1 【o ，1 u a ，好上的一个2 一因子分解厂= 只= f + i ( , n o d1 1 ) ：t z l l ，其中 f ：( 0 0 ，i o ，3 0 ) ( 5 1 ，6 1 ，8 1 ) ( 2 0 ，6 0 ，9 1 ) ( 4 0 ，9 0 ，1 0 1 ) ( 7 0 ，0 1 ，4 1 ) ( 8 0 ，7 1 ，2 1 ) ，5 0 ，3 1 ) ( b ，1 0 0 ，1 1 ) 这个2 一因子分解给出了8 8 a ( 2 4 ) 令g ：( 0 0 ，l o ，3 0 ) ( 4 0 ，9 0 ，1 0 1 ) ( 7 0 ，0 1 ，4 1 ) ( a ，5 0 ，3 1 ) ( b ，1 0 0 ，1 1 ) ( 8 1 ，5 1 ，6 1 ，6 0 ，9 1 ，2 0 ，2 1 ，7 1 ，s o ) ， g i = g + i ，i 历1 将局，毋依次替换成g o ，g 1 ，可以得到8 5 ，8 2 ( 2 4 ) 令日0 ：( o o ，i o ，3 0 ) ，6 0 ，9 1 ) ( 4 0 ，9 0 ，1 0 1 ) ( 7 0 ，o l ，4 1 ) ( a ，5 0 ，3 1 ) ( b ，1 0 0 ，1 1 ) ( 5 1 ，8 1 ，6 1 ，7 1 ，2 1 ，s o ) ， h 1 ：( 1 0 ，2 0 ，4 0 ) ( 3 0 ，7 0 ，1 0 1 ) ( 5 0 ，1 0 0 ，0 1 ) ( 9 0 ，8 1 ，3 1 ) ( a ，6 0 ，4 1 ) ( b ，0 0 ，2 1 ) ( 6 1 ，9 1 ，7 1 ，s o ，1 1 ，5 1 ) ， 日2 t = h o + 2 i ，奶件1 = h 1 + 2 i ，t = 0 ，1 ，2 ，3 ，4 完全图鲍n 的三角形谱 第四章主要结果 将局和f 1 ，f 2 和玛，凡和屁，晶和乃，毋和局依次替换成凰和玩，玩 和风，皿和风，凰和珥，凰和凰，可以得到8 4 ，8 0 ，7 6 ，7 2 ，6 8 a ( 2 4 ) 将昂，见，晟，只+ 1 替换成凰，凰，风，g t + 1 i = 7 ，9 ，可以得到6 9 ，6 5 1 ( 2 4 ) 将昂和尼替换成( o o ，l o ，3 0 ) ( 5 1 ，6 1 ，8 1 ) ( 4 0 ，9 0 ，1 0 1 ) ( 7 0 ，0 1 ，4 1 ) ，7 1 ，2 1 ) ( o ，5 0 ，3 1 ) ( 9 l ， 2 0 ，6 0 ，1 1 ，b ，1 0 0 ) 和( 2 0 ，3 0 ，5 0 ) ( 7 1 ，8 1 ，1 0 1 ) ( 4 0 ，8 0 ，0 1 ) ( a ，7 0 ，5 1 ) 0 ，