（基础数学专业论文）几类线图的tutte唯一性.pdf

本学位论 授权北京交通 提供阅览服务 同意学校向国 ( 保密的 学位论文 签字日期 中图分类号：0 1 5 7 5 皿c ：5 1 9 1 、n * w ，一，胡嘲ih 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 几类线图的t u t t e 唯一性 t u t t eu n i q u e n e s so fs e v e r a lk i n d so fl i n eg r a p h s 作者姓名：李文俏 导师姓名：郝荣霞 学位类别：理学 学号：0 8 1 2 2 1 l o 职称：教授 学位级别：硕士 学科专业：基础数学研究方向：图论及其应用 北京交通大学 2 0 1 0 年6 月 致谢 本论文的工作是在我的导师郝荣霞教授的悉心指导下完成的，郝荣霞教授学 识渊博，治学严谨，在学习及科研工作中给了我极大的帮助。人的成长过程中会 遇到许许多多的老师，但真正教书育人，传道授业解惑者很少，郝荣霞教授正是 这样一位恩师，她的精益求精的工作作风，诲人不倦的高尚师德，严以律己宽以 待人的崇高风范，朴实无华，平易近人的人格魅力以及科学的教学方法，给我很 大影响，使我终身受益。在此衷心感谢两年来郝荣霞老师对我的关心和指导。 何卫力教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。同时也要感谢北京变通大学数学系的所有老师，自2 0 0 8 年我进入北京 交通大学以来，老师们的教导和帮助使我不断成长，他们都是我的良师益友，在 此对他们表示感谢。 在论文的研究和撰写论文期间，张锐，周玎，金正国，石淼，白冬蕾等同学 给予了我热情帮助，在此向他们表达我的感激之情。 另外也要感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学 、i k 。 中文摘要 摘要：近年来，图的多项式一直都是一个活跃的研究课题。它是图与传统代数之间 的一座桥梁。图的多项式包含了丰富的组合信息，所以图多项式的研究可以为我 们了解图的复杂结构和参数提供新的途径。 在研究图的相关性质及应用的很多文章中用相关的多项式不变量来刻画图类， 如特征多项式，匹配多项式，色多项式，流多项式，t u t t e 多项式，亏格分布多项 式，全嵌入分布多项式等。其中色多项式，流多项式和t u t t e 多项式是图论中三个 非常重要的多项式这三个多项式之间有非常重要的联系，其中色多项式和流多项 式在某种意义上具有“对偶性”，并且他们都是t u t t e 多项式的特殊形式。所以， 近些年很多研究都是关注于t u t t e 多项式以及能够由t u t t e 多项式唯一决定的图。 本论文主要研究了线图的t u t t e 多项式的唯一性。我们称图g 是t 一唯一的当 且仅当任何与图g 有相同t u t t e 多项式的图都与g 同构。图的t u t t e 多项式是图论 中一个非常重要的内容，它不仅与拟阵和图的色多项式有很大联系，而且我们可 以根据图的t u t t e 多项式得到图的很多信息，如顶点数，边数等，另外，图的t u t t e 多项式还可以唯一决定一些图类。 已经有很多学者在图的t u t t e 唯一性方面做了人量的研究并且得到了一系列的 成果。但是大部分的线图的t u t t e 唯一| 生还没有得到结论。 本论文在前人的研究基础上主要研究了两类图梯形图和十二面体的线图 的t u t t e 唯一性。 第一章对图的t u t t e 多项式及其t u t t e 唯一性的相关概念和背景知识进行简要介 绍，对文章的结构和各章内容进行简介。 第二章研究了梯形图的线图的t u t t e 唯一性，并且得到如下结论：当，z 6 ， n 4 ，i = 2 , 3 时，若日是与三( 三。) t _ 等价的平面图，则h 一定同构于( 厶) 。而 当n = 4 i ，i = 2 , 3 ，时，l ( l 竹) 是不满足严唯一性的。 第三章证明了十二面体的线图是满足t u t t e 唯一| 生的。 关键字：t u t t e 多项式；线图；t u t t e 唯一性；梯形图；十二面体 分类号：0 1 5 7 5 a b s t r a c t a b s t r a c t ： t h es t u d yo fg r a p hp o l y n o m i a l sh a sb e e na na c t i v er e s e a r c ht o p i cf o rm a n yy e a r s i t s e r v e sa sab r i d g eb e t w e e ng r a p ht h e o r ya n dt r a d i t i o n a la l g e b r a s i n c et h ec o e f f i c i e n t so f p o l y n o m i a l so f t e n c o n t a i nr i c hc o m b i n a t o r i a li n f o r r m t i o n , t h es t u d yo fg r a p h p o l y n o m i a l sp r o v i d e sn e w a v e n u e st ou n d e r s t a n dt h ec o m p l i c a t e ds t r u c t u r e so fg r a p h s a n d 伊a p h i cp a r a m e t e r s i nt h ea r t i c l e sw h i c hs t u d yt h ep r o p e r t i e sa n da p p l i c a t i o n so fag r a p h , s o m e p o l y n o m i a l ss u c ha st h em a t c h i n gp ol y n o m i a l ，t h ec h r o r m t i cp ol y n om i a l , t h ef l o w p o l y n o m i a l ，t h et u t t ep o l y n o m i a l , t h eg e n u sd i s t r i b u t i o np ol y n o m i a l ，a n dt h et o t a l e m b e d d i n gd i s t r 南u t i o np o l y n o m i a la r eu s e dt od e s c r i b et h eg r a p h s a m o n gw h i c h , t h e c h r o m a t i cp o l y n o m i a l ，t h ef l o wp o l y n o m i a l ，a n dt h e t u t t ep o l y n o m i a la r et h r e e i m p o rr a n tg r a p hp ol y n o m i a l si nt h eg r a p ht h e o r y t h e yh a v eac l o s er e h t i o n s h i pw i t h e a c ho t h e r t h ef l o wp o l y n o m i a lc a nb ec o n s i d e r e da st h ed u a lo ft h ec h r o m a t i c p o l y n o m i a l ，a n db o t ho f t h e ma r ee v a l u a t i o n so f t h et u t t ep o l y n o m i a lt h e r e f o r e ，m a n y s t u d i e si nr e c e n ty e a r sa r ef o c u s e do nt h et u t t ep o l y n o m i a la n dg r a p h st h a tc a n d e t e r m i n e du n i q u e l yb yt h et u t t ep o l y n o m i a l t h i sp a p e rm a i n l ys t u d i e st h eu n i q u e n e s so ft u t t ep o l y n o m i a lo fl i n eg r a p h s w es a y t h a tag r a p hgi st u n i q u ei f a n yo t h e rg r a p hh a v i n gt h es a m et u t t ep o l y n o m i a la sg i s i s o m o r p h i ct og t h et u t t ep o l y n o m i a lo f ag r a p hi sa ni m p o rt a n tp a r to fg r a p ht h e o r y i tn o to n l yh a sm a n yr e l a t i o n s h i p sw i t hm a t r i o da n dc h r o m a t i cp ol y n o m i a l s ，b u ti ta l s o c o n t a i n sab to fi n f o r m a t i o na b ou tt h eg r a p h , s u c ha st h en u n a b e ro fv e r t i c e s ，t h e n u m b e ro f e d g e s ，a n ds oo i lw h a ti sm o r e ，s o m ef a m i l i e so fg r a p h sa r ed e t e r m i n e db y t h e i rt u t t ep ol y n om i a l s o m es c h o l a r sh a v ed o n eal o to f r e s e a r c ha b o u tt h eu n i q u e n e s so ft u t t ep o l y n o m i a l , a n dt h eu n i q u e n e s sf o rs e v e r a lf a m i l i e so fg r a p h sa n dl i n eg r a p h sh a v eb e e nd i s c u s s e d b u tl i t t l ei sk n o w na b o u tt h eu n i q u e n e s so f t u t t ep o l y n o m i a lf o rm o s tl i n eg r a p h s i nt h i sp a p e r , w es t u d yt h eu n i q u e n e s so ft u t t ep o l y n o m i a lo ft w ok i n d so fl i n e g r a p h s t h el i n eg r a p h o fl a d d e r s ( l ) a n dt h el i n eg r a p ho f t h ed o d e c a h e d r o no nt h e b a s i so f t h ep r e v i o u sr e s e a r c h i nc h a p t e ro n e ，w ei n t r o d u c et h ec o n c e p t sa n db a c k g r o u n do f t h eu n i q u e n e s so f t u t t e p o l y n o m i a l i na d d i t i o n , w eg i v et h es t r u c t u r ea n dt h ec o n t e n to fe a c hc h a p t e ro ft h i s p a p e rb r i e f l y i nc h a p t e rt w o , w es t u d yt h eu n i q u e n e s so ft u t t ep ol y n o m i a lo ft h el i n eg r a p ho f l a d d e r sl ( l ，t ) a n do b t a i nt h e f o u o w i n gc o n c l u s i o n ：i fhh a s t h es a m gt u t t e p o l y n o m i a lw i t h ( 厶) a 耐hi s ap h n eg r a p h , t h e nhi s i s o m o r p h i ct o 也) f o r n 6 na n dn 4 i ，= 2 ，3 ；a n dt h e ya r en o tt - u n i q u ef o rn = 4 ia n di = 2 , 3 i nc h a p t e rt h r e e ，w ep r o v et h el i n eg r a p ho f t h ed o d e c a h e d r o ni st - u n i q u e k e y w o r d s ：t u t t ep o l y n o m i a l s ；l i n eg r a p h s ；t h eu n i q u e n e s so ft u t t ep o l y n o m i a l s ； l a d d e r s ；d o d e c a h e d r o n c l a s s n o ：o1 5 7 5 v 目录 中文摘要：i i i a b s t r a c t i 、， 第一章绪论1 1 1 背景知识1 1 2 已知结论3 1 3 重要引理3 第二章梯形图的线图的t u t t e 唯一性7 第三章十二面体的线图的t u t t e 唯一性1 6 结论2 0 参考文献2 2 作者简历2 4 独创性声明2 5 学位论文数据集2 6 1 1 背景知识 第一章绪论 早在1 9 5 4 年，t u t t e 就首先提出了t u t t e 多项式的概念。刚了f ：始，t u t t e 称这 个双变量多项式为图的二色性，但是现在人们都习惯把这个多项式称为t u t t e 多 项式。 设图g = ( y ，e ) ，其中v 是g 的顶点集，是边集，假设图g 没有孤立顶点， 但是可以有环或者重边。边集e 的子集彳的秩是指g 中由彳导出的生成森林的 边数，即：r ) = i v i k ( gi a ) ，其中k ( gl a ) 是指g 中由a 诱导出的生成子图 的连通分支数。令n ( a ) = l a i r ( a ) 图g 的t u t t e 多项式定义如下： 7 1 ( g ；_ y ) = 一e ( x 一1 ) 7 ( 且) 一r ( 4 ) ( ) ，一1 ) i a i r ( m ， 设两个图g 1 和g 2 满足r ( a 1 ；墨y ) = t ( g z ；x ，) ，) ，则称图g 1 和g 2 是t - 等价 的。若任何与图g 满足t 一等价的图日都是与g 同构的，那么称图g 是t u t t e 唯 一的，也简称t - 唯一的。 t u t t e 多项式在图论中有着很重要的地位，因为它包含了图g 中的很多信息， 其中一个重要的应用是：若x ，y ( 1 ，2 】，我们可以通过计算丁( g ；x ，y ) 在平面上 某一固定顶点( 一y ) 的值得到图g 的某些参数。如下面引理1 1 所示： 引理1 1 ( b o l l b f i s 3 ) 设g 是一个连通图，则7 1 ( g ；1 ，1 ) 代表了图g 的生成树的个数，7 ( g ；2 ，1 ) 是g 的森林的个数，丁( g ；1 ，2 ) 是图g 的连通生成子图的个数，7 ( 6 ；2 ，2 ) 是图g 的生 成子图的个数。 另外，t u t t e 多项式在很多其它领域都有着广泛的应用，如纽结理论、数理 统计等。 在研究图的t u t t e 唯一性之前我们先来了解一下图的色多项式。 设图g = ( v ，f ) ，如果可以用k 种颜色对g 的顶点进行颜色分配，每一个顶 点分配一种颜色，且任意两个相邻的顶点分配不同的颜色，则称g 是七一可着色 的。 图g 的色多项式用p ( g ，z ) 表示，它是图g 的x 一可着色的个数。 用m ，表示把v ( g ) 划分成厂种色类的不同划分数，则图g 的色多项式为： 1 p ( a ，x ) = ，m ，x ( x 一1 ) ( z 一2 ) ( z r + 1 ) 。 色多项式的系数和结构都已经被很多学者详细的研究过了，并且发现p ( a ，x ) 包含图g 的大量信息，例如，我们可以从p ( g ，x ) 中得到图g 的顶点数，边数， 围长g ( g ) 和最短圈的个数等。 若任何满足p ( g ，x ) - - - p ( i - l ，x ) 的图日都是与图g 同构的，n f , j ：图g 是色一 唯一的，简记x 唯一的。此时，图g 的参数是由色多项式唯一决定的。一些图类 已经被证明是x 一唯一的，如完全图k ：，圈c n ，二部图，q ( p ，g 2 ) 等。由 7 知，通过对比色多项式和t u t t e 多项式之间的关系，我们可以得剑上面这些图也 可以完全由t u t t e 多项式决定，即如果一个图是x 一唯一的，那么它一定是卜唯一 的；反之则不成立。如下面图1 1 中的两个图，睢和尺具有相同的色多项式，即 它们不是x 一唯一的，但睢却是严唯一的。由此。町见，丁( g ；x ，) ，) 是t 匕p ( a ，x ) 更强 的一个多项式。 i 。擘 夕 r 图1 1 所以在以后的研究中我们就可以只研究不是x 一唯。的或者没有被证明x 一唯 一的那些图就可以了。 实际上色多项式是t u t t e 多项式中的特殊形式。他们有如下关系： p ( g ，x ) = ( 一1 ) r ( g ) x 七( g ) 丁( g ；1 一x ，0 ) 。 在 7 中，d em i e r 和n o y 介绍了一类新的多项式秩生成多项式，定义 如下： f ( g ；训) = yx 川) y i a i j ；- 一 f 在f ( g ；z ，y ) 中x y j 的系数实际上是g 中秩为f 边数为的生成子图的个数。 显然，f ( g ；x ，) ，) 和丁( g ；x ，) ，) 都包含着图g 的相同信息，但是f ( g ；x ，y ) 这个 多项式要比丁( g ；x ，y ) 这个多项式简单的多，因此从f ( g ：x ，y ) 中提取信息也更为 简单，所以我们可以通过对f ( g jx ，y ) 的研究来达到研究丁( g ；五y ) 的目的。 但是在t u t t e 多项式中有一些性质是秩生成多项式所不具备的，如t u t t e 多 项式满足：若g 不包含桥和环，则存在边e f ( g ) ，使得 丁( g ；x ，y ) = r ( a p ；x ，y ) + r ( a e ；z ，y ) ， 2 其中，g 一8 和g e 分别代表将g 中的边e 去掉和收缩。而秩生成多项式则不 具备这样的性质。 t u t t e 多项式的定义也可以被推广到所有拟阵。设拟阵m ，若任何与m 有相 同t u t t e 多项式的拟阵都与m 同构，则称拟阵m 是产唯一的。b o n i n 和m i l l e r 在 8 中证明了一些拟阵是满足t u t t e 唯一的，如：一致拟阵、秩至少为4 的射影 和仿射几何，另外还有完全图的拟阵m ( k ) 等。设m ( g ) 表示图g 的二重拟阵， 则t u t t e 多项式满足如下等式： t ( m ( g ) ；x ，) ，) = t ( g ；y ，x ) 。 1 2 己知结论 目前一些著名的图类的卜唯一性已经被证明了。在 5 中，k u h l 证明了广 义p e t e r s e n 图p ( m ，2 ) 是t _ 唯一的，同样在这篇文章中还证明了广义p e t e r s e n 图 p ( m ，2 ) 的线图是t _ 唯一的；在 7 中，d em i e r 和n o y 证明了轮图、圈的平 方岛、完全多部图k p 。祝，、梯形图l ，t 、m 6 b i u s 梯形图帆还有超立方 体q n 是t _ 唯一的。在 1 中，完全多部图k 、完全二部图k ，q 和正则的完 全t 部图k ( p ，0o 2 ) 的线图的t 一唯一性也已经被证明；在 2 中，段英华和 于青林还证明了双半轮图眠( 1 c 1 ，k 2 ) 也是满足t _ 唯一性的。但是大部分线图的 t u t t e 唯一性还是没有得到证明的。 1 3 重要引理 t u t t e 多项式的系数包含了图的大量信息。如下四个引理总结了与本论文有 关的t u t t e 多项式的性质。 4 t ( g ；x l y ) = x 少 引理1 2 若图g 不包含桥和环，则 r ( g ) = m a x i ：b f o o ) ，礼( g ) = m a x j ：b 町o ) 引理1 3 ( b r y l a w s k i , t ，o x l e y j 1 2 ) 若r ( g ) 和n ( g ) 都是正的，则图g 的块的个数( 即2 连通分支的个数) 为 r a i n i ：b f o 0 ) 。否则，g 有i e ( g ) 1 个块。特别的，若g 是2 连通的，日与g 满 足t - 等价，则日也是2 连通的。 引理1 4 ( d em i e r 和n o y ， 7 ) 3 令6 = ( y ，e ) 是一个2 连通图，则图g 的如下系数是由它的t u t t e 多项式唯 一决定的。 1 顶点数和边数； 2 对任意k ，重数为k 的重边的条数；特别的，图g 是不是简单图； 3 最短圈g ( g ) 的个数； 4 边连通度a ( g ) ；特别的，最小度6 ( g ) 的下界； 5 若g 是简单图，不同大小的团的个数；特别的，团数c o ( a ) ； 6 若g 是简单图，长分别为3 ，4 ，5 的圈的个数，另外还有含有一条弦的 长为4 的圈的个数。 证明：1 因为g 是2 一连通图，故l y ( g ) i = r ( g ) + 1 。由引理1 2 知， r ( g ) = m a x ( i ：b f o o ) ，n ( g ) = m a x j ：b o ，o ) ，所以l v ( a ) i 等于1n _ k 顶点x 在7 1 ( g ；x ，y ) 中的次数。边数e ( g ) 等于n ( g ) + r ( g ) ，即在丁( g ：五) ，) 中x 和y 的次 数之和。因此，图g 的顶点数和边数是由它的t u t t e 多项式唯一决定的。 2 集合 e 1 ，e 2 ，e 七) e ( g ) 是图g 中k 条平行边的集合，图g 中这科，集合 的个数就是f ( g ；蜀y ) 中x ) ，七项的系数。相应的，f ( g ；x ，y ) 中每个x ) ，k 项都是来自 于这么一个集合。令： p = m a x j ：【x e ( a ；x ，y ) o ) ， 设p ，2 i p ，为有f 条平行边的子集的个数，并且这f 条平行边不包含于 任意i + 1 个平行边之中。令：j = p i ，我们用归纳法证明p f 是由f ( g ；x ，y ) 决定 的，凶此也是由丁( g ；x ，y ) 决定的。 对j = 0 ，此时满足i = p ，名= 【x y p 】f ( g ；x ，y ) 。假设昂，名- j 已知，下 面来计算巳叫一l 。系数 x y p - j 一1 】f ( 皖x ，) ，) 代表了g 中p 一歹一1 条平行边的集合 个数，而这p 一，一1 条平行边可能包含于更多的平行边的集合中，故 p p 。一1 2 x y i f ( g ；x ，) ，) 一冬p 。p f ( p j 一1 ) ， 故p f 是由f ( g ；x ，y ) 唯一决定的，因此也是由丁( g ；x ，) ，) 所唯一决定的。 当p = l 时，图g 是简单图。故图g 是否为简单图也是由丁( g ；x ，) ，) 所唯一 决定的。 3 设a 冬e ( g ) 是图g 的子图的边集，且这个子图是一个长为k 的圈，则 7 似) = k 一1 ，f a i = k ，图g 中这样的集合a 的个数就是f ( g ：x ，y ) 中x k - l y 丘项的 系数，显然 g ( g ) = r a i n k ：【x k - t y “】f ( g ；x ，y ) o ) ， 它是图g 的围长，故g 中的围长是由f ( g ；五) ，) 所唯一决定的，即由7 ( g ；x ，y ) 所 唯一决定的。 4 而卜口( 6 ) 一1 y a ( g 】f ( g ；置y ) 是它的最短圈的个数，显然它也是由f ( g ；五y ) 所 唯一决定的，因此也是由丁( g ；x ，y ) 所唯一决定的。 4 边连通度a ( g ) 是图g 的割边集所包含的最小边数。而g 中的割边集对应 于g 的二重拟阵m + ( g ) 中的圈。因此a ( g ) 同m + ( g ) 中的最小圈的长度是相等的。 上面3 中的证明同样适用于二重拟阵m + ( g ) ，因此我们可以由t ( m + ( g ) ；x ，) ，) 来计 算出五( g ) 。但是又因为 t ( m + ( g ) ；x ，) ，) = 7 ( g ；) ，x ) ， 所以a ( g ) 其实是由图g 的t u t t e 多项式所唯一决定的。 由a ( g ) 6 ( g ) 知，g 中每个顶点的度至少为a ( g ) 。故g 的最小度占( g ) 的下 界也是由图g 的t u t t e 多项式所唯一决定的。 5 若g 是简单图，子翱至e ( g ) 是一个阶为，z 的团( 即以兰k ) ，当且仅 当这种子集彳的个数等于f ( g ；x ，) ，) 中的x n - 1 y 【： j 项的系数。此时，阶为咒的团的 个数为b n - 1 y ( ：) 】f ( g ；五y ) ，故g 中不同大小的团数是由f ( g ；z ，y ) 摊- 决定的， 因此也是由t ( g ；x ，y ) 所唯一决定的。 而图g 的团数为 o x a ) = m 口x n ：【x n - 1 y ( n ) 】f ( g ；剐，) o ) ， 故图g 的团数是由f ( g ；x ，y ) 所唯一决定的，因此也是由7 1 ( g ；x ，y ) 所唯一决 定的。 6 因为长为3 的圈是一个团，所以由上面5 中的证明知，它的个数可以计算 出来，记为c 3 。长为4 的圈的个数与f ( g ；五y ) 中x 3 y 4 的项的系数有关，但是长为 3 的圈加上一条边也可以构成f ( g ；z y ) 中x 3 ) ，4 的项，故 c 4 = z 3 y 4 f ( 皖x ，) ，) 一c 3 d e ( a ) i 一3 ) ， 其中c 4 是指长为4 的圈的个数。记团心为有两条弦的长为4 的圈，由含有一条 弦的长为4 的圈所构成的且( g ) 的子集构成i x 3 y 5 】f ( g ；t y ) 中的系数。由5 知， 可以算出团心的个数丸。令c i 表示不含弦的长为4 的圈的个数，c 为含有一条 弦的长为4 的圈的个数，则有如下等式： c 4 = 3 k + c + c i ： 【x 3 y 5 】f ( g ；置力= 6 k 4 + 对。 通过这两个式子我们可以得出百和c 。 最后，考虑构成系数i x 4 y 5 】f ( g ；墨) ，) 的e ( g ) 的子集，有如下三种可能： 。长为5 的圈； 。长为4 的圈加上一条边，并且这条边不是此圈中的弦； 长为3 的圈加上两条边，含有一条弦的长为4 的圈除外。 5 后面这两类的个数分别是c 4 ( i e ( g ) i 一4 ) 一k 3 y s 】f ( g ；z y ) 矛n c 3 ( i f 2 i 一3 ) 一 2 x 3 y 5 i f ( c ；五y ) ，所以我们可以计算出g 中长为5 的圈的个数。 故g 中长为3 ，4 ，5 的圈的个数，还有含有一个圈的个数都是f h f ( g ；五y ) 所 唯一决定的，因此也是由7 1 ( g ；x ，y ) 所唯一决定的。 引理1 5 ( d em i e r 和n o y 1 ) 若g 是，z 一边连通的，那么它的线n l ( a ) 是甩一连通的，( 2 n 2 ) 一边连通的。 关于更多图的t u t t e 多项式，流多项式，色多项式及其它图论的知识见参考 文献 4 、 6 、 9 卜一 1 1 、 1 3 1 - - 2 4 ，关于拟阵的知识见参考文献 2 5 一 2 7 。 6 第二章梯形图的线图的t u t t e 唯一性 首先我们给出线图的定义：图g 的线图l ( g ) 是指将g 中的边看作l ( g ) 中的 顶点，若x ，y e ( g ) ，且工，y 相邻，当且仅当l ( g ) 中相应的顶点相邻。 在下面的文章中我们将长为f 的圈简称为i 圈，用c f 表示i 圈的个数。 首先我们来介绍一下梯形图，梯形图l n = g 心 图2 1 从图中我们可以看出，l n 是一个3 正则、3 一边连通的简单图，它有2 ，z 个顶 点，3 ，z 条边。 梯形图的线图l ( l n ) 如下图所示 l ( l 8 ) 图2 2 显然，l ( l n ) 有3 n 个顶点，6 九条边，2 ，z 个三角形，n 个4 圈，4 ，z 个5 圈， 不存在含有一个弦的4 圈。 定理1 当门6 ，礼4 i ，f = 2 ，3 时，若日是与( 匕) t _ 等价的平面图， 则h 一定i 司构于三也) 。 在证明定理1 之前我们先来证明下面几个引理。 7 j e 塞銮适态堂亟迨塞 笙三童搓毖图的垡图鲍i 垡坦堕= 毽 引理2 1 当，z 之6 ，7 l 4 i ，i = 2 , 3 时，若图h - 与l ( l n ) 是产等价的，则日是 4 正则，2 一连通，4 一边连通的简单图，并且日有3 ，z 个顶点，6 以条边，2 甩个三角 形，刀个4 圈，4 刀个5 圈，不存在含有一个弦的4 圈。 证明：因为l 竹是一个3 正则3 一边连通的简单图，由引理1 5 知，l ( l n ) 是3 一连通， 4 一边连通的简单图。 因为图日与l ( l 九) 是p 等价的，而l ( l 竹) 有3 n 个顶点，6 n 条边，2 n 个三角 形，z 个4 圈，4 咒个5 圈，不存在含有+ 。个弦的4 圈。由引理1 4 我们可以知道 h 也有3 胛个顶点，6 ，2 条边，2 刀个三角形，z 个4 圈，4 ，2 个5 圈，不存在含有一 个弦的4 圈。由引理1 5 知，是2 一连通，4 一边连通的简单罔。 因为h 中顶点的度至少为4 ，所以妒矿( h ) d ( 妒) 4 i v ( h ) = 1 2 n ，又因为h 中所有顶点的度数之和为p 矿( ) d ( v ) = 2 i e ( h ) i = 2 6 n = 1 2 n ，故h 中每个 顶点的度均为4 ，即是4 正则图。 n 引理2 2 当，2 6 ，n 4 i ，i = 2 , 3 时，若图h 与l ( l n ) 是严等价的，则日中 每个顶点都恰好包含于两个三角形中，并且这两个三角形的交只包含这一个顶点。 证明：令_ = i p i 妒恰好包含于f 个三角形中，1 7 y ( h ) ) l ， 因为日是4 正则的，所以0 i 3 ，所有可能的情况如下图所示： 躯 y 咒 vx v 图2 3 v 其中图2 3 中图中顶点x 不与影朋，2 相邻，中的顶点x ，y 不相邻，并且 x ，y 均不与肌，z 相邻，中的顶点x ，男m ，咒均不相邻。 但是中不存在含有一个弦的4 圈，故在顶点v 处不可能出现图2 3 中、 、的情况，即t 3 = 0 ，只能取，三种情况。 ，1，! 聊 以 又因为所有恰好包含于两个三角形中的项点在三角形中出现的次数为2 r 2 ， 而所有至多包含于一个三角形中的顶点在三角形中出现的次数为3 n t ，故 3 2 n 2 r 2 + 3 n f 2 ，即：t 2 3 n 。 但是i v ( h ) l = 3 n ，故t ，= 3 n 。故图2 3 中的和的情况不可能出现， 只有图成立。即日中每个顶点都恰好包含于两个三角形中。 既然中每个顶点都恰好包含于两个三角形中，故h 中每个顶点都是三角 形中的点，每条边郜是三角形中的边，则这两个三角形只包含这一个顶点。否则， 设有两个顶点同时包含于两个三角形中，则出现下图2 4 中( 口) 或者( 6 ) 的情 况，与h 中不存在含有一条弦的4 圈矛盾。 图2 4 口 引理2 3 当刀6 ，n 4 i ，= 2 , 3 时，若图h - 与l ( l n ) 是严等价的，则h 中 每个5 圈的诱导子图都恰好含有一条弦。 证明：设日中的任意一个4 圈，设为a b c d a ，对其中任意顶点，不妨设为顶点a 。 因为h 是4 正则图，故d 俐= 4 。因此存在y ( h ) 一( n ，b ，c ，( f ) 中的两个相异顶点 弛，使得a u , a v e ( h ) 。 又因为日中每个顶点恰好包含于两个三角形中，若u v f ( h ) ，且中不存 在含有一条弦的4 圈，此时点a 只包含于一个三角形中，与日中每个顶点都包 含于两个三角形矛盾。故u ，分别与巍d 相邻。由顶点a 的任意性知，h 中任 意一个4 罔中的每条边都同时包含在另一个三角形中( 如图2 5 所示) 。 图2 5 也就是说h 中每一个4 圈可以构成4 个有一条弦的5 圈，而在中，c 4 = n ，c 5 = 4 n ， 故日中所有5 圈都含有一条弦。 口 9 引理2 4 当”6 ，刀4 i ，f _ 2 ，3 时，若日与( t ) 是t - 等价的，则h 中每个三 角形恰好包含于两个5 圈中。 证明：令以为日中恰好包含于f 个5 圈中的三角形的个数。因为h 是4 正则的， 所以h 中每个三角形最多包含在3 个5 圈中，即0 i 3 。 因为所有恰好包含于3 个5 圈中的三角形在5 圈中出现的次数为3 国，脯 恰好包含于2 个5 圈中的三角形在5 圈中出现的次数为20 9 ，而所有至多包含于 1 个5 圈中的三角形在5 圈中出现的次数为2 ，z 一一蛾，故 2 甩一鹞一纰+ 2 c 0 2 + 3 国1 4 n ，即 0 9 2 + 2 0 ) 3 2 n ，( 1 ) 而 + q + 哆+ o j 3 = 2 n ， 故 缈o + c o l c 0 3 a 假设纰 0 ，即日中存在包含于3 个5 圈中的三角形。小妨设其中一个三角 形为彳，我们开始在彳的基础上构造日的子图。 根据日的如下性质： ( 1 ) 有3 ，1 个顶点，6 ，z 条边，2 以个三角形，n 个4 圈，4 ，2 个5 圈，不存在 含有一个弦的4 圈。它是4 正则，2 一连通，4 一边连通的简单图。 ( 2 ) 日中每个顶点都恰好包含于两个三角形中，并且这两个三角形的交只包 含这一个顶点。 ( 3 脚中每个5 圈都恰好含有一条弦。 我们可以唯一得到h 的子图日，h 图2 6 其中z ，y ，厶是日中的2 度顶点，h7 中的其它顶点度均为4 ，已饱和。 若x ，y ，z 中有两个顶点相邻，由对称性不妨设x ，y ，则出现h ”作为日的 子图，如下图所示： l o h ” 图2 7 在日”中三角形b ，c 为只包含于一个5 圈中的三角形，并且分别与b ，c 有一 个公共点相连的另外两个三角形也是至多包含于一个5 圈中的三角形( 公共顶点 分别为b ，c 中的2 度顶点) 。由图中我们还可以看出d 也是包含于3 个5 圈中的 三角形。 即此时日4 中出现两个包含于3 个5 圈中的三角形，则一定存在两个至多包 含于一个5 圈中的三角形。 若x ，y 。z 互不相邻，则出现日”作为日的子图，如下图所示： k h ” 图2 8 在日m 中，出现一个包含于3 个5 圈中的三角形则日”中一定存在6 个至多包 含于1 个5 圈中的三角形：，m ，e ，p ，q 。 因为日中包含于3 个5 圈中的三角形个数为纸，而每个日包含两个这样的 三角形，每个日”包含1 个这样的三角形。设日中与日”同构的子图的个数为口， 与h ”同构的子图的个数为，则有2 口+ = c o ，且三角形eee 必n 互不重 合，故与日和日”同构的子图中所包含的至多包含于一个5 圈中的三角形个数 至少为2 饼+ 3 。 若：0 ，则2 t z = c o ，。此时日中包含口个与h ”同构的子图，另外还可能存 在恰好包含于两个5 圈中的三角形或至多包含于一个5 圈中的三角形。 ( 1 ) 若日中除了与日一同构的图中所包含的至多包含于1 个5 圈中的三角形 外还包含其它至多包含于1 个5 圈中的三角形，则日中至多包含于1 个5 圈中 的三角形的个数大于2 a = 9 0 3 ，即缈o + c o l c 0 3 ，与前面所证明的+ q ( 0 3 矛 盾。 不： ( 2 ) 若h 中不包含其它至多包含于1 个5 圈中的三角形，但是哆 0 。 设口是恰好包含于两个5 圈中的三角形，则有h 作为h 的子图，如下图所 图2 9 南引理2 3 知，h 中任意的一个4 圈中的每条边都同时包含在另一个三角形中， 故我们可以得到h 的子图日：，如下图所示 图2 1 0 其中h ，中的三角形c ，以p ，厂都是包含二度顶点的三角形，又因为口是恰 好包含于两个5 圈中的三角形，故c ，f 中的两个二度顶点不相邻，则c ，厂是恰好 包含于1 个或2 个5 圈中的三角形。 若与日，同构的子图中像c ，厂这样的三角形中存在恰好包含于1 个5 圈中 的三角形，则在日中至多包含于1 个5 圈中的三角形的个数大于2 a t = 国，即 - i - q 缈3 。与前面所证明的4 - q 彩3 矛盾。 若与以同构的子图中像c ，厂这样的三角形都是恰好包含于两个5 圈中的 三角形，则由日的性质知，日中肯定存在h ，这样的子图( 如下图所示) 爿3 图2 1 1 此时三角形璺h ，t 是包含于一个或两个5 圈中的三角形。 若其中存在包含于一个5 圈中的三角形，则国o + l 2 a = 彩3 ，矛盾。 若与h ，同构的h 的子图中像f l , h 这样的三角形分别与像f ，的i 角形两 两重合，此时构成的图是日的一个连通分支，故日是不连通的，与己知日是2 一 连通的矛盾。 若存在晶j i z 与f ，不重合，且g ，j i l ，j 都是包含于两个5 圈中的三角形， 1 2 则日中出现h 4 这样的子图。 月4 图2 1 2 类似于中的讨论方式一直讨论下去。我们可以得出或者在日中有 + q 国3 的情况，或者胃是不连通的，又因为已知在h 中+ q 9 0 3 ，且日 是2 一连通的，故这两种情况都1 i 符合。故情况( 2 ) 不符合。 ( 3 ) 若日中不存在包含于两个或两个以下的5 圈中的三角形，则此时日是 由f 个日”构成的，此时n = 4 i ，与已知条件n 4 i 矛盾。 由( 1 ) 、( 2 ) 、( 3 ) 知y 0 ，并且h 中至多包含于一个5 圈中的三角形的 个数为缈o + q 2 0 r + 3 p 缈3 ，与+ q 缈3 矛盾。 因此中不存在包含于3 个5 圈中的三角形，即纸= 0 。故( 1 ) 式变为纸2 n ， 而h 中三角形个数为2 ，z ，故缈2 = 2 n ，缈o + q = 0 ，即日中每个三角形都恰好包 含于两个5 圈中。 口 下面我们开始证明定理2 1 ： 证明：由引理2 3 知，h 中任意一个4 圈中的每条边都同时包含于另一个三角形 中而日中有n 个4 圈故日中存在n 个日的子图如图2 1 3 所示，图中， ，均代表三角形。令乜，& 分别表示三角形和中所包含的边集。 假设m e ，n e 4 ，因为日中每个三角形都包含于两个5 圈，故三角形 还应与另外一个4 圈有一条公共边，由对称性，不妨设这条公共边为m ，又因为 日是4 正则的，故刀也是这个4 圈中的边，又凶为日中不存在含有一条弦的4 圈，故中的二度点不可能与，中的二度点相连，只能与v