（计算机软件与理论专业论文）不包含三边形四边形五边形的极图.pdf

不包含三边形四边形五边形的极图 摘要 图论( g r a p h t h e o r y ) 是数学的一个分支，它与数学的其他分支有密切的关系。这些 分支包括群论、矩阵论、数值分析、概率论、拓扑学和组合论等。事实上，图论为任何 一个包含二元关系的系统提供了一个数学模型；利用图直观、漂亮的表现特性可以使人 对现实的系统有清晰的了解。这个领域内的许多问题，即使是对图论一无所知的人，都 是非常容易理解的，但是想要得到这些问题的结论却要使聪明的数学家绞尽脑汁。 随着计算机科学与数学的发展，图论已经应用到了各个领域，其中包括物理学、化 学、通讯科学、计算机技术、土木工程、建筑学、运筹学、生物遗传学、心理学、社会 学、经济学、人类学和语言学等等，几乎包括了人类社会的所有领域。图论已经成为人 们研究自然科学以及社会科学的一个重要工具。 极图理论是图论中的重要组成部分。极图问题中最主要的一类问题是：给定一族图 = g l ，g 2 ，g 。) ，e x ( n ；扩) 表示由n 个顶点组成的不包含任一g ，的图的最多边数。 e x ( n ；扩) 表示由月个顶点组成的不包含任一g 。扩的边数最多的图( 极图) 的集合。 在不包含多边形的极图问题中，对于矿= c 4 ) 的极图问题，c l a p h a m 等人给出了所 有n 2 1 的极 ( j o u r n a lo fg r a p ht h e o r y ，v 0 1 1 3 ，1 2 0 1 ，( 1 9 8 9 ) ，2 9 4 7 ) ，杨元生等人给出了 所有2 2 n 3 1 时的极 ( u t i l i t a s m a t h e m a t i c a ，4 1 ，( 1 9 9 2 ) ，2 0 4 2 1 0 ) ；对于扩= f c 3 ，c 4 的极图问题，g a r n i c k 等人给出了n 2 4 的所有极 ( j o u r n a lo f g r a p ht h e o r y ，v 0 1 1 7 ，n o 5 ， ( 1 9 9 3 ) ，6 3 3 6 4 5 ) 本文主要研究了e = c 3 ，c 4 ，c 5 ) 时的极图问题，给出了n 4 2 时e x ( n ； c 3 ，c 4 ，c 5 ) ) 的 值以及n 4 2 时的情形，本文给出了 e x ( n ： c 3 ，c 4 ，c 5 ) ) 的上界。 关键词：极图：禁止子图：笼：正则图；围长 至璺宣三望垩巴望堡至望兰塑堡里 a b s t r a c t g r a p ht h e o r yi s ab r a n c ho fm a t h e m a t i c s g r a p ht h e o r yi sa l s oi n t i m a t e l yr e l a t e dt o m a n yb r a n c h e so fm a t h e m a t i c s ，i n c l u d i n gg r o u pt h e o r y , m a t r i xt h e o r y , n u m e r i c a la n a l y s i s ， p r o b a b i l i t y , t o p o l o g y , a n d c o m b i n a t o r i c s t h ef a c t i st h a t g r a p ht h e o r y s e r v e s a sa m a t h e m a t i c a lm o d e lf o ra n ys y s t e mi n v o l v i n gab i n a r yr e l a t i o n p a r t l yb e c a u s eo ft h e i r d i a g r a m m a t i cr e p r e s e n t a t i o n ，g r a p h sh a v e a l li n t u i t i v ea n da e s t h e t i ca p p e a l m a n yp r o b l e m si n g r a p ht h e o r ya r eu s u a l l yq u i t ee a s y t os t a t ea n d e x p l a i n ，e v e nf o rt h el a y m a n ，b u tt h e y a r et o o d i 街c u l tt os o l v ee v e nf o rt h em o s ts o p h i s t i c a t e dm a t h e m a t i c i a n w i t ht h ed e v e l o p m e n to f c o m p u t e rs c i e n c ea n dm a t h e m a t i c s a p p l i c a t i o n o f g r a p ht h e o r y t os o m ea r e a so f p h y s i c s ，c h e m i s t r y , c o m m u n i c a t i o ns c i e n c e ，c o m p u t e rt e c h n o l o g y , e l e c t r i c a l a n dc i v i l e n g i n e e r i n g ，a r c h i t e c t u r e ，o p e r a t i o n a lr e s e a r c h , g e n e t i c s ，p s y c h o l o g y , s o c i o l o g y ， e c o n o m i c s ，a n t h r o p o l o g y , a n dl i n g u i s t i c s ，e t c g r a p ht h e o r yt u r ni n t o a ni m p o r t a n tt o o lt o r e s e a r c ht e c h n o l o g ya n dn a t u r es c i e n c e ，e v e nf o rt h es o c i a ls c i e n c e e x t r e m a lt h e o r yi sa l li m p o r t a n tp a r to fg r a p ht h e o r y t h ep r i m ee x a m p l eo f a ne x t r e m a l p r o b l e m i st h ef o l l o w i n g ：g i v e nac l a s so f g r a p h s 5 g t ，g 2 ，g _ ，d e t e r m i n ee x ( n ；扩) t t h em a x i m u mn u m b e ro fe d g e si na g r a p ho fo r d e rnn o tc o n t a i n i n g 矿a s as u b g r a p h ， d e t e r m i n ee x ( n ；矿1 ，t h es e to f g r a p h sw i t h o r d e rna n dm a x i m u ms i z ea n dn o tc o n t a i n i n g a sas u b g r a p h f o rt h ee x t r e m a lp r o b l e m sn o tc o n t a i n i n gp o l y g o n ，f o r 2 ( c 4 ) ，c l a p h a mi n v e s t i g a t e dt h e v a l u e so fe x ( n ；g ) ( n 2 1 ) ( j o u r n a lo fg r a p ht h e o r y ，v 0 1 1 3 ，1 1 0 1 ，( 1 9 8 9 ) ，2 9 4 7 ) ，y u a n s h e n g i n v e s t i g a t e d t h e v a l u e so f e x ( n ；) ( 2 2 s 疗3 1 ) ( u t i l i t a s m a t h e m a t i c a ，4 1 ，( 1 9 9 2 ) ，2 0 4 _ 2 1 0 ) ； f o r 驴 c 3 ，c 4 ，g a r n i c ki n v e s t i g a t e dt h ev a l u e so fe x ( n ；0 - 2 4 ) ( j o u r n a lo f g r a p h t h e o r y ， v 0 1 1 7 ，n o 5 ，( 1 9 9 3 ) ，6 3 3 6 4 5 ) t h i s p a p e ri n v e s t i g a t e s t h ev a l u e so f e x ( n ；矿) f o r 矿。 c 3 ，c 4 ，c 5 ( n _ 4 2 ) g i v e s a l l g r a p h si n 戤功； c 3 ，c 4 ，c 5 1 ) ( n - 4 2 ) ，a n d s h o w su p p e rb o u n d sf o ra l l 驴4 2 k e y w o r d s ：e x t r e m a lg r a p h ；f o r b i d d e ns u b g r a p h ；c a g e ；r e g u l a rg r a p h ；g i r t h 2 不包含三边形四边形五边形的极图 前言 图论中的许多问题是在特定的条件下寻找具有最优属性值的图，通常把这些问题统 称为“极图问题”。 “t u r d n 原始极图问题”是最早提出的“极图问题”：找出由，z 个顶点组成的，不包 含完全图局( 图中的p 个顶点都相互邻接) 的图的最多边数以及具有上述性质的图极 图。 在t 9 3 5 年，在“t u r d n 极图问题”的启发下，e r d s s 和s z e k e r e s 用薪的思路和方 法重新证明了r a m s e y 定理。 在“r a m s e y 问题”中，有这样的一个假定：对于给定的正整数，与p ，当图g 的顶 点数足够大时，如果图g 不包含f 个相互独立o 个顶点的任意两个均不邻接) 的顶点，那 么g 中一定包含完全图髟 在“t u r d n 极图问题”中，也有一个类似的假定：对于给定的正整数p 嘲，如果由” 个顶点组成的图g 的边数足够多，那么g 一定包含完全图巧 尽管“r a m s e y 问题”迄今仍然没有实质性进展，但是“t u r d n 极图问题”却已经 有了相当漂亮的结果著名的t u r d n 定理。 “一般极图问题”是“原始极图问题”的推广，该问题要求找出满足下面条件的圈： 由n 个顶点数组成的，并且不包含一族禁止子图( 不以该族图中的任意一个图为子图) 的 边数最多的图。这样的图被称作为极图。 即使是由非常简单的图组成的禁止子图族，要确定相应极图的边数并且找出所有的 极图都是件非常困难的事情。到目前为止，只对少数包含特殊图的禁止子图族，才确定 出所有极图的边数和极图。 本文主要研究了禁止子图为三边形、四边形和五边形的极图问题，利用计算机构造 性证明与数学归纳法证明，给出了n o ) 个顶点，属于同一个集合中的顶点均不相互邻接，属于不 同集合中的顶点均相互邻接。 耳岍，舯表示完全m ( 疗p 1 ) 分图，该图共有p l 切2 + 印。个顶点，这些顶点被分到m 个集合中，各个集合分别包含p l ，p 2 ，砌( p | o ) 个顶点，属于同一个集合中的顶点均 不相互邻接，属于不同集合中的顶点均相互邻接。 “正则图表示所有顶点度均为k 的图。 ，暑) 一图表示围长为g 的缸正则图。 许，曲- 笼是指 ，曲一图中顶点数最少的图，它必须满足下面3 个条件： 1 为卜正则图； 2 围长为g ； 3 在满足前两个条件的图中，为顶点数最少的图。 1 1 5 常用的图的运算 吞t ( 矿，西表示图g 毫( y ，句的补图，其中坎西= h g ) ，段面= ( ( “，v ) l u ，v v ( g ) g 4 不包含三边形四边形五边形的极图 ( “，v ) g e ( g ) ) 若v i ，1 ：2 ，e 坎6 3 ，e l ，e 2 ，e 。耳6 3 ，那么 g - e l ，e 2 ，p 肌) 表示在图g 上删除一些边后得到的图。若n = 1 ，简记为g e l ； 6 斗扣l ，e 2 ，e m 表示在图g 上添加一些边后得到的图。若，l = 1 ，简记为g 斗e ； g - v l ，v 2 ，) 表示在图g 上删除一些顶点以及这些顶点相关联的边后得到的 图。若作= 1 ，简记为g v 1 若v g 坎回，那么 g u v ) 表示在图g 上增加一个孤立点后得到的图； g 斗v 表示在图g u v ) 上添加邻接v 与h g ) 中所有顶点的边后得到的图。 若图日为图g 的一个子图，那么 g - h 表示在图g 中删除e ( - 0 后得到的图。 若图g i = ( n ，e 0 ，图g z = ( v 2 ，易) 那么 g l ug 2 表示图( h u 坞，e l u 毋) m 表示从集合中删除元素a 后得到的集合。 1 2 极图问题 1 2 1 t u r d n 原始极图问题 图论中的许多问题都含有求极值的内容，这些问题被统称为“极图问题”。 t u r d n 是极图领域的先驱，极图理论是在t u r d n 原始极图问题的基础上发展起来的。 1 9 3 0 年r a r n s e y 证明了r a m s e y 定理，首先我们了解一下r a m s e y 定理。 定理1 1 ( r a m s e y 定理1 2 】) 对于任意一个大等于3 的正整数p ，一定可以找到一个最小 的正整数k ，使得对完全图蜀舫的边进行任意的一种2 着色中，必存在由同种颜色 的边组成的局：其中整数k 称为是不包含玛的经典r a m s e y 数，记作尺0 ) 为了进一步了解经典r a m s e y 数，下面给出r ( 3 ) _ 6 的证明，即对联 6 ) 进行边的 2 着色时，必存在由同种颜色的边组成的局 定理1 2r ( 3 ) = 6 证明：显然，可以将墨的边着色成两个c 5 ，而g 中不包含凰，所以r ( 3 ) 6 ；接下来 证明r ( 3 ) = 6 ； 设将塌研6 ) 两着色为g 和石，设v 是蜀中的一个顶点，因为v 与其余胛一1 个顶点 不包含三边形四边形五边形的极图 或者在g 中邻接，或者在召中邻接。因为片一l 5 ，不失一般性，不妨设至少有三个顶 点朝，2 2 ，的在g 中与v 邻接。如果这些点中任意两个相邻接，则它们与v 就形成一个 鹧；如果在g 中“l ，地，的均不相邻接，则u l ，u 2 ，哟在召中就形成岛，所以对凰6 ) 边的任意2 着色中，必存在由同种颜色的边组成的玛，故r ( 3 ) = 6 口 在r a m s e y 定理的启发下，在1 9 4 0 年t u r d n 提出了这样的问题：由珂个顶点组成的 不包含局( 3 p 酌的图中，最多的边数是多少? 边数最多的图有哪些? 这个的问题被称 作t u r d n 原始极图问题。 t u r d n 把满足下面3 个条件的图霸，d ( 1 s 豳劝定义为t u r d n 图5 1 j ： 1 图矗，d 为一个完全d 分图k m ， 2 ：。= ”， 3 k - n d l 1 ，i - i 鱼 即t u r d n 图霸。d 是将聆个顶点尽量均匀分成d 个部分的完全d 分图。 下面给出6 个顶点的所有t u r d n 图。 嘲臀褥西罾 死，2 桶，3t 6 ，3 喝，2 ，2t 6 ，4 桶i22 t 6 ，5 = k i i1i ，2t 6 6 = k i 111 ，1 图1 1t u r d n 图死，i ( 1 - k - - e ( h ) 在图g 上矽中剩下的顶 点都与p 邻接，集合中的顶点都与坎g d 矽中的顶点相邻接，集合s 中的顶点都与 h g ) 一& 中的顶点相邻接； 如果= o ，那么循环结束， 否则，设图日= g ，i = i + l ，继续进行上面的循环。 显然，每进行一次循环都会从形中移出至少一个顶点，不妨设经过m 次循环使 。o ，也就是通过牌次移动将中最初的个顶点移到m 个集合s ( 1 f m ) 中。 不包含三边形四边形五边形的极图 第1 次循环，将得到图g l ，可知e ( g 1 ) e ( g ) ，v ( g 1 ) 被分为s 1 和两个集合，属 于不同集合的顶点均相互邻接，s l 中的顶点相互对称所以均不邻接。 第2 次循环，将得到图g 2 ，可知e ( g 2 ) e ( g 1 ) ，并且将f ( g 2 ) 分为s i 、岛和三个 集合，属于不同集合的顶点均相互邻接，s l 、中的顶点相互对称所以均不邻接。 第m 次循环，将得到图g 。，可知e ( g m ) e ( g 州) ，g m 中的顶点被分到集合s i ， 岛中，属于不同集合的顶点均相互邻接，属于同一个集合中的顶点相互对称故均不邻接。 所以最终得到的图6 将是一个完全m 分图晦胆棚，其中a 为集合s 中的顶点数 由于g 不包含岛，进行对称操作后得到的图g 也不包含岛 所以m p 一1 ，故e ( g x ) - e ( g 2 ) e ( g m ) - e ( t n ，。) p ( 死p 1 ) ，即对任何”个顶点组 成的不包含昂的图g ，则p ( 回p ( ? 0 1 ) 再补充上证明1 中，当e ( g ) = e ( 矗p 1 ) 时，g 就是l p l 的证明，就得到结论。 口 这样t u r d n 原始极图问题就完全解决了，如果n = 妇1 ) + 岛0 - k 3 时，纵行； c 4 ) i 1n ( 1 + 4 n 4 t 五- 3 ) ：州 2 蹦( 疗；( c 4 ) = ( 1 2 + o ( 1 ) ) 玎m ；睁1 0 】 3 当t 为素数的幂，那么项f 2 + f + 1 ； c 4 ) “什1 ) 2 2 ，州 若t 为偶数，那么b f 2 + f + 1 ； c 4 ) “件1 ) 2 2 ，【4 】 若f 为奇素数的幂，那么e x ( t 2 + f + 1 ； c 4 ) ) n ( r + 1 ) 2 2 + ( 件1 ) 2 ； 5 1 4 当t 为2 的幂口i ，或者为超过1 3 的素数的幂【8 1 时，蹦( 产+ 什1 ； c 4 ) ) = “什1 ) 2 2 ，对 应的极图被构造于【9 f1 0 】； 5 c l a p h a m 等人给出了所有n 2 1 时e x ( n ； c 4 ) ) 的值以及相应的极图【4 】； n 1 0123456 7891 0 甜( h “c 4 ) ) 1 00134679 1 11 31 6 n l 1 l1 21 31 41 51 61 7 1 81 92 02 1 盯( h ； c 4 ) ) l 1 82 12 42 73 03 33 6 3 94 24 65 0 6 杨元生等人给出了所有2 2 n _ 3 1 时e x ( n ； c 4 ) ) 的值以及相应的极图瞪1 。 疗 i 2 22 32 42 52 62 7 2 82 93 03 l 蹦( n ；( c 4 ) j 5 25 65 96 36 7 7 17 6 8 08 59 0 2 3 不包含三边形四边形的极图问题 f = c 3 ，c 4 ) 时的极图问题已有如下结果： 1 0 不包含三边形四边形五边形的极图 1 e x ( h ；( c 3 ，c 4 ) = ( 1 2 + o ( 1 ) ) n s 彪；明 2 蹦( h ； c 3 ，c 4 ) ) 蔓妻n 而；【8 l 上 3 如果碳g ) = 3 ，盯( 磁 c 3 ，c 4 ) ) 去仃2 一1 ) 一号n ：嘲 4 若碳g ) = 3 且g 中顶点的平均度为整数，e x ( n ； c 3 ，c 4 ) - - - 寺1 n 2 ( n - 1 ) - 4 n ；【8 】 二 5 若r 为满足( t z + t + 1 ) n 的最大的素数，盯( ； g ，c 4 ) ) 2 珂+ ( f - 3 ) ( t 2 + t + 1 ) ；【8 】 6 g a m i c k 等人给出了下表中e x ( n ； c 3 ，c 4 ) 的值以及n 2 4 的所有极图8 l ； 以 i1 2 1 31 41 51 6 1 71 81 92 02 12 2 e x ( n ； c 3 ，c 4 ) ) i 1 82 12 32 62 83 13 43 84 14 44 7 7 对于n 1 2 时，e x ( 2 n + 2 ； c 3 ，c 4 ，g ) _ 2 n + 4 ；0 3 3 e x ( n ； k 2 ，2 ) ) = 1 2 矿陀+ 0 0 3 勺；【2 】 4 蹦0 ； c 4 ，c 5 ) ) ；( 以) 3 陀+ o 3 勺；【1 4 】 5 e x ( n ；g ) = 1 + ( ，z - 1 ) ( 疗- 2 ) 2 ：l ：q 6 e x ( n ；k 4 - 们= l 4 j ；”1 7 e x ( n ；k i 3 + o = l n 0 4 j ；p j 5 a l a b d u l l a t i f 对驴= c m 胂l ，g ) 及舻 r 抖l ，r ( 1 七s 行2 ) 时的极图问 题进行了研究，给出了较好的下界 1 i 】。 2 5 本文工作 本文研究了以= c 3 ，c 4 ，c 5 为禁止子图族的极图问题。利用计算机构造性证明 与数学归纳法证明，给出了n _ 5 2 ，k 4 2 ) 1 0 5 通过考察f ( n y 9 的图，v ge f ( n ) ，v v 坎6 3 ，记 ( = ( v i ，v 2 ，( ，； ，“= v m ) ， ( v ，) v = u ，l ，v l 2 ，一，u 一( u ) 一1 ) ，i i d ( v ) ， ( “) v = ( ，甜2 ，“d ( 。】一l ， n ( u ，) “= 蹦j t ，“，2 ，一，“，d ( ) 一1 ， 1 s i 蔓d ( ) - 1 ， 口 不包含三边形四边形五边形的极图 出v 1 一l s 。= u n ( v ，) v ， ， 1 c w j c v ) l _ 2 牡d 一t ”l i l ”1 ，d ( 仉卜l 瑚一l ，l ”d ( 啦一l ，d 一1 ) 一t 撇- l i ，, t c l - tu 峨, l - i ，lu a c u l - t ，d c 嘶c g ) 一l - t 图3 1 图g f ( n ) 的子图 g r a p h 3 1s u b g r a p ho f gf ( 月) 考察图3 1 中图g 子图的边数与顶点数，我们有 弓i 理3 2 ( a ) v g a f ( n ) ， v v 啊6 3 ， d ( v ) 州h ) 一l p 荆+ 地) i = l _ 1 ( b ) v g 户i 竹) ，v o ，”) e ( 6 _ ， 矾v hd ( 劬一1 胛2 + 地) + 泓吩) ( c ) v g e h n ) ，如果v ( v ，u ) e 耳g ) ，有d ( v ) + a ( u ) m ，则 d o 。- 1_ l e 荆+ 撕) + ) 一1 ) 一讹) ) 进一步，我们有 引理3 3 v g a 以行) ， ( a ) 艿1 2 e l , , i a _ 2 e n ， ( b ) e ( c ，2 一万+ 1 ) ， ( c ) e t ( n - 1 ) d k 葺 万r 云万。砸+ 1 ) 2 j ( 胛2 ) 证明：( a ) 由占与的定义，对任意珂个顶点的图g ，我们有占l 2 p 行_ l v 2 e n ( b ) vg 足n ) ，j v ev ( 6 3 ，吠v ) - ( g ) ，由引理3 2 ， 不包含三边形四边形五边形的极图 烈d ( h 卜1 p 荆+ 泓) 2 a + a ( 8 - 1 ) 占= a ( 8 2 - 6 + 1 ) i = 1 j = l 从而有 a e ( 6 2 一万+ 1 1 ( c ) 由 i - 2 p q - 2 时， p v 2 e 1 ， 当n 2 时， e t 2 e l n j _ 1 ， 万2 5 + 1 一 e l v 2 e l n u e o 一2 ) 一1 ， 珂一d ( ，力一d ( u ) t - 1 ( p n + 1 ) ， d ( v ) + d ( u ) n r 一1 ( p n + 1 ) 3 3 顶点个数不超过4 2 的不包含三边形四边形五边形极图的边数 口 对于顶点数h 1 0 的不包含三边形四边形五边形的极图，可以很容易地构造出来。 图3 2 中给出了2 1 0 时，不包含三边形四边形五边形的所有极图的集合职胛) ，其 中g “表示由力个顶点生成的第i 个极图。 。i 。l 岛，l瓯，lg t ，2岛，lg 5 ，2 士pgp9 可 ge 固固固 图3 2 足月) 中所有的图( 2 s 玎1 0 ) g r a p h 3 2a l lg r a p h s i n 孔甩) ( 2 n 1 0 ) 定义函数_ ) ，当2 ”1 0 时，令i 0 ) = “胆) 通过对图3 2 中所有图的观察和验证 就可以得到 ( 行) ( 2 ”1 0 ) 的值。 引理3 6 ；( 2 ) = “2 ) = 1 ， i ( 4 ) = “4 ) = 3 ， ( 6 ) = t ( 6 ) = 6 ， ( 8 ) = “8 ) = 9 ， ( 1 0 ) = t o o ) 2 1 2 ， 玎2 ) = 1 ：正( 3 ) 2 f ( 3 ) 。2 ，玎3 ) 。1 玎4 ) = 2 ；a ( 5 ) ；5 ) - 4 ，疋5 ) 2 3 玎6 ) = 1 ； ( 7 ) 。t ( 7 ) - 7 ，h 7 ) 2 2 玎8 ) = 1 ；石( 9 ) 爿( 9 ) 2 1 0 ， 孔9 ) 叫 “1 0 ) = 3 由【1 5 1 ，可知只存在唯一的( 3 ，6 ) - 笼，唯一的( 4 ，6 ) 一笼和唯一的( 5 ，6 ) 笼。 口 记( 3 ，6 ) - 笼，( 4 ，6 ) 笼与( 5 ，6 ) - 笼分别为g 1 4 ，q 6 与g 4 2 ，其对应的顶点集与边集 的关系如下： 矿( g 1 4 ) = v ，：0 i 1 3 ) ， e ( g 1 4 ) = ( v 2 。，”( 2 ) m d l 4 ) ，( v 2 ，”( 2 ) 。d 1 4 ) ，( v 2 。，v ( 2j + 1 3 ) m o dj 4 ) ：0 i 6 1 ， v ( g 2 6 ) = v ，：0 s i 2 5 ， e ( g 2 6 ) = ( v 2 f ，”( 2 f + 1 ) d 2 6 ) ，( v 2 j ，v ( 2 ) r e e d 2 6 ) ，( v 2 f ，v ( 2 7 ) m o d 2 6 ) ， ( v 2 ，”( 2 。+ 2 5 ) 。o d2 6 ) ：0 i 1 2 1 ， v ( g 4 2 ) = v ，：0 i 4 1 ， e ( g 4 2 ) = ( ( v 2 ”v ( 2 j + 1 ) m o d 4 2 ) ，p 2 。，v 2 。+ 1 ) m 柚4 2 ) ，( v 2 。，v t 2 。+ ”) m o d4 2 k ( v 2 。，”( 2j + 3 i ) m “4 2 ) ，( v 2 ，v ( 2 l + 4 1 ) 。4 2 ) ：0 s f s 2 0 接下来，在图3 3 中给出了( 3 ，6 ) 一笼g , 4 ，( 4 ，6 ) 一笼g 2 6 ，与( 5 ，6 ) - 笼g 4 2 的图。由 笼的定义可得，图g 1 4 ，g 2 6 与g 4 2 最小的围长为6 ，故图g g 2 6 与g 4 2 中不包含三边 形，四边形和五边形。 利用图g 1 4 ，g 2 6 与g 4 2 就可以构造出表3 1 中的图，其中图g ( 2 8 n 4 1 ) ，分别在 ( 5 ，6 ) - 笼g 4 2 的基础上通过逐步地删边得到的，所以图g ( 2 8 n 4 1 ) 的最小围长一定- - - 6 ； 而图g ( 1 5 门2 5 ) 是在( 4 ，6 ) 一笼g 6 的基础上逐步删边构造的，同样图中也不包含三边 形，四边形和五边形；而图g ( 1 1 n 1 3 ) 是通过( 3 ，6 ) 笼g 1 4 逐步删边构造得到的，同 样图中也不包含三边形，四边形和五边形：而g 2 7 = g 2 6 k ) v 2 6 + ( v 2 6 ，v l 是在( 4 ，6 ) 笼上 增加一个新的顶点v 2 6 ，并且新增加一条边，该边连接y 2 6 和( 4 ，6 ) 笼上任意一个顶点( 不 妨设为v o ) ，构造得到的图g 2 7 中的最小围长仍然为6 ；因此，表3 1 中给出的图g 1 6 不包含三边形四边形五边形的极图 ( 1 1 ”4 2 ) 的围长均不小于6 ，并且当1 1 ”蔓4 2 时，令函数j s ( n ) 2 e ( g n ) ，通过图3 3 和表3 1 中g 的公式就可以得至l j j i ( n ) ( 1 1 h 4 2 ) 1 拘值。 v 1 2 v 1 1 v 1 ( 3 ，6 ) 一笼( 3 ，6 ) 一c a g eg 1 4 v 4 v 5 ( 4 ，6 ) 一笼( 4 ，6 ) 一c a g eg 2 6 ( 5 ，6 ) 一笼( 5 ，6 ) 一c a g eg 4 2 图3 3 ( 3 ，6 ) 一笼g 1 4 ，( 4 ，6 ) 笼g 2 6 与( 5 ，6 ) 笼g 4 2 g r a p h 3 3 ( 3 ，6 ) - c a g eg 1 4 ，( 4 ，6 ) - c a g eg 2 6 ，( 5 ，6 ) - c a g eg 4 2 6 v 7 v 8 9 至皇鱼三望型些垫登至望型塑壑璺 表3 1 由图g 1 4 ，g z 6 和g 4 2 构造的围长不小于6 的图瓯( 1 1 即s 4 2 ) 及口( g ) t a b l e 3 1g r a p h sg ( 1 1 4 2 ) a n de ( 伉) c o n s t r u c t e df r o mg 1 4 ，q 6 a n d g 4 2 ， ”4 24 l4 03 93 83 73 6 g 。g 4 2g 4 2 一1g 4 1 - v og 4 0 y lg 3 9 - v 2g 3 s - v 3g 3 7 一v 1 4 z ( n ) = 8 ( 瓯) 1 0 51 0 09 69 28 88 48 1 抒3 53 43 33 23 13 02 9 g 。g 3 6 - v 1 5g 3 5 - v 1 6g 3 4 一v 1 7g 3 3 1 , 1 8g 3 2 v 7g 3 1 一v 8g 3 0 - v 9 五( 嘭= e ( c 。) 7 77 47 06 76 46 15 8 聆2 82 62 72 52 42 3 g 。g 2 9 - v 1 0g 2 6g 2 6 u v 2 6 ) + ( v 2 6 ，v 0 )g 2 6 一v og 2 5 一y ig 2 4 一v 2 一( 珂) = p ( 瓯) 5 65 25 34 84 54 2 w2 22 12 01 91 81 71 6 g 。g 2 3 - v 3g 2 2 - v 4g 2 1 - - v 5g 2 0 - - v 6g 1 9 - v 7g i s - - v 8g 1 7 - v 9 z ( n ) = e ( g 。) 3 93 63 43 12 92 62 4 盯1 51 41 31 21 1 g 。g 1 6 - v 1 0g 1 4g 1 4 - - v og 1 3 - v lg 1 2 - v 2 i ( n ) = e ( g 。) 2 22 l1 81 61 4 由表3 1 我们得如下结论 弓l 理3 7 当1 1 s 1 7 4 2 时，t ( n ) ( h ) 口 下面我们将对1 1 s n 兰4 2 用反证法来逐一证明t ( n ) y 1 1 ( n ) 假定t ( n ) a ( n ) + 1 ，则 存在g f ( n ) ，e ( g ) ( 功+ 1 从而，存在g 的一个生成子图g j g ，g 1 f ( 功 e ( g 。) = z ( ) + 1 在下面的引理证明中，我们通过证明这样的g 1 不存在，从而得出 t ( n ) s ：( h ) ，再由引理3 7 ，t ( n ) f l ( n ) ，得出t ( n ) = f x ( n ) 弓l 理3 8 当1 1 s n 1 4 时，f ( n ) = f l ( n ) 证明：当n 2 1 1 时，假定j g 1 f ( 1 1 ) ，p ( g 1 ) = 石( 1 1 ) + 1 = 1 4 + 1 = 1 5 由引理3 6 ，t ( 1 0 ) = 1 2 不包含三边形四边形五边形的极圈 由引理3 3 ，在圈g 1 中 e t ( n - 1 ) 巧l ( 耳 万r 五了砸+ d 2 j ， 3 = 1 5 1 2 5 - l ( 月面再冠研+ 1 ) 2 j ：2 ， 矛盾。从而，f ( 1 1 ) a ( 11 ) 由引理3 7 ，t 0 1 ) = 石( 1 1 ) = 1 4 用同样的方法可以证明， 当月5 1 2 时，假定s g i f ( 1