（计算机应用技术专业论文）若干图的染色.pdf

摘要 图的染色是一个应用非常广泛的学科，确定图的色数又是图论中一个重要内容。本文提 出了一种新的图运算一一等度，由此运算生成的图称为等度连图。文中分别讨论了其正常边 染色、邻点可区别边染色、全染色，最后给出该图的邻接矩阵的生成算法。为了方便、简单 地证明路的正常边染色、邻点可区别边染色，文中又引入了一个新的概念一一加图。在讨论 全染色时，没有使用常规的染色方法，提出了一种新的染色方法。该方法使得邻点可区别边 染色与全染色建立联系，为讨论全染色提供了便利。 除了讨论等度连图之外，还讨论了联图的正常边染色、邻点可区别边染色及其邻接矩阵 的生成算法。冠圈的正常边染色、邻点可区别边染色。最后给出路和圈的正常边染色的染色 算法。 关键词：等度连图；联图；冠图；邻接矩阵：正常边染色：邻点可区别边染色；全染 色。 a b s t r a c t t h ec o l o r i n gp r o b l e mo fg r a p h si sw i d e l ya p p l i e di n p r a c t i c e t h ec h r o m a t i cn u m b e ro f c o l o r i n gi si m p o r t a n tc o n t e n ta b o u tg r a p ht h e o r y an e wo p e r a t i o no fg r a p hc a l l e de q u a ld e g r e ei s d u et ob yu si nt h i sp a p e r , t h eg r a p hc r e a t e db yt h i so p e r a t i o ni sc a l l e de q u a ld e g r e ej u n c t u r eg r a p h i nt h i sp a p e r , w ed i s c u s st h ep r o p e re d g ec o l o r i n g ，a d j a c e n tv e r t e x - d i s t i n g u i s h i n ge d g ec o l o r i n g a n d t o t a lc o l o r i n g o f e q u a l d e g r e e j u n c t u r e g r a p h , a n d g i v ea r i t h m e t i co f a d j o i n m a t r i x i no r d e r t o p r o v et h ep r o p e re d g ec o l o r i n ga n da d j a c e n tv e r t e x - d i s t i n g u i s h i n ge d g ec o l o r i n go f p a t ho r d i n a r y , w ed u et oan e wc o n c e p t i o n a d dg r a p h h e nw ed i s c u s st h et o t a lc o l o r i n g ，w ed o n tu s et h e g e n e r a lm e t h o d ，a n dg i v e an e wm e t h o dw h i c he s t a b l i s h e dar e l m i o no ft h e a d j a c e n t v e r t e x - d i s t i n g u i s h i n gc o l o r i n ga n dt o t a lc o l o r i n g t h i sm e t h o di sg i v e nas i m p l ew a yf o r d i s c u s s i n gt o t a lc o l o r i n g e x c e p te q u a ld e g r e ej u n c t u r eg r a p h , w ea l s od i s c u s st h ep r o p e re d g ec o l o r i n ga n da d j a c e n t v e r t e x - d i s t i n g u i s h i n ge d g ec o l o r i n go f j o i ng r a p ha n dc o r o n a lg r a p h ，a n dg i v ea r i t h m e t i co f a d j o i n m a t r i x l a s t l yw eg i v et w oc o l o r i n ga r i t h m e t i co f p r o p e re d g ec o l o r i n go f p a t ha n dc y c l e k e yw o r d s ：e q u a ld e g r e ej u n c t u r eg r a p h , j o i n tg r a p h , c o r o n a lg r a p h , a d j o i nm a t r i x p r o p e re d g ec o l o r i n g ，a d j a c e n tv e r t e x - d i s t i n g u i s h i n ge d g ec o l o r i n g ，t o t a lc o l o r i n g i i 前言 自e u l e r 于1 7 3 6 发表图论的第一篇文章，图论发展经历的近三个世纪。在 此期间，许多伟大的数学家为图论的发展作出了巨大的贡献，同时取得了丰硕的 成果。1 8 5 8 年格里色提出了地图着色问题，标志着图论的一个重要分支的产 生一一图的染色。由于图的染色问题是一个n p 困难问题，使得许多数学工作者 都致力于这一工作。就图的边染色来说，已经得到很多重要的结果，见文献 8 1 一 1 5 1 ， 4 2 】。由不同实际问题引出了不同的染色概念，如仓库数的确定，地图染 色，有线通讯网、无线通讯网等引出的邻点可区别边染色，得到国内外图论研究 者的关注，现在产生许多有价值的成果，见文献 2 3 1 一【2 6 】， 4 3 1 一 4 4 1 。对于在图的 点染色和边染色的基础上产生的图的全染色问题的研究，已有系列结果和专著， 见文献 2 4 1 4 1 。近年来新提出的点可区别的全染色问题，鉴于其难度，现在所 做的工作很少。 在本文中，提出了一种新的图运算一一等度，由此运算产生的图称为等度连 图。除此之外，还考虑了另外两种图一一联图和冠图。在染色问题上，着重研究 图的正常边染色和邻点可区别边染色。在进行研究路的等度连图边染色时，给出 一种特殊的染色方式；在进行研究全染色前，给出了一个重要定理，使邻点可区 别边染色与全染色建立了关系，因此仅在等度连图中讨论了全染色，在联图和冠 图中就没再讨论全染色问题；最后给出了等度连图和联图的邻接矩阵的生成算 法。本文讨论的图都是一些简单连通的、无向的、有限图。文中所涉及的术语均 遵从文献【1 】、【4 】、【5 】、【6 】、 7 。 兰州大学硕士学位论文 1 若干等度连图的染色 1 1 基本知识 定义1 q 4 s 9 1 1 1 0 l 设图g 为一个简单连通图， 1 ，2 ，蛐为一个色集合，若，是一个从 e f q 到集合 l ，2 ，舛的映射，即 e ( g ) - - ) 1 ，2 ，蚰， 满足任意相邻的不同边p ，e 。e ( g ) n f ( e ) f ( e ) ，则称，为g 的一个正常j i 一边染色 简记作k p e co fg 。且称 z ( g ) = m i n k l k p e co fg ) 为g 的边色数。 1 9 6 5 年，h z i n g 证明了( 陀以g 定理) 【1 1 a ( g ) z ( g ) ( g ) + l ， 其中a ( g ) 为g 的最大度。但什么样的图g 有z ( g ) = ( g ) 或z 。( g ) = ( g ) + l 是一个至 今没有解决的问题。 定义2 z l 设厂为一简单连通图g 的正常七一边染色，则称，为g 的邻点可区别边染色 ( 简称k a v d e c ) ，当且仅当对v u v e ( g ) 有c ( u ) c ( v ) ，其中 c ) = ，( 州i 删e ( g ) ) ，f ( u w ) 表示对边u w 的染色；且称 ( g ) = m i n k lk a v d e co fg ) 为图g 的邻点可区别边色数。 猜想i 2 1 对i 矿( g ) 陲3 的连通图g ，若g c 5 ( 5 圈) ，则有 ( g ) ( g ) + 2 定义3 设g3 0 - - + i 瑜至_ , 3 , 3 02 的简单连通图，k 是一个正整数， 1 ，2 ，k ) 为 一个色集合，是y ( g ) u e ( g ) 到 1 ，2 ，舛的映射，如果 ( 1 ) 对v m , ，v w e ( g ) ，“w ，有f ( u v ) f ( v w ) ； - 2 兰州大学硕士学位论文 ( 2 ) v u v e ( g ) ，n f ( u ) f ( v ) f ( u v ) 则称，为g 的一个_ j 一正常全染色，简记为k p t c 。且称 z t ( g ) = m i n k i 后一p e co fg ) 为g 的全色数。 定义4 设g 为一个阶至少为2 的简单连通图，则称 ，( g ) 为g 的等度连图，当且仅当 满足 矿( m ( g ) ) = 矿( g ) ； m ( e ( g ) ) = e ( g ) u w i 如( “) = 蟊( v ) ，“v g e ( g ) ； 其中c l ( u ) 表示点“的度。 设有一简单图e ，则其等度连图如下图所示。 u 3 m ( p 5 ) 定义5 设图q 为一个阶至少为3 的完全图，外有一点w ，将完全图的某一点与1 4 ：相连 生成新图甲( k o + w ) ，则称甲( k + w ) 为k 与点w 的加图。 v ( k n + 神 兰i ! ：! ! 奎兰堕主堂篁丝苎 定义6 1 1 设图g 是一个有n 仰2 ) 个点的简单连通图，矿( g ) = “l ，“2 ，) ， 阶 方阵a ( g ) = ，其中 一 ：，麓i 鬈；一，； 则称矩阵爿( g ) 为图g 的邻接矩阵。 引理1 1 1 设图g 为一个简单连通图，则有石( g ) ( g ) + 1 。 引理2 【2 】设图g 为一个阶至少为2 简单连通图，则当g 有最大度点相邻时， z 0 耐( g ) ( g ) + 1 引理3 1 1 设图g 和日为两个简单图，若g c h ，则有z + ( g ) z ( 日) 。 引理4 2 1 设图g 和为两个简单图且都不为c ( 5 圈) ，若gc h ，则有 ( g ) 3 , n 。- - - 上l ( m 掣o d 丢7 ； i h ，玎之j ，玎夸z ) 证明： 对于圈可知，当r l = 3 时，c 3 即就是一个完全图；当玎3 时，v “，v vq ：c ：) 都有 d ( u ) = d ( v ) ，由等度连图的定义可知m ( g ) = k n 。 情形1 当 3 ，h = o ( m o d2 ) 时，m ( g ) = k n ，此时完全图为偶阶的，由引理5 可知z 。( 彳( q ) ) = 一1 ，此时定理4 为真。 情形2 当n 3 ，月；l ( m o d2 ) 时，m ( g ) = k n ，此时完全圈为奇阶的，由引理5 可 知z ( m ( e ) ) = r l ，此时定理4 为真。 综合上述二种情况定理4 为真。 定理5 对轮的等度连图m ( 矾) 白3 ) ，有 z m c 哪= p nr ”t 翥二：m 掣o o 著； l 。2 j ，h 三l lz i 证明： 兰州大学硕士学位论文 - _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ - - - _ _ _ _ _ _ _ _ _ _ _ _ _ 一 对于圈可知，当n = 3 时，= 巧，即本身就是一个完全图；当h 4 时，设 呒= w ，“2 ，$ 1 n ，x c u ，v 矿( ) 且“，v w 都有d ) = d ( v ) ，由等度连图的定义 可知此时m ( k ) = 情形1 当h 3 ，- = o ( m o d2 ) 时，肘( 形) = e + l 此时完全图为奇阶的，由引理5 可知z ( m ( ) ) = n + 1 ，此时定理5 为真。 情形2 当以3 ，行f - l ( m o d2 ) 时 f ( 睨) = 瓦+ l ，此时完全图为偶阶的，由引理5 可知z ( m ( ) ) = n ，此时定理5 为宾。 综合上述二种情况定理5 为真。 定理6 若图g 一个珂阶是七一正则图，则有 ( 1 ) m ( g ) = 疋 m 仰胪p ：篇芸 1 3 邻点可区别边染色定理 定理7 设图、壬，( k + w ) 为完全图疋与点w 的加图( w 岳g ) ，则有 如眦删= 篡器骂 证明： 由引理6 可知，当，z 9 0 ( m o d2 ) 时，z “( 蚝) = n + l ，对v ”e 都有d ) = 聆一1 ， 即i c ) | _ 竹一l 。由于w 只与完全图中的某一点u i 相连，对于“。e w ( k o + w ) 则有 d ( ) = 珂。由于瓦c w ( r o + w ) ，所以有疵呷( e + w ) ) 如( e ) = n + l ，为证明 此时定理成立，只需证明图- e ( e + w ) 存在( n + 1 ) 一a v d e c 。这显然是成立。设 c = l ，2 ，”+ 1 ，_ ( “) = c c ) ，由- t - v “巧都有i c ) l = n - 1 ，所以i 己q ) i = 2 。 由于w 只与完全图中的某一点“；相连，对于u 。甲( k + w ) 则有d ( u ；) = 聆，所以只需从 石( ”) 中取一种颜色染边w 虬即可。 兰州大学硕士学位论文 当h - = l ( m o d2 ) 时，如( e ) = n ，对v “k 都有d ) = n 一1 ，即i c ) i _ 竹一1 。 由于w 只与完全图中的某一点相连，对于u i 、壬，( + w ) 则有d ( u 。) = n 。由于 k n 匕甲( k + w ) ，所以有z ( 、王，( e + w ) ) z ( e ) = n ，为证明此时定理成立只需 证明图甲( k + w ) 存在”一a v d e ca 这显然也是成立的。设c = 1 ，2 ， ) 石 ) = c c ( “) ，由于v u e k 都有l c ) i = n 一1 ，所以有l 己 ) | _ 1 。由于w 只与完全图 中的某一点u l 相连，即图甲( b + w ) 只存在点“。为晟大度点，所以只需用c ( u ) 染边w u ，即 可。 综合上述两种情况可知定理7 为真。 定理8 对路的等度连图m ( 只) 白3 ) ，有 如c 懈炉裂 证明； 情形1 当n = 3 时，m ( p 3 ) = g ，由引理6 可知此时定理为真。 情形2 当h = 4 时，m ( 只) = c 4 ，由引理6 可知此时定理为真。 情形3 当n 5 时，由定理2 可知 彳( ) 包含一个完全图k 一2 ，所以可采用完全图的 加图染色方法对图 彳( 只) 进行染色。若将点u 1 和点“。分别视为完全图k 一：外一点，就构 成定义5 所谓的加图、王，( k 一2 + “1 ) 和甲( k 一2 + ) ，所以对图 f ( 只) 可采用完全图的加图 染色方法进行染色。 当以；- o ( m o d2 ) ，e v u k n 一2 都有d ( “) = ”一3 ，即l c ( u ) l = n 一3 。由于“，只与完 全图e 一2 的u 2 相连，可以看作加图甲( e 一2 + “1 ) ，所以有d ( “2 ) = 一2 。由定理7 可知 z , m ( w ( k o 一2 + “1 ) ) = ”一1 ，而加图、王，( 蚝一2 + ) c m ( p o ) ，由引理4 可知此时有 磊。( 肘( 只) ) 2 0 ( 甲( 瓦一：+ m ) ) = ”一1 。为证明此时定理成立，只需证明图m ( 只) 存 在0 1 ) 一a v d e c 。这显然是成立的。设c = 1 ，2 ，玎一1 ) ，c ) = c c ) ，现只考 虑完全图e 一：，由于v k 一：都有d ( u i ) = n - 3 ，e p i c ( u , ) i = 7 1 - - 3 ，所以i 石( ) i = 2 。 由于 1 只与完全图k n 一2 中的点“2 相连，对于加图甲( e 一2 + u 1 ) 则有d ( 屹) = n 一2 ，所以只 兰鲨堡圭堂生丝苎 需从c ( “z ) 中取一种颜色染边“i u 2 即可。由于“。只与完全图k 一：中的点一l 相连，对于加 图甲( k 一2 + “。) 则有d ( 一- ) = n 一2 ，所以只需从 ( “。) 中取一种不同于毡“：的颜色对边 u n l “。染即可。 当胛2 l ( m o d 2 ) ，对v 甜瓦一2 都有d ( “) = n 一3 ，目p l c ( u ) i = ”一3 。由于毡只与完 全图k 一2 的“2 相连，可以看作加图甲( 一2 + “1 ) ，所以有d ( “2 ) = h 一2 。由定理7 可知 z ( 甲( k 一2 + ) ) = 疗一2 ，而加图甲( 一2 + m ) c m ( 只) ，由引理4 可知此时有 z 0 ( m ( 只) ) z 0 ( 、王，( k 一：+ ) ) = n 一2 。为证明此时定理成立，首先证明图w ( 只) 不 存在一2 ) 一a v d e c 。 假设图m ( 只) 存在0 2 ) 一a v d e c ，对于图 彳( 只) 显然存在两个最大度点也，u n _ l ， r d ( u z ) = d ( - 1 ) = h 一2 ，由引理2 可知如( m ( e ) ) n - 1 ，与假设相矛盾，所以m ( 只) 不存在一2 ) 一a v d e c 。下面只需证明 f ( e ) 存在0 一1 ) 一a v d e c 。 设c = l ，2 ，月一1 ) ，c ( “) = c c ) 。先对加图、壬，( e 一2 + ”1 ) 进行邻点可区别边染 色，由定理7 可此时只需要行一2 种色。对加图甲( k 一2 + ) 进行邻点可区别边染色时，完 全图的染色不动，只需要对边一1 进行染色。由于当前只使用了b - - 1 种色中的疗一2 种， 所以用剩余的一种色对虬一1 u n 进行染色，这时显然有c ( “2 ) c ( u ) 。因此 z ( 只) 存在 一1 ) 一a v d e c 。 综合上述三种情形可知定理8 为真。 定理9 对圈的等度连图 彳( g ) 白3 ) ，有 z 二( m ( c o = 麓筠骂 证明： 对于圈可知，当珂= 3 时，c 3 即就是一个完全图；当珂3 时，v u ，v y ( g ) 都有 d ( u ) = d ( v ) ，由定理6 可知m ( g ) = 疋。 情形1 当n 3 ，n ；o ( m o d2 ) 时，m ( c n ) = 镌，此时完全图为偶阶的，由引理6 兰1 l 大学硕士学位论文 可知z ( f ( c ：) ) = n + l ，此时定理9 为真。 情形2 当挖3 ，n ；l ( m o d2 ) 时，m ( e ) = 疋，此时完全图为奇阶的，由引理6 可 知1 名口( 彳( q ) ) = n ，此时定理9 为真。 综合上述二种情况定理9 为真。 定理1 0 对轮的等度连图m ( ) 3 ) ，有 如( 哪= 删n - - - l ( m o ( m o 鞫 证明： 对于圈可知，当r l = 3 时，= k 4 ，即本身就是一个完全图；当n 4 时，设 y ( ) = w ，$ 1 1 ，“2 ，) ，对v u ，v 矿( ) 且“，v w 都有a ( u ) = a ( v ) ，由等度连图的 定义可知此时m ( ) = g n + 1 。 情形1 当行3 ，以s 0 ( m o d2 ) 时， f ( ) = 巧+ l ，此时完全图为奇阶的，由引理6 可知z “( m ( ) ) = n + l ，此时定理1 0 为真。 情形2 当竹3 ，h = l ( m o d2 ) 时，m ( 呒) = k + 1 ，此时完全图为偶阶的，由引理6 可知z “( 彳( ) ) = h + 2 ，此时定理1 0 为真。 综合上述二种情况定理1 0 为真。 1 4 全染色定理 定理1 1 设g 为一个阶至少为2 的简单连通图，如果g 中存在两个最大度点相邻，则有 。拓“( g ) = ( g ) + 1汐石( g ) = ( g ) + l 。 证明： 充分性。假设厂是g 的一个( ( g ) + 1 ) 一a v d e c ，令c = 1 ，2 ，( g ) + 1 ) ， 刁 ) = c c ( “) 。则有对v ”矿( g ) 都有i c ) 恒( g ) ，即l 石 ) 陲1 。令，如下 ( 1 ) d ) = ( g ) y ( g ) ) ，有，+ ) = 石 ) ( 2 ) d ( “) ( g ) 矿( g ) ) ，则从_ ( “) 中选取一种色对点进行染，且满足 兰州i 大学硕士学位论文 可知z 。( f ( q ) ) = n + l ，此时定理9 为真。 情形2 当n 3 ，h s l ( m o d2 ) 时，m ( e ) = e ，此时完全图为奇阶的，由引理6 可 知五d ( ，( e ) ) = h ，此时定理9 为真。 综台上述二种情况定理9 为真。 定理1o 对轮的等度连图 f ( ) 白3 ) ，有 如胪删n - - - l ( m o 鞫 证明： 对于圈可知，当h = 3 时- = k 4 ，即本身就是一个完全图；当以4 时，设 y ( 睨) = ( w ，“l ，“2 ，“月) ，对v “，v 矿( 呒) 且“，v w 都有d ) = d ( v ) ，由等度连图的 定义可知此时m i ( k ) = k h a 情形1 当n 3 ，”s o ( m o d2 ) 时， f ( ) = 晖“，此时完全图为奇阶的，由引理6 可知z 。d ( m ( e ) ) = n + l ，此时定理1 0 为真。 情形2 当月3 ，h = l ( m o d2 ) 时m ( 暇) = k n 十1 此时完牟图为偶阶的，由引理6 可知z “( 吖( 酩) ) = h + 2 ，此时定理1 0 为真。 综合上述一种情况定理1 0 为真。 1 4 全染色定理 定理u 设g 为一个阶至少为2 的简单连通图，如果g 中存在两个最大度点相邻，则有 ( g ) = ( g ) + 1移石( g ) = ( g ) + 1 。 证明； 充分| 生。假设厂足g 的一个( ( g ) + 1 ) 一a v d e c 令c = 1 2 ，( g ) + 1 ， 百 ) = c 、c ( “) 。则有对v 甜矿( g ) 都有i c 恤) 峰( g ) ，即l _ ( 甜) 陲1 。令，如下 ( 1 ) d 0 ) = a ( 6 3 ( u y ( g ) ) ，有，+ 啊) = 石 ) ( 2 ) d ( “) ( g ) 似矿( g ) ) ，则从_ ( “) 中选取一种色对点进行染，且满足 ( 2 ) d ( “) 2 n + 1 ，t a k em o d ”+ 1 ) ，i = 1 ，2 ，n ；j = 1 ，2 ，- ，玎+ 1 ； 厂( k + l v ，) = ，i = 1 ，2 ，”； f ( v j v s + 1 ) = j + 2 ，i = 1 ，2 ， 一2 ； ，( 一1 ) = 1 ； ，吨v 1 ) = 2 ； 显然f 是最v 的( 2 n + 1 ) 一p e c ，从而结论为真。 定理1 6 当m t = 3 时，有 z c 最v 吩，惹 证明： 情形1 当m = 4 时，墨v 暇= 瓯v 蚝，( 只v k 4 ) = 8 ，v i z i n g 定理可知 z ( 墨v ) - 8 。假设z ( 只v ) = 8 ，1 五( s v ) 卜3 0 ，显然至少存在6 色染4 条边。 由于l v ( s 4 v ) 卜9 ，则说明瓯v 存在6 个最大匹配，但s v 中只有5 个最大度点， 分别为u 5v i ，v 2 ，v 3 ，心，显然不存在6 个最大匹配，所以有z 。( 只v ) 9 。而& v c k 所以有z 。( 蜀v 暇) = 9 情形2 当m 5 时， 设c = 1 ，2 ，2 n + l ，令，为 ，( v 4 q ) = f ，i = 1 ，2 ，3 ； f ( v l v = ) = 3 ，( v 2 坞) = 1 ，( 屹v 1 ) = 2 ； f ( v 4 u j ) = j + 3 ，j = l ，2 ，r e + l ； 1 7 - 兰州大学硕士学位论文 f ( v f u j ) = i + j + 3 ( fi + j + 3 m + 4 ，t a k em o dr e + 1 ) ，i = 1 ，2 ，3 ；j = 1 ，2 ，m + l f ( u 。+ 1 “1 ) = m + 3 f ( u u i ) = i - 1 ，i = 2 ，3 ，4 ； f ( u 。+ 1 ) = “2 ，i = 5 ，6 ，m ； 显然，是最v 暇的( m + 4 ) 一p e c ，从而结论为真。 定理1 7 当m 4 ，有 证明： z ( 瓯v ) = m + n + 1 当m ”4 时( v ) = d ( u ) = d ( + 1 ) = m + n + l ，由v i z i n g 定理可知 z ( 最v 睨) m + n + l ，为证明此时结论成立，只需证明最v 存在( m + ”+ 1 ) 一p e c 。 情形1 当m 一”= 1 时。 设c = 1 ，2 ， n + h + 1 ) ，令，为 ，( h + lv ) = f ，扛1 ，2 ，聆； f ( v , v t + 1 ) = i + 2 ，i = l ，2 ，n 一2 ； 厂( 一l 心) = 1 ；，( v 1 ) = 2 ； 厂( b + l u j ) = n + y ，j = 1 ，2 ，川+ l ； f ( v , u j ) = i + j + n ( i fi + j + n r n + n + l ，t a k em o dr e + 1 ) ，i = 1 ，2 ，m + l ；j = 1 ，2 ，r t 一1 ； f ( v u 1 ) = r n + r t + i ；f ( v u 2 ) = 3 ； f ( v u 。) = 竹+ i 一2 ，i = 3 ，4 ，m + l 厂( ”。+ i u l ) = m + n ； f ( u m + 1 “j ) = ，一1 ；y = 2 ，3 ，m ； 显然，是瓯v 睨的( 所+ h + 1 ) 一p e c ，从而结论为真。 情形2 当m 一玎= 2 时， 设c = 1 ，2 ，坍+ 月+ b ，令，为 兰州大学硕士学位论文 f ( u u 。) = f ，i = 1 ，2 ，m ； 厂( + l v j ) = m + j ，j = 1 ，2 ，n + l ； f ( u ，v ) = i + j ( i fi + j m ，t a k em o dm ) ，i = 1 ，2 ，m 一1 ；j = 1 ，2 ，n + l f ( u 。v j ) = ，= 1 ，2 ，”+ 1 ； ，( h + 1 v j ) = m + j + l ，= 1 ，2 ，n 一1 ； 厂( 1 0 + 1 1 0 ) = m + 1 ；f ( v l v 2 ) = m + n + l f ( v j v j + 1 ) = 珊+ ，一1 ，= 2 ，3 ，n 一1 ； ，( k v l ) = m + n 一1 ； 显然，是v 睨的( m + 聆+ 1 ) 一p e c ，从而结论为真。 情形3 当m n 3 时， 设c = 1 ，2 ，m + 行+ 1 ) ，令，为 f ( u 。+ 1 1 , l 。) = f ，i = 1 ，2 ，卅； f ( u v j ) = m + j ，= 1 ，2 ，h + l ； ，( 屿q ) = i + j ( i fi + j m ，t a k em o dm ) ，i = 1 ，2 ，m ；j = 1 ，2 ，仃+ 1 ； ，( + 1v ，) = m + j + l ，j = 1 ，2 , - - - , ”一1 ； ，( + 1 1 _ ) = m + 1 ；f ( v ：2 ) = m + 聍+ 1 ； f ( v j v j + 1 ) = m + j 一1 ，= 2 ，3 ，竹一1 ； ，( 吒v 1 ) = m + n l ； 显然厂是咒v 的( 棚+ n + 1 ) 一p e c ，从而结论为真。 综合上述三种情况，定理1 7 为真。 定理1 8 当3 m 4 f ( u 4 u ，) = f ，i = 1 ，2 ，3 ； f ( u 4 g j ) = j + 3 ，= 1 ，2 ，n + 1 ； f ( u , v j ) = i + j + 3 ( t fi + j + 3 n + 4 ，t a k em o d ”+ 1 ) ，i = l ，2 ，3 ；j = 1 ，2 ，n + l ，( k + l v j ) = j + 7 ，= 1 ，2 ，n 一4 ； 厂( 吒+ 1 v j ) = ，一2 ，j = 胛一3 ，n 一2 ，n 一1 ； f ( v o + l v o ) = 7 ；f ( v , v 2 ) = n + 4 ； f ( v ：j + 1 ) = j + 2 ，= 2 ，3 ，n 一2 ； f ( v o 1 ) = 1 ；f ( v ：1 ) = 2 ； 显然，是s 3 v 既的0 + 4 ) 一p e c ，从而结论为真。 情形2 当n m = l m 3 时， 兰州大学硕士学位论文 设c = 1 ，2 ，m + n + 1 ) ，令，为 ，( + lv f ) = f ，i = 1 ，2 ，n ； 厂( k + 1 u j ) = ，+ r l , ，= 1 ，2 ，m + l ； f ( v , u ，) = i + j