（计算机软件与理论专业论文）给定面对的最小正则平面图.pdf

人迕理r 火学硕十学位沦文 摘要 图论是应用数学理论的重要分支。图论的广泛应用，促进了它自身的发展。尤其是 近几十年来，随着计算机技术的出现和进步，图论理论有了飞速的发展并取得了惊人的 成绩。 本文所研究的具有给定围长的最小征则图称为笼，找笼问题是图论中的一个经典问 题。关于找笼问题已经有了一些精确的结果。 h a r a r y 和k o v a c s 引进了给定围长对的笼的概念，即把具有给定奇数围长与偶数围 长的最小正则图也称为笼。对于偶数围长为4 及其它一些特殊情况，已经给出了精确结 果。本文把问题局限于平面图来考虑，并且仅考虑奇偶面对而不是奇偶圈。 令g 为一个平面图，v ，c o 和s 为大于2 的整数。如果和8 分别为图g 的最小奇 数面和偶数面，则称( ，) 为g 的而对，并称g 为一个( 芦) 一图。如果g 是一个v 一正 则图，也就是g 中的每个顶点的度均为v ，则称它为一个( v ，一图。具有最少顶点数 的( v ，棚，一图中的顶点数记作贝v ，c o ，0 。由欧拉公式，( v ，) 只能有( 3 ，3 ，s ) ，( 3 ，5 ，0 ， ( 3 ，c o ，4 ) ，( 4 ，3 ，0 和( 5 ，3 ，0 五种可能的情形。 c m m i e m c a m p b e l l 给出了关 二( 3 ，3 ，0 与( 3 ，4 ) 的结果，本文更正了其中关于( 3 ，3 ， 0 的结果，并完成t x c 其余三种情形，也就是( 3 ，5 ，s ) ，( 4 ，3 ，0 和( 5 ，3 ，8 ) 的研究。 本文设计了生成具有较小顶点数的( v ，0 图的算法，从而给出了( v ，0 9 ，0 的上 界，再利用欧拉公式，证明t x v , c o ，0 的下界，并最终给出了苁v ，c o ，8 ) 的精确结果，从 而完成了对给定面对的最小正则平面图问题的研究，从而为给定面对的最小正则平面图 问题的研究画上了一个完美的句号。 关键词：正则图；平面图；面对：围长 给定面对的最小正则平丽蚓 t h ef a c ep a i ro fp l a n a rg r a p h a b s t r a c t g r a p ht h e o r yi so n eo ft h em o s ti m p o r t a n tb r a n c h e so fa p p l i e dm a t h e m a t i c s i t sw i d e a p p l i c a t i o na c c e l e r a t e si t sd e v e l o p m e n t ，e s p e c i a l l yi nt h er e c e n ty e a r s ，w i t ht h eo c c u r r e n c ea n d d e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , g r a p ht h e o r yh a sm a d eg r e a tp r o g r e s sa n do b t a i n e d w o n d e r f u la c h i e v e m e n t ac l a s s i cq u e s t i o ni ng r a p ht h e o r yh a sb e e nt h es e a r c hf o rc a g e s ，t h a ti s ，m i n i m a lv - r e g u l a r g r a p h sw i t hag i v e ng i r t h c o n s i d e r a b l ee f f o r th a sy i e l d e do n l yah a n d f u lo fp r e c i s er e s u l t s h a r a r ya n dk o v a c sh a v ei n l r o d u c e dt h en o t i o no f c a g a sf o rg i r t hp a i r , w h e r eo n es e e k sm i n i m a l v - r e g u l a rg r a p h sw i t hg i v e no d da n de v e ng i r t h s as e q u e n c eo fa r t i c l e sh a sr e s u l t e di ns o m e e x a c tr e s u l t sw h e nt h ee v e ng i r t hi sf o u r , a n daf e wo t h e ri s o l a t e dr e s u l t s 鼢fw ep m p o s ei n t h ep r e s e n tw o r ki st ol o o ko n l ya tp l a n a rg r a p h sa n dc o n s i d e ro n l yo d d a n de v e nf a c e sr a t h e r t h a no d da n de v e nc y c l e s l e tgb eap l a n eg r a p ha n dl e tv ，0 9a n dsb ei n t e g e r sb i g g e rt h a n2 w es a yt h a t ( ，0i st h e f a c e p a i ro f g i f m a n ds a r e t h e l e n g t h s r e s p e c t i v e l yo f s h o r t e s t o d d a n de v e n f a c e s o f gi n t h i s c a s ew es a ygi sa n ( c o ，曲一g r a p h 1 f gi sp - i e g u l a rg r a p h , t h a ti si f e v e r yv e r t e xo f gh a sd e g r e ev ， w es a yt h a tgi sa n ( v ，c o ，0 - g r a p h n l en u m b e ro f v e r t i c e si na s m a l l e s t ( v ，c o ，0 一g r a p hw i l lb e d e n o t e db y 以v ，0 b yt h ee u l e rf o r m u l a , t h e r eo n l yp o s s i b l ee a s e sa r e ( 3 ，3 ，0 ，( 3 ，5 ，0 ，( 3 ，c o ， 4 ) ，( 4 ，3 ，0 a n d ( 5 ，3 ，0 c o n n i em c a m p b e l lg a v et h er e s d t sf o r ( 3 ，3 ，0a n d ( 3 ，c o ，4 ) w ec o r r e c t e dt h eo n ef o r ( 3 ， 3 ，0a n dg a v et h em s u l t sf o rt h er e s tt h r e ec a s e s ，i e ( 3 ，5 ，0 ，( 4 ，3 ，0a n d ( 5 ，3 ，0 i nt h i st h e s i s ，a na l g o r i t h mf o rc o n s t r u c t i n gs m a l l ( v ，珊，o - g r a p h si sg i v e n ，a n di ti su s e dt o i m p r o v et h eu p p e rb o u n d so f x v ，c o ，) 毗e u l e rf o r m u l ai su s e dt op r o v et h el o w e rb o u n d so f 贝v ，0 a sar e s u l t , t h ep r e c i s ev a l u e so f 必v , ，0 a r eo b t a i n e d , a n dt h i sf m i s h e dt h er e s e a r c h o nt h ep r o b l e mo f t h es m a l l e s tr e g u l a rp l a n a rg r a p hw i t l lg i v e nf a c ep a i r s k e yw o r d s ：r e g u l a rg r a p h ；p l a n a rg r a p h ；f a c ep a i r ；g i r t h 大连理1 ：大学硕士学位论文 0 前言 图论是研究某些事物及它们之间关系的学科。现实世界中的许多事物( 或对象) 能用 图表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论对这些问 题作出分析和判断。图沧发展至今，已经积累了许多难题，至今仍找不到有效的算法去 解决，如求图中的h a m i l t o n 回路，r a m s e y 问题，笼问题等等。这些问题均属于n p - 完 全问题。 找笼问题就是在给定围kg 的条件下，寻找含有最少顶点数的旷f 则图，记作( v ， 曲一笼。对于( v 曲一笼，随着v 与g 值的增大，求得笼的顶点数目及找到所有的( 1 ) ，曲一笼是 非常困难的。有些笼问题的解决不得不借助于计算机强大的计算功能，利用穷举搜索的 办法来解决，如( 5 ，5 ) 一笼问题。但是，即使是利用计算机亦必须采用有效的算法以解决 速度及存储空间问题，而且在目前的计算机技术条件下，大量笼问题的解决还是力不从 心的。 于是人们开始研究源于传统笼问题的新问题。一类是仅考虑给定度集合和围长的图 这个问题足从c h a r t r a n d ，g o u l d 和k a p p o r 开始研究的。一个( d ；曲一笼就是度集合为d ， 围长为g 的含有最小顶点数的图，( d ；朗一笼的顶点数记为f d ；曲。令一类是仅考虑给定 奇偶数数围长对的r 正则图，这个问题是从h a r a r y 和k o v a c s 开始研究的。一个o ，c o , s ) 一笼，就是围长对为 ，0 的含有最少顶点数的旷正则图，( v ，0 9 ，0 一笼的顶点数记为觚 ，8 ) 。 多年来，我们课题组对找笼问题及其演化问题都进行了比较深入的研究，1 9 8 9 年 杨元生教授和张成学教授借助计算机找到了第4 个( 5 ，5 ) 一笼，并证明y ( 5 ，5 ) 笼仅有4 个。杨教授和张教授的这一结论，是对找笼问题的突破性成果。另外，他们还研究出了 围长为6 度集合为_ d 的图的最少顶点数。 令a 与盼别为正则平面图的最小奇数面与偶数面。在1 9 9 5 年，c o n n i em c a m p b e l l 提出了给定面对的最小正则平面图问题 1 ，并证明了 1 ) f 1 3 ，3 ，曲( 6 e + 2 ) 5 ，且对于正整数丘 以3 ，3 ，l o ) 21 2 k + 2 苁3 ，3 ，1 0 k + 2 ) = 1 2 k + 6 f 3 ，3 ，1 0 k 十4 ) = 1 2 k 十6 ( 3 ，3 ，1 0 + 6 ) 21 2 k + 1 0 苁3 ，3 ，1 0 k + 8 ) 2 1 2 k + 1 0 2 ) 对于r d 3 ，苁3 ，c o ，4 ) = 2 c o ， 3 ) 2 e - - y ( 5 ，3 ，0 4 ， 给定面对的撮小正则平面图 4 ) 2 十1 0 厦3 ，5 ，s ) s4 e ， 5 ) e + 3 f 1 4 ，3 ，0 2 e 本文在前人工作的基础上，对于给定面对 ，0 的最小正则平面图的问题给出了全 面深入的研究。本文设计了一种能生成具有较小顶点数的化固一图的算法来改进以v ，o k ， 0 的上界，利用数学证明得到下界，最终给出火3 ，3 ，0 ，t ( 3 ，5 ，8 ) ，苁4 ，3 ，0 ，必5 ，3 ，0 的精 确结果，从而为给定面对的最小正则平面图问题的研究画上了一个完美的句号。 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除r 文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：盈日期：! 噬：厦 大连理：人学硕十学位论文 1 基本概念 本章介绍与本文相关的图论的一些基本概念和术语。 定义1 1 图 一个无向图g 定义为一个二元组( 以目，记作g 气k 目，其中睁坎g ) 是个非空集 合，称作无向图g 的顶点集：e = e ( q 是由k g ) 中元素构成的无序对集合，即 联g 户 ( “，v ) 协，v 叹g ) ) ，称为无向图g 的边集，简记边( “，v ) 为“v 。 无向图与有向陶统称为图。本文中的图是指无向图。 边“v 的端点“，v 称为相邻的。称一条边的端点为与这条边相关联，同时，也称一条 边为与它的端点相关联。若两条不同的边与一个公共的点关联，则称它们是邻接的边。 关联同一端点的一条边称为自环。两条或两条以上的边关联一对端点，称为多重 边。本文所涉及的图均为无自回路，无重边，有限的无向图。 p = p ( g ) = i 坎g ) l 表示图g 巾的顶点数，称为图( ；的阶( o r d e r ) 。 q = g ( 回= i e ( g ) l 表示图g 中的边数，称为图g 的大d , ( s i z e ) 。 定义1 2 正则图与完全二分图 在图g 中，如果顶点u , p 是相邻的，通常称v 是 的一个邻接点，顶点“的邻接点 集合是图g 中所有与“相邻的顶点的集合，记作( “) ，( “) = v ju v e 耳 ) 。 m “】= 吖) u ( ，称作顶点“的闭邻接点集。 设v 以g ) ，称硪v ) = l ( g ) i 为v 的度。 若图g 的各顶点的度相同，则称图g 为正则图，着任取v h g ) ，翻，v ) ，则称图g 为七一正则图，称它的 e n 度为k ，此时：n ( u ) = v l 洲以g ) 完全- - j ) - 图k 是满足以下条件所构成的图类： ( 1 ) 顶点分为二个集合，娩，其中1n l = m ，；圪l = n ： ( 2 ) 对于任意搓k ，v 巧，若i c j 则mv 相邻( f ，j = 1 ，2 ) 。 定义1 3 嵌入与平面图 如果一个图g 可以画在一个表面s 上，且任何两条边都不相交，则称g 可以嵌在 表面| 5 r 上。褶应的画法称为一种嵌入。 一个无向图g = ( 圪d ，如果它可以嵌入到平面，称它是呵平面的。已经嵌入平面的图 称为平面图。由平面图限定的各个区域称为g 的面，包围这个区域的各条边构成的 圈，称为该面的边界，边界的长度，称为该面的度，记为a ，称这个面为面。 无限的区域，称为外平面。可见，平面图g 恰有一个外部面。 给定面对的最小正m u 平面图 通常将平面图g 表示为g = ( k 最d ，其中f 一只表示图g 中所有面的集合。用厂= g o - d = f f f g ) i 表示平面图g 中面的个数。 定义1 4 子图 若h 仞量取6 9 ，占c 功以回，则称图h 为图g 的子图。若坎= 坎g ) ，段仞 耳q ，则称图为图g 的生成子 蛩( s p m m i n gs u b g r a p h ) ；若坎国坎g ) ，“v 耳功当 且仅当z n ) e ( g ) ，且“，v h 回，则称图h 为图g 的导出子图( i i 血l c e ds u b g r a p h ) ，记 作：( g ，上d 。 定义1 5 割点，块，端点块及中间块 如果g 不是连通图，则称为非连通图或分离图。图g 连通分支的个数称为w 国。 由此说明只有一个连通分支的图刁是连通图。 从图g = ( k 固中删除顶点集s 是指图g 的v 。s 导出子图，即从v 中删除所有s 中 所有顶点和所有与s 中顶点相关联的边丽得到的予图，记作g s 。特别当s = v 1 ，则 称v 是g 的割点。 设g 是连通图，称数k ( 6 3 = r a i n i s ；s 是g 的分离顶点集) 为g 的点连通度，此时 称图g 是n q 连通的。 一个图的块是指该图的一个予图，这个子图本身是块( 没有割点的连通图称为 块) ，而且是有此性质的块中的极大者。 如果g 为包括割点的图，g 中仅含一个割点的块称为端点块，g 中包含至少两个割 点的块称为中间块。如果g 含有端点块，则至少含有两个端点块。 定义1 6 割对，广义块，广义端点块及广义中间块 如果g 为二连通图，存在邻接的两点，同时删除这两点将导致g 为不连通图，则 称这对邻接点称为割对。一个矿不可分图是指二连通且不含割对的图。 一个广义块是指最大的r 不可分图。 如果g 为包括割对的二连通图，g 中仅含一组割对的块称为广义端点块，g 中包含 至少两组割对的块称为广义中间块。如果g 含有广义端点块，则至少含有两个广义端 点块。 定义1 7 笼及m o o r e 图的定义 若v _ 正则图g 的围长为g ，则称其为( v ，曲图。人们称顶点数最少的( v ，曲一图为( v ， 曲一笼。即若一个图g 为( v ，g ) 一图，则满足以下全部的3 个条件： 此图为v 一正则图； 此图的围长为g ； 在满足以上两个条件的图中，此图的顶点数最少。 大连理t 大学硕t 学位论文 如图l _ 1 所示： 一个( bg ) m o o r e 图是一个顶点的度v 2 ，且围长为g 包含尽量少的结点数的图。 。小，羔( v 1 ) ”1 ：掣粤 定义1 8 内部路径，最短内部路径长度 令g 为一个( 5 ，3 ，) - 图，则g 含有一个争面，称作r 一1 , t o “1 r d t 1 。令= g ，h r ) ) 。假设嘶，崎h e ( i 5 时，寻找似曲一笼或确定必u 曲值时非常困难的，目前仅确切知道 有限的如，曲值，并且还未找到求如，曲的理想上界公式。 定理2 1 ( 关于下界公式) 5 ： 卜，g ) = 1 ( 2 ( v ( ( v 。一- 1 1 ) ) r ，- 一2 2 ) ) ( 。- 一2 2 ) ) , ，( ( g g = ：2 2 r ，) + 1 ) 苁v ，曲似v ，曲。 若，- 曲= f d v ，曲，n - 个( v ，朗- 笼又被称为最小( v ，曲- 图或m o o r e 图。m o o r e 图这一 术语是由h o f f m a n 及s i n g l e t o n z a i 两人提出的。 定理2 2 ( 关于上界公式) 5 ： 大连理t 大学硕士学位论文 如果g 为奇数，那么，( 3 ，g ) 玉f 票1 一+ 芸且厂( 。，g ) 2 ( v 一1 ) 一，( v 4 ) 。 如果g 为偶觏那么f ( 3 , g ) 褂+ j 2 且，( v 。g ) 4 ( v - 1 ) g - 3 v 4 ) 。 这是迄今为止最好的上界公式，但与已知的，( v ，g ) 值相比，利用上式得出的上界 显然太大了，因此改进上界公式是一项有趣的工作。 定理2 3 仅当( i ) g = 5 且v = 3 , 7 或( 可能) 5 7 ，或( i i ) g = 6 , 8 ，1 2 时存在最( v ， 曲一陶。 2 1 3 ( v ，5 ) 一笼 如定理2 3 所描述的，只有当v = 3 , 7 或( 可能) 5 7 时，最小的( v ，5 ) - 图存在。当v = 3 时，独一无二的最小( 3 ，5 ) 一图是p e t e r s e n 图，而且，3 ，5 ) = 1 0 。( 如图2 1 ) 当v = 4 时，唯一的( 4 ，5 ) 笼是r o b e m s o n 图( 如图2 - 1 ) ，而且a 4 ，5 ) _ 1 9 ，见文献 6 。 当v = 7 时，唯一的( 7 ，5 ) 一图是h o f f m m l s i n g l e t o n 图，而且贝7 ，5 3 = 5 0 。这个图的构造 如下描述：首先有1 0 个5 一环：尸0 ，l , p 2 , p 3 ，p 4 ，q o ，p 1 ，q 2 ，q 3 ，q 4 ，如图2 - 2 ；b 中的顶点i 分 别同甄中的顶点+ j k ( m o d 5 ) 连接。例如p 2 中的顶点2 连边方式如图2 2 。h o f f r a a n 和 s i n g l e t o n 4 得到这个图并证明了它的唯一性。图2 2 的构造分析过程由 r o b e r t s o n 7 ， 8 给出。关于更多的这个图的特性请参考文献 9 ， 1 0 。 当v = 5 时，存在四个3 0 ( w e g n e r i j h e 明a 5 ，5 ) = 3 0 ) 个顶点的( 5 ，5 ) 一笼。第一 个( 5 ，5 ) 一笼为r o b b e r t s o n - w e g n e r 图，有1 2 0 个自同构群。b r o u w e r 给r o b b e r t s o n - w e g n e 图 一个新的描述：图有两个轨道 1 0 ，2 0 1 ，如图2 - 3 中所示；第二个( 5 ，5 ) 一笼是由w o n g 构 造的，由3 个五边形和3 个五角星形，是h o f f m a n s i n g l e t o n 图( 5 个五边形和5 个五角 星形) 的导出于图，有 5 ，5 ，l o ，1 0 ) 同构组的2 0 个自同构群，如图2 3 所示；第三个 ( 5 ，5 ) 一笼由f o s t e r 构造的，是有 1 5 ，1 5 同构组的3 0 个自同构群，如图2 3 所示；1 9 8 9 年杨元生教授和张成学教授借助计算机找到了第4 个( 5 ，5 ) 笼，是有 6 ，2 4 ) 同构组的9 6 1 个自同构群，并完成了c ( 5 ，5 ) = 4 的证明。杨教授和张教授的这一结论，是对笼问题研 究的突破性成果，如图2 - 3 所示。 当v = 6 时，0 k e e f e 和w o n g 1 2 订e n 存在唯一的( 6 ，5 ) 一笼，且，( 6 ，5 ) = 4 0 ，这个图 通过从h o f f m a n s i n g l e t o n 图删除五角星形得到，有4 8 0 个自同构群。 给定面对的最小正则平面图 当v = 8 时，现在仅有g o r d o n 得出最小的含有8 0 个结点( 8 ，5 ) 一图，有1 6 0 个自同构 群。 当v = 9 时，现在仅知道的最小的( 9 ，5 ) 一图是归属于b r o w n ，m u r t y 和o k e e f e 的古 老构造方法。 r o b e f t s o ng r a l o h 图2 - 1 ( 3 ，5 ) 笼和( 4 ，5 ) 笼 f i g u r e2 - 1 ( 3 ，5 ) - c a g ea n d ( 4 ，5 ) - c a g e 2 1 4 ( v ，6 ) 一笼 唯一的最小( 3 ，6 ) 一图是h e a w o o d 图，且7 ( 3 ，6 ) = 1 4 ，如图2 - 4 所示。 当k = v 1 是一个素数时，最小的( v ，6 ) 一图是k 阶映射j r 面的点缘一致图，且_ 7 ( u 6 ) = 2 ( 萨+ k + 1 ) 。这个图是k a r t e s z i 1 3 和s i n g l e t o n 1 4 发现的。w o n g 给出了这个图的不 同的构造。图2 5 所示：给出这个图2 ( 惫2 + 女+ 1 ) 顶点的布局。顶点( 1 ) ，( 2 ) ， 图22 ( 7 ，5 卜笼的构造过程 f i g u r e2 - 2t h ec o n s t r u c t i o no f ( 7 ，5 ) 一c a g e 大连理t 火学硕士学位论文 ( 1 1 ) ，( 1 磅，( 女助，同样的定义几i i j 于k ( - v - 1 ) 是一个素数，存在一个由l ，2 ，_ j 组成 的完全序y ! j l 2 ，l 3 。, l k ) ，参考文献 1 5 。 令 l l = 饿臆 r o b e n 5 0 n _ w 。印e r c a g ew o n gc a g e 勰 窳 12k l2 七 图2 - 3 四个( s ，5 ) 一笼 f i g u r e2 - 3f o u r ( 5 ，5 ) - c a g e s 和l ，= 耳，耳： e ，： l nl ( 1 ，l a y 啦争z h 锄gc a g e 这里一，= 1 ，e ：= 2 ，_ 。= k 。和y 中的顶点根据下而的规则连接：( p q 卜1 q ， 2 ，吆( p ，q = 1 , 2 ，k ) 。 由于厶，厶，厶均为矩阵，遵循e 目长为6 和度为、睁= 尼+ 1 ) ，所以是最小的( v ，6 ) 一 图。 通过类似的方法构造，o k e e f e 和w o n g 在文献 1 6 得到唯一的( 7 ，6 ) 一笼，并且证 明了苁7 ，6 ) = 9 0 。阈题：是否存在1 0 阶的映射平面? 举例说明一下，最小的( 4 ，6 ) 图的连接方式： 给定丽对的最小止则平面图 1 1 ( 3 1 ) 2 3 3 2 1 2 ( 1 2 ) 2 2 3 2 1 2 ( 2 2 ) 2 3 3 l 1 2 ( 3 2 ) 一2 1 3 3 1 3 0 2 ) 2 3 3 3 1 3 ( 3 3 ) 2 2 3 1 h e a v v o o dg r a p h 图2 - 4 唯一的( 3 ，6 ) 一笼 f i g u r e2 - 4t h eu n i q u e ( 3 ，6 ) 一c a g e b i g g s 和i t o 在文献 1 7 已经给出了下面砥个结论： 定理2 4 如果g 是一个度为v ，围长为2 r 6 ，剩余结点为。的正则图，且e y - 2 ，则g 足个直径为r + 1 的二分图。 定理2 5 当v = 5 或7 ( m o d 8 ) 时，古有2 个剩余点的6 ) 一图不存在。 从定理2 5 可得出郧，6 ) 8 8 。 2 1 5 ( v ，7 ) 一笼 根据定理2 3 得知，不存在最小的( v ，7 ) 一笼。所以，关于围长为7 的笼目前仅发现 当v = 3 时，即唯一的( 3 ，7 ) 一笼。m c g e e 1 8 中给出y ( 3 ，7 ) 一笼，它的唯一性由t u t t e 在文 献c 1 9 ；中证明。下面给出( 3 ，7 ) - 笼的构造过程，从定理2 1 和2 3 得知这个笼至少有2 4 个结点。这些结点的排列如图2 - 6 所示，如果a 和b 不相邻，则这个图中长度为7 的 圈个数为( 6 x 2 4 x 3 2 ) 7 ，显然_ i 可能，所以a 和b 是相邻的。呵以假定爿唧，e 和b c ， ； l 2 3 、j l o b 孔弛 ”q 丝弱 、，q 大连理j 一人学硕士学位论文 则有e - i ；i - d , 抛；c t 占锄；如f ；a - l ；6 也t ， 和卜g 。从这个构造可以得到- ，( 3 ，7 ) = 2 4 及 其唯一性。图2 7 给出t o ，7 ) 一笼的另一种构造方法。 k 。l 譬 、， 、髟7 7 。”一。x 图2 - 52 一啪+ 1 ) 顶点的排列方式 f i g u r e2 - 5t h el a y o u to f 2 ( 2 十斛1 ) v e r t i c e s 图2 - 6 ( 3 ，7 ) 一笼顶点的排列方式 f i g u r e2 - 6t h ea r r a n g e m e n to f v e r t i c e so f ( 3 ，7 ) 一c a g e 、 j 惫 一 、羚一 一 、 r 。蓣一 一， 、 ， 一 ，j。、 一珠 一 一 ，m 耄 、 辩 ， m 夕 ，?啪 ：= = j 挚 j、 _、 、 啮， 一 ， 、 ， 救 、心 。 给定面对的最小正则平面图 跃兔 滞- ， 图2 7 ( 3 ，7 ) 一笼 f i g u r e2 - 7 ( 3 ，7 ) 一c a g e 2 1 6 ( v ，8 ) 一笼 t u t t e 2 ， 1 9 给出了唯一的最小( 3 ，8 ) 一图且苁3 ，8 ) = 3 0 。我们给出这个图的简单构 造，这些结点的排列如隆i2 8 所示，可以假定加f ，肌和6 岛0 ，则有f e ；卅 g ；产c ， ；f 以 p 一面c 卅； 。；p p ；t 厂和 曙。从这个构造可以得n ( 3 ，8 ) 一笼及其唯一性。图2 - 9 给出了 f 3 ，8 ) 一笼的另一种构造方法。更多关于( 3 ，8 ) 一笼的性质可查阅义献 2 0 ， 2 n 2 2 。 当v _ 1 是一个素数时，已知的最小( v ，8 ) 一图均是s i n g l e t o n 1 4 和b e n s o n 2 3 从映射 几何学得到的。假设q 4 是一个在映射4 空间p ( 4 ，v 一1 ) 上的非简单二次i 曲面。假设g 是 一个所有顶点为q 4 的点和边图，两个顶点直接有连边当且仅当他们在q 4 中关联与一个 点线一致对。所以g 是一个最小的( v ，8 ) 一图。 图2 - 8 ( 3 ，8 ) 一笼顶点的排列方式 f jg u r e2 - 8t h ea r r a n g e m e n to f v e r t i c e so f ( 3 ，8 ) 一c a g e 大i 童理工人学硕士学位沦文 图29 ( 3 ，8 ) 一笼 f i g u r e2 - 9 ( 3 ，8 ) 一c a g e 尚未发现其他的( v ，8 ) 笼。只有b i g g s 和i t o 1 7 证明了下面的结论。 定理2 6 不存在围k2 r 8 ，且剩余顶点数为2 的正则图g 。 定理2 6 并没有达到预期的纡i 论。例如，它认为仟意一个剩余顶点数为2 的( v ，8 ) 一 图不存在。但是，我们知道当v 一1 是素数时，存存最小的( v ，8 ) 罔。 2 ，1 7 ( v ，1o ) 一笼 o k e e f e 和w o n g 2 4 证明了苁3 ，1 0 ) = 7 0 。那时已经知道有3 个( 3 ，1 0 ) 一笼，分别由 b a l a b a n ，h a r r i e s 和w o n g 给出。w o n g 2 5 还证明了仅存在3 个( 3 ，l o ) 一笼。 2 1 8m 1 2 ) 一笼 当v 一1 是一个素数时，已知的最小( v ，1 2 ) 一图山b e n s o n 2 6 构造。关于最小( 3 ，1 2 ) 一图 请参考文献 2 7 ， 1 0 ( p 1 6 4 ) 。假设q 6 是存映射6 一空涮p ( 6 ，v 一1 ) 的二次曲面，给出 x j + x i x 一】十x 2 x 一2 + x 3 x 一3 = 0 对于线中的每个顶点，防+ 别于x 一致的q 6t i7 的线和点y 满足下列关系： x o y ，一x i y o + x _ j y r x _ k y ，0 ， 这里( f ，工足( 1 ，2 ，3 ) 或( 一1 ，一2 ，一3 ) 循环的奇罱换，并且x = ( ) 和y = o ( - 3 i 3 ) 。如果 ( 勺所有顶点是q 6 中的点利4 i 同于上面的纷中的线，则g 是一个最小的( v ，1 2 ) 一图。 b i g g s 和i t o 的二分理论( 定理2 4 ) 应用于所有已知的具有偶数围长的笼，除了3 个( 3 ，1 0 ) 一笼，因为这3 个笼的剩余结点是8 。但是，很容易验证3 个( 3 ，1 0 ) 一笼是二分 图。所有已知的具有偶数围长的笼邵有这个性质。 给定而对的最小正则平面劁 2 1 9 两个( v ，g ) 一图 在本章前面的部分我们介绍了已经被发现的笼，本节介绍两个特殊的( v 曲一图。 找( 3 ，9 ) 一笼问题是一个古老又困难的问题。在1 9 5 2 年，r m f o s t e r 构造了第个6 0 个顶点的( 3 ，9 ) 一图。从那之后，有至少3 0 个具有6 0 个顶点不同构的( 3 ，9 ) 一图被发现。根 据上界公式，己知x 3 ，9 ) k 5 4 ，在计算机的帮助下，b i g g s 和i t o a r e 2 8 发现了5 8 个顶点 的( 3 ，9 ) 一图，所以5 4 - x 3 ，9 ) 5 8 。表2 - 1 中火3 ，9 ) = 5 8 是b r e d a nm c k a y 得出的，m c k a y 通过计算证明了f ( 3 ，9 ) = 5 8 ，并与b f i n k m a m a ，s a a g e r 一起利用计算机通过穷举搜索找到 了全部的1 8 个( 3 ，9 ) 笼。这一成果是近年来笼问题研究的展大进展。 b a l a b a n 2 7 给出了一个11 2 个顶点的( 3 ，11 ) 图。这个图通过从最，、的( 3 ，】2 ) 一图删除 1 4 个顶点得到。目前b r e n d a nm c k a y 与w e n d ym y r v o l d 已证明t f l 3 ，l1 ) = 1 1 2 ，即已知 的( 3 ，11 ) 图是一个( 3 ，11 ) 一笼，但人们目前仪找到这一个( 3 ，11 ) 一笼。 对于v23 ，g 1 3 的情形，目前均未得到确定的贝v 曲值，人们只是求出了一些苁v ， g ) 值的上下界，并找到了一些这样的化朗一图。 为了清晰起见，我们将所有已知的笼在表2 一l 中罗列出。从表2 - - 1 的结果可看出， 对某些笼人们已经确定了它们的以h 曲值的范围。如：围长为3 的笼均为完全图，围长 为4 的笼均为二部图。除此两类图外，同前人家仅知道很少的笼。人们对已知的笼进行 研究还发现，绝大部分笼中有相似顶点。 设c ( ug ) 为( v ，g ) 一笼的个数，目6 u 划v = 3 ，g 3 ，已经确定( v ，g ) 值的笼的状况，如 表2 2 所示。从表2 2 不难看出，人们对笼的了解还很不足，目前仅确切知道有限的 苁b 曲与c ( v ，曲值。任何对现有的结论的改进，都意味着笼问题研究的一大进步。至今 已经知道的笼及其类型参见表2 2 。 表2 - 1 已确定且v 期值的笼状况 !量：z j 垃! 墨jf 生：星j 334d 346 6 351 01 0 361 41 4 372 22 4 383 0 3 0 394 6 5 8 31 06 27 0 人连理_ ：【= 大学硕十学位论文 表2 - 2 目前已知的笼名称及其数h ! 星)! ! ! ! ! ! ! ! 婴! ! ! ! ! ! ! ! ! ( 3 ，3 ) 1 c o m p l e t eg r a p h 确 ( 3 ，4 ) 1 c o m p l e t eb i p a r t i t eg r a p hk3 ，3 ( 3 ，5 ) l p e t e r s e ng r a p h ( 3 ，6 ) 1 h e a w o o d ；r a p h ( 3 ，7 ) 1 m c g e eg r a p h ( 3 ，8 ) 1 l c v ig r a p h ( 3 ，9 ) 1 1 3 b i g g sa n dh o a r c ( 1 9 8 0 ) ，b f i n k m a n ne ta l 。( 1 9 9 5 ) ( 3 ，10 ) 3 b a l a b a ng r a p h ，i i a r r i e sg r a p h ，h a r r i e s w o n gg r a p h 给定面对的最小正则平面i 刳 0 ，11 ) 1 b a l a b a n ( 1 9 7 3 ) ，m y r v o l da n dm c k a y “3 1 1 c o m p l e t eg r a p hk s “，4 1 1 c o m p l e t eb i p a r t i t eg r a p hk 4 , 4 “，5 1 1 r o b e r s t o ng r a p h “，6 ) 1 w o n g ( 1 9 8 2 ) ( 5 ，3 ) 1 c o m p l e t eg r a p hk 6 ( 5 ，4 1 1 c o m p l e t eb i p a n i t eg r a p hk s ，5 f 5 。5 1 4 w o n gg r a p h , f o s t e rg r a p h ，r o b e r t s o n - w e g n e r ，y a l l g 。 ( 5 ，6 ) l f 6 ，3 1 i c o m p l e t eg r a p hk 7 f 6 ，4 ) 1 c o m p l e t eb i p a r t i t eg r a p hk 66 ( 7 ，3 ) i c o m p l e t eg r a p hk 8 f 7 , 4 1 1 c o m p l e t eb i p a r t i t eg r a p hk 7 ，7 f 7 ，5 1 1 h o f f m a n - s i n g l e t o ng r a p h 由此可见，找笼问题仍有广阔的空问有待人们去探索。 2 2 对于给定围长对的正则图的问题 假设g 是一个非树的连通图。g 中最短的奇( 偶) 圈的长度称为g 的奇( 偶) 围 长，如果g 中没有奇( 偶) 圈，则g 中的奇( 偶) 围长被认为是一。令g 表示奇偶田 长中较小的那一个，而h 表示较大的那一个，则b ) 称为g 中的围长对。围长对为味功 的v 正则图称为( v ，凸 ) 图。( v ，g ， ) 一图的最少顶点数记为以v ，g ， ) ，其中v 3 ，3 g 3 和h = o o 。 f r a n kh a r a r y 和p e t e rk o v a c s 2 9 首先得到了最简单的结果坂2 ，。，b ) = 口十b 。g u y 和 h a r a r y 在 3 1 中介绍，k o v a c s 3 0 证明了唯一的( 3 ，4 ，6 ) 笼应该是m 6 b i u sl a d d e r ，而且 必3 ，4 ，b ) 一2 b 一2 。 定理2 8 ( h a r a r y 和k o v a c s 3 2 ) 对于整数三元组v , g , h ，若它满足满足标准条件， 则存在- - + n 长n n o g ，的v 一正则图即( v 岛一图。 大连理r 大学硕