（运筹学与控制论专业论文）关于不同直径的图的最大亏格.pdf

目录 摘要 l 图的可嵌入性的概念源于平面性早在3 0 年代初，首先是波兰的数学 家k k u a t o w s k i ，其后不久，还有美国的数学家h w h i n e y 和s m a c l a n e 都做过精湛的研究他们在这方面分别创立了各自的理论 随着图的可嵌入性问题的深入研究，人们对图在曲面上的可嵌入性有 了一定的理论认识曲面可嵌入性的一个重要组成部分，即所谓上可嵌入 性，或者说使得所在曲面的亏格最大有关这一整个课题刘彦佩已经在他 的专著啕的可嵌入性理论，科学出版社，1 9 9 4 j 中给出了系统的总结 亏格是图的一个拓扑不变量，本文通过对不同直径的图的分类讨论， 得出了几类图的最大亏格，进而讨论它们的上可嵌入性全文共分为四个 部分： 在第一章中。介绍了问题的由来和为了能更准确地从数学上描述或更 便于解决问题所必需的一些基本知识其中包括了关于图的一般嵌入理论 和最大亏格这里对按照直径划分的图的嵌入及最大亏格的研究成果作 了一个概括性的总结，也包含对已有结果的一系列新的简化 第二章中考虑图的直径和连通度，得出一类直径为2 的图的最大亏 格这类问题虽然已经有所研究，在本文中添加了某些参数，借鉴其他文 章考虑了图的衰变数，得到了一些结论。 由于直径为3 的图的最大亏格已经由刘彦佩和黄元秋得出了较为完 全的结果，因此第三章主要研究了直径为4 的图的最大亏格文章对直 径为4 的简单图的最大亏格的讨论是对这类图已得结果的一个改进，从 而达到此类图研究的较为完满的结论 第四章对前面直径为4 的图的最大亏格的研究成果阐述了进一步的 目录 想法。并对直径大于4 的图作了一些理论分析 2 本文的主要目的在于为上面提到的有关图的最大亏格及上可嵌入性 的问题提供一种理论处理。若考虑算法构造，可能会稍显复杂 关键词：亏格；上可嵌入性；直径；b e t t i 亏数；连通度 a b s t r a c t t h e c o n c e p to ft h ee m b e d d a b l eg r a p hc o m e s f r o mt h ep l a n a r i t y i n t h eb e g i n n i n go f3 0 s ，ap o l i s hm a t h e m a t i c i a nf i r s t ，a f t e r w a r da n ds o o n ， s o m em a t h e m a t i c i a n so ft h eu n i t e ds t a t e sd i dt h ec o u s u m m a t er e s e a r c h t h e y 盆l le s t a b l i s h e dt h e o r i e si nt h i sa s p e c t t h r o u g hr e s e a r c ho ft h ep r o b l e mo ft h ee m b e d d a b l eg r a p h ，p e o p l e u n d e r s t a n dt h e o r i e s0 ft h ee m b e d d i n go fg r a p h so i lt h es u r a c e t h e s u r f a c e - e m b e d d i n gc o n t a i n st h ei m p o r t a n tp a r t ，t h e nt h es o - c a l l e du p - e m b e d d a b i l i t y , f o rt h em a x i m u mg e n u so fag r a p h t h eg e n u si sa t o p o l o g i c a li m , a r i a a t t h r o u g ht h ec l a s s i f i c a t i o no f g r a p h st h a th a v ed i f f e r e n td i a m e t e r s ，t h i st e x tg e t sm a x i m u mg e n u so f s e v e r a lg r a p h s ，t h e na n a l y s e st h e i ru p - e m b e d d a b i l i t yt h ef u l lt e x ti s d i v i d e di n t of o u rc h a p t e mt o t a l l y ： i nc h a p t e r1 ，t h eo r i g i no ft h ep r o b l e mi si n t r o d u c e d t oa c c u r a t e l y d e s c r i b eb ym a t h e m a t i c sa n dm o r ee a s i l ys o l v et h ep r o b l e m ，t h e r ea r e s o m ee s s e n t i a lk n o w l e d g e t h e yi n c l u d ee m b e d d i n gt h e o r i e so fg r a p h s a n dm a x i m u m g e n u s a c c o r d i n gt ot h ed i a m e t e ro fg r a p h s ，as u m m a r yo f r e s u l t so ng r a p h i c a le m b e d d i n ga n dm a x i m u mg e n u sw i t has e r i e so fn e w s i m p l i f i c a t i o no ft h er e s u l t si sm a d e i tc o n s i d e r i n gt h ed i a m e t e ra n dt h ec o n n e c t i v i t yo fg r a p h si nc h a p t e r 2 t h em a x i m u m g e n u s 0 ft h e g r a p h t h ed i a m e t e r w i t h0 i sp r e s e n t e d a l t h o u g ht h i sp r o b l e mh a sa l r e a d yb es o l v e d ，t h et e x tc l a r i f i e ss o m ec o n - c l u s i o n s ，w i t hs o m e o t h e rp a r a m e t e r sa n d c o n s i d e r i n gt h ed e c a y o fa g r a p h a l la b o u tt h i st o p i ch a ds y s t e m e t i c a l l yb e e nd e s c r i b e di nt h em o n o - g r a p h e m b e d d a b i l i t yi ng r a p h s ，b o s t o n ：k l u w e ra c a d e m i cp u b l i s h e r s ， 1 9 9 5 1 b yl i uy a n p e i h u a n gy u a n q j ua n dl i uy a n p e ih a da l r e a d ym a d et h em a 五m u m g e n u so ft h eg r a p hw i t hd i a m e t e rt h r e e ，s oi n c h a p t e r3 ，g r a p h sw i t h d i a m e t e rf o u ra r em a i n l ys t u d i e d i nt h i ss e c t o rt h ed i s c u s s i o n o ft h e m a x i m u m g e n u so ft h es i m p l eg r a p h w i t hd i a m e t e rf o u ri sa n i m p r o v e m e n t t h a th a s a l r e a d yg o tt h er e s u l tt ot h i sg r a p h ，t h u sa t t a i nm o r es a t i s f a c t o r v c o n c l u s i o no ft h i sk i n do fg r a p h s i n c h a p t e r4 ，f u r t h e rv i e w p o i n tt ot h ef r o n tr e s e a r c hr e s u l to ft h e g r a p hw i t hd i a m e t e rf o u r ，s o m et h e o r e t i c a la n a l y s i st ot h eg r a p ht h a th a s d i a m e t e rb i g g e rt h a nf o u ri ss h o w n t h ep u r p o s eo ft h i st h e s i si st op r o v i d eat h e o r e t i c a lt r e a t m e n tf o r t h ep r o b l e m so nt h em a x i m u m g e n u so fag r a p ha n du p - e m b c d d a b i l i t yi f a l g o r i t h m s & r ec o n s i d e r e d ，s o m ec o m p l i c a t i o nw o u l da p p e a r k e y w o r d s ：g e n u s ；u p - e m b e d d a b l e ；d i a m e t e r ；b e t t id e f i c i e n c y ；c o n n e c - t i v i t y 第一章引言与综述 1 1 引言 电子技术和现代化计算机的发展为数学提供的新问题层出不穷对 于这些问题的深入理解和精湛研究正在或已经开拓出数学中一些新的分 支科学。图的可嵌入性问题不仅是组合地图理论中的基础，而且在诸如大 规模和超大规模集成电路的设计和制造的自动化的研究过程中有着现实 意义 本文所讨论的图是一个抽象的数学概念拓扑图论研究图在拓扑曲 面上的嵌入，研究在嵌入过程中的拓扑不变量一直以来，数学工作者们 致力于各类图在亏格不同的曲面上嵌入的存在性及存在数量的研究。旱 在上个世纪7 0 年代【以及2 0 年后】刘彦佩的专著 1 中就提到了图的曲面 嵌入并且通过图g 的码论证明在曲面( 可定向与不可定向的) 上嵌入的存 在性 按照直径分类来研究图的嵌入在最近引起了这一领域内人士的广泛 关注黄元秋和刘彦佩【2 】得到了对于简单连通图g 。若存在一个点“ v ( g ) 使得对任何点$ v ( g ) ，z “，z 都与u 相邻，则g 是上可嵌 入的即赢径为1 的图的最大亏格7 f ( g ) = 【l 譬 另外，s k o v e r i a i s 还 得出了直径为2 的图的最大亏格，并且证明了如果g 是个直径为2 的 无环图，那么g 是上可嵌入的，且若g 是个2 一连通图( 允许有环) ， 则( g ) 4 ，即 4 譬1 2 7 m ( g ) i 警j 。进而计算了g 的点连通 度是1 的7 m ( g ) 的值此外，x u o n g 4 1 证明了每个4 一边连通图是上可 5 第一章引言与综述 6 嵌入的c h e n n 得到了对于所有点的度数都大于2 的2 连通图，其最 大亏格至少为g 譬的结论 黄元秋和刘彦佩还得到了如果g 是一个直径为3 的简单图，则g 是 上可嵌入鹊，但要排除。一图或3 一图这两个镪外，它们的“g ) = 2 ， 即最大亏格7 m ( g ) = i ! 喾其中2 图的定义为：令r 和易是两 个奇b e t t i 数的简单图，存在u i y ( 只) 使得对v x j y ( f j ) ，q “i ， 与u ，相邻0 = 1 ，2 ) ，则2 - 图由连接u l 和地得到就形式而 言，y ( 2 ) = y ( r ) uy ( f 2 ) ，且e ( x 2 ) = e ( f 1 ) ue ( f 2 ) u u l u 2 3 图的定义为t 令g 1 ，g 2 ，g 3 是三个奇数个b e t t i 数的简单圈， 存在，饥y ( c 。) ( 可能u i = n ) 使得对v 甄ey ( c d ，戤u t ，u 忍 与和坎相邻( i = 1 ，2 ，3 ) ，则连接u l 和“2 ，饥和“3 ，也和地得到 3 一图就形式而言，y ( 3 ) = v ( c 1 ) uv ( g 2 ) ov ( c 3 ) ，且e ( a 3 ) = e ( g 1 ) ue ( g 2 ) oe ( g 3 ) u l l u 2 ，m u 3 ，v 2 u 3 至此，直径为3 的图的最大亏格问题就已解决完全自然地，对于直 径大于3 的图的最大亏格问题就被提出来了本文就对这一问题作了些 工作 1 2 基本概念 一个图用g = ( m e ) 表示，就是一个集合y 和y 上的一个二元 关系e = ( u ， ) 1 v “， v ) 其中y 称为节点集，其元素称为节点；e 称为边集，它的元素称为边在一个图中，与节点口关联的边的个数，称 为顶点”的度，用d ( 口) 表示设u 和”为图g 的任意两点，u 和u 之 闯的距离，记为d g 缸，”) ，是g 中连接u 和v 之间的最短路的长度一 第一章引言与综述 7 个图的直径，记为d ( g ) ，是g 中所有两点之间距离的最大者 若一条边的两个节点重合。则称之为环若两个节点之间的边多于一 条，则称之为重边既无重边也无环的图称为简单图若y 中含有有限个 节点，称这时的图g 为有限的在图g 中，若p = e 1 1 e 2 ，、8 k 是一个顶点和边的交替序列，使e 。= ( “，) ，v i = 1 ，2 ，k ，称p 为 从“o 到“的途径“o 和分别称为p 的起点和终点p 的长度为 k 在一个途径中。若任意两条边皆不相同，则称之为迹若在迹中任意 两个节点皆不相同，则称之为路起点和终点相同的途径，迹和路分别称 为迂，回和圈长为k 的圈。按k 是奇数还是偶数，称k 圈是奇圈或偶 圈若一个图中任意两个节点之间存在一条路。则称此图是连通的图g 的每一个连通的部分。称为它的一个连通分支对于一个图g 中的任意 一条边e ，记号g 。表示从g 中删除边e 所得到的图，常称之为图g 的 一个删边主子图若g 。的连通分支数大于图g 的连通分支数，称e 为 图g 的割边设u 为g 的一个节点，g u 表示从g 中去掉节点u 以 及与u 关联的所有边所得到的图，若图g 一“的连通分支数大于图g 的 连通分支数，则称u 为g 的一个割点若y 的子集v 7 使得g 一不连 通，则y 称为g 的顶点割k 顶点割是指有k 个元素的顶点割若g 至少有一对相异的不相邻顶点，则g 所具有的k 顶点割中最小的k ，称 为图g 的连通度，记为k ( e ) 若k ( v ) k ，则称g 为k 一连通的本 文所讨论的图皆为有限，无向的连通图 若图g 中任意两节点间均有边相连，则称g 为完全图，记为j 厶。其 中，n 为g 的节点数设两个图g 和日分别为g = e ) ，h = ( u ，e 1 ) ， 若k 晶e 则称h 是g 的一个子图( 记为日冬g ) 若k = v ， 则称h 是g 的一个支撑予图假设1 ，是y 的个非空子集，以v 为 第一章引言与综述 8 节点集。以两端点均在y 7 中的边的全体为边集所组成的子圈，称为g 的 由v 7 导出的子图，也称点导出于图容易看出，任何一个图均是同阶或 更高阶的完全图之子图只有一个节点的孤立图称为平凡的 不含圈的连通图称为树，在一棵树中，任意两个节点均由唯一的路连 接由于树本身即是一个支撑子图，故可称为支撑树。如果r 是图g = ( k e ) 的一个支撑树，则g 的支撑子图t + = ( k e k e ( 丁) ) 被称为g 的 一个上树称由上树的一边与相应的树所确定的圈为基本圈不管怎样取 图上的树，基本圈的数目均为i e 卜l yj + 1 ，称其为基圈数这里f y i 表 示节点集y 中元素的个数 l ，3 嵌入及最大亏格 在拓扑学中，这里所说的曲面就是无边缘的2 - 维紧闭流形事实上， 可以视为平面上的个偶数条边的正多边形，每边分配个方向且两两成 对，将同一对边依同方向合而为一所得到的注意，在合而为一的过程中， 可以收缩或伸长，但不能断裂 曲面闭曲线公理在曲面上的任何一条闭曲线，要么有两侧( 左侧和 右侧) ，要么只有一侧，二者必居其一 一个曲面，若其上的所有闭曲线全是双侧的。则称它为可定向的；否 则为不可定向 将一个图g = ( u e ) 的节点放在一个曲面s 上用点表示，当然不 同的节点相应不同的点然后，将边作为连接相应端点的两点之间的连续 曲线如果所有代表边的曲线本身无重点，而且彼此之间除端点可能公共 外，再无其他公共点，则称g 在曲面s 上的这种实现，为它在曲面s 上 第一章引言与综述 9 的一个嵌入 注意，在这个定义中，自然蕴含每一条代表边的曲线不可能有内点相 应g 的节点因为这样必然引起两条代表边的曲线有一个公共点至少不 是其中一条曲线的端点 若记u ( g ) 为g 在曲面s 上的一个嵌入，则s 弘( g ) 将由若干连通 部分组成一般而言，在这些连通部分中可能有的不与圆盘( 单位圆的内 部区域) 拓扑等价由于这样的连通部分的出现对于这里所研究的问题无 关紧要，因此，只限于讨论所有这些连通部分都与圆盘拓扑等价的情形 并将这种嵌入称为胞腔嵌入那些连通部分被称为这个嵌入的面因为总 讨论这种嵌入，也就简称为嵌入下面，凡提及嵌入均指胞腔嵌入 图g 的最大亏格，记为7 m ( g ) ( 亏格，记为7 ( g ) ) ，是指最大( 最小) 的整数k 使得g 能嵌入亏格为k 的可定向曲面s 上 一个多面形就是多边形的一个集合对于一个多面形 x ( m ) = i y ( g ) | _ l e ( g ) i + l ( g ) i( 1 1 ) 被称为e u l e r 示性数这里咖( g ) 表示图g 的嵌入的面集合 引理1 1 【1 日 x ( m ) ： 2 2 7 ，若m 为亏格为，y 的可定向曲面，7 o ； l2 7 ，若m 为亏格为，y 的不可定向曲面，7 o ； 引理1 21 1 l 对于一个图g = ( v e ) ( 当然，简单而且连通的) 令 g ( ) 为g 在一个曲面s ( 可定向与不可定向) 上的一个嵌入或简记 g ( ) cs 则，有 i y ( g ) l l e ( g ) i + 1 茎( s ) si v ( g ) i 一阜 ( 1 2 ) 第一章引言与综述 t 0 其中，x ( s ) 为曲面s 的e u l e r 示性数 如果一个图可以嵌入到e u l e r 示性数为( 1 2 ) 所示的下界或上界的曲 面上，则分别称它们为下可嵌入的或上可嵌入的因为一个图g 在任意 可定向曲面的嵌入中至少有一个面，则易得g 的最大亏格上界7 m ( g ) ( 2 譬 同时，称一个图g 是上可嵌入的，若7 m ( g ) = 2 笋1 另外，对于x e ( g ) ，c x 表示从g 中去掉x 中的所有边所得 到的图若丁为图g 的一棵支撑树，记号f ( g ，t ) 表示g e ( t ) 的边数为 奇数的连通分支数称( g ) = m i n t ( g ，t ) 为g 的b e t t i 亏数，其中m i n 取遍g 的所有支撑树t 对于连通图g ，称p ( g ) = i e ( g ) l _ l 矿( g ) l + l 为g 的圈秩数( 或b e t t i 数) 显见，p ( g ) 与f ( g ) 同奇偶性。又，对g 的任意边子集a ，记号c ( c a ) 表示g a 的连通分支数；而记号b ( v a ) 表示g a 中具有b e t t i 数为奇数的连通分支数 第二章一类直径为3 的2 一连通图的最大亏格 2 1 有关理论结果 这一章关于图的最大亏格的讨论中，考虑了图的衰变数，s k o v i e r a 7 定义了g 的衰变数e ( g ) ，它是g 的所有上树中连通分支数c ( g t ) 的 最小值，并且说明了 e ( g ) = 2 n ( g ) 一m ( c ) 一14 - m i n f l ( g t ) ( 21 ) 这里，m ( c ) 表示图g 的边数，礼( g ) 表示图g 的节点数 关于图的最大亏格，文献【1 1 给出了用f ( g ) 刻画7 m ( c ) 的一个公 式，即： 定理2 1 设g 为图，则一r m ( g ) = 业糊2 ，且g 是上可嵌入的， 当且仅当 ( g ) 1 对于直径为2 的2 一连通图，s k o v i e r a 4 1 给出了下面的结果： 定理22 如果g 是直径为2 的2 - 连通图，则f ( g ) 3 的情形与i e ( w a ) i = 3 的情形讨论类似，这里只 讨论l e ( w a ) i = 3 由讨论i e ( 眦a ) i = 2 时的情形可知，此时与相邻的3 个连通分支 必定两两相邻设这三个连通分支分别为m ， ，2 ，w 3 ，w 以及与w 相邻 的任一个连通分支都与其它的3 个以上的连通分支相邻，即i e ( 暇，a ) l 3 ，i = 1 ，2 ，3 若存在连通分支p 跪与某个睨相邻，对任意点 p v ( p ) ，最短路p g ( p 1 ， ) 必含有4 条边，其中d ( v ，u ) = 2 ，另外两 条边分别属于集合e ( m m ，w 2 ，w 3 ) ) 和集合e ( p 仉，l ，w 2 ，w 3 ) ) ，故 p l 必为p 的一个接触点由p 1 的任意性知，p 中所有点均为接触点 由引理3 , 6 知i y ( p ) l 4 ，故i e ( p a ) l 4 由此，i k 眦以及与w 相邻的所有连通分支在a 中的边都至少为3 条 情形2 t g a 的所有连通分支队接触点都至少为2 回到前面讨论的存在a e ( g ) ，使得有卟连通分支f ，i e ( f ，a ) i = 第三章直径为4 的图的最大亏格 2 6 3 的情形，证明其中两个接触点即可不妨设这两个接触点为 ，止 v ( f ) 若，l 厶茌e ( c ) ，即d ( ，2 ) 2 此时，历和玩必然相邻，假 设h 1 ，日2 都不与虢中其它的连通分支相邻，那么日l 中与h l 不相邻的 点与日3 中异于虬的点的距离都大于4 ，此与定理条件矛盾，故假设不 成立，即日- ，中至少有一个与其它连通分支相邻，不妨设皿与其它 的两个连通分支相邻，则j e ( h 1 ，a ) j 3 若，1 ，2 e ( c ) ，e l = ( ，h i ) ，e 2 = ( ，2 ，k ) ，其中e l ，e 2 a ， h l y ( 研) 。，一h 2 y ( 也) 存在g l y ( 吼) 。卯y ( 凰) 。且 g l h l e ( g ) ，9 2 h 2 e ( g ) ；存在 v ( h 1 ) ，j 2 y ( 凰) ，且 j l h i e ( g ) ，j , h 2 e ( g ) 假设i e ( h 1 ，a ) 1 = 2 ，不妨设f 以外的 与h 相邻的那个连通分支为b ，同时设f ( 肌，b ) = e 4 ) 为满足条件 d ( g l ，9 2 ) 4 ，d ( j l ，如) 茎4 ，必定有e 4 = ( g l ，b x ) 。e 5 = ( 9 2 ，b 1 ) ，其中b 1 为b 的个接触点若b 为b ，则令凰为要证明的日1 即可；若b 为 既以外的连通分支，则需要另外的一个连通分支b 来连接凰和巩( 或 f 如和t t 3 ) 来满足与上面情形类似时定理的条件，即i e ( h 1 ，b 川= 1 这样，不论如何，i e ( h 1 ，a ) 3 这样就证明了断言口 引理3 7l e ( z ，x u y ) i24 1 z l t “】 引理3 8l e x u y l 1 x l 【1 1 】 由断言2 可得，在图g e 。中， e ( 风，a ) l22 又，由于集合e ( 五x u y ) ，e ( x uy 日l ，h 2 ，塌) ) ，e ( ，现，日3 ) ， f ) 以及f k 。y 均是a 的子集。且两两不交，敌在图晚，中有： l a l l e ( z ，x u y ) i + i e ( x u r h 1 ，h 2 ，风) ) i + i e ( 丑j ，塌) ， f ) ) i + l e x u y + l e ( h i ，肖) 第三章直径为4 的图的最大亏格 4 1 2 1 + i x i + 2 i y l + 2 + 1 x l + 2 由引理3 1 性质( 5 ) 有 ( g 。) = 2 i 搋i i a l 一1 2 ( i z l + i x l + i y l + 4 ) 一( 4 i z i + 2 l y i + 2 i x i + 4 ) 一1 3 2 i z i 综上所述，有( g 。) 3 从而，对于一切( g 。) 2 ，m h 代( g 。) i e e ( g ) 卜一ls2 。故f ( g ) 2 对于g 。的其它情形，显然有( g ) 曼2 至此完成了定理的证明n 为说明直径是4 且不含3 阶完全子图恐的图的最大亏格下界已不 能再改进，现给出一例，如下图所示此图符合定理条件，且( g ) = 2 k | ，j | t 沙 谬懑 图3 第四章结束语 关于直径为4 的图的最大亏格虽然已经得到了一些比较好的结果， 在这里有一些进一步的想法若g 为直径为4 的简单图，g 不含3 阶完 全子图 3 ，则，可将这样的图分为两类，一类为上可嵌入图，另一类的 b e t t i 亏数 ( g ) = 2 并且b e t t i 亏数f ( g ) 为2 的图应相对力少数，出 定理3 2 证明过程中可以分析得到这个想法，但具体划分可能稍显复杂 至此，直径为4 的筒单图已基本分析完全在考虑直径大于4 的简 单图时，首先，因对于任意大的正数m ，总存在直径为4 的图g 使得 ( g ) m ，所以。对于任意大的正数m ，必存在直径大于4 的图g 使 得( g ) m 对于直径大于4 的图而言，由于节点和边的增多使得这类图更加复 杂，也呈现出较多的类别，这给研究这些图的性质及嵌入问题增加了许多 困难但是可以想象总有一定的规律可循，并且由于直径为5 的图可以 由直径小于5 的图减边或加点构造而成，形式上与直径小于5 的图有一 定的联系。而直径小于5 的简单图的最大亏格已经得到了较为完全的结 果，所以应该能够找到途径解决某些问题 参考文献 e 1 】刘彦佩，图的可嵌入性理论，科学出版社1 9 9 4 【2 】y u a n q i uh u m a g ，y a n p e il i u t h em a x i m u mg e n u so f g r a p h sw i t hd i a m e t e r t h r e e d i s c r e t em a t h 1 9 4 ( 1 9 9 9 ) 1 3 9 - 1 4 9 【3 】m s k o v i e r a t h em a x i m u mg e n u so fd i a m e t e r t w o d i s c r e t em a t h 8 7 ( 1 9 9 1 ) 1 7 5 1 8 0 ， f 4 1 n hx u o n g ，u p p e re m b e d d a b l eg r a p h sa n dr e l a t e d t o p i c s j c o m b i n t h e o r yb2 6 ( 1 9 7 9 ) 2 2 6 - 2 3 2 【5 】5j c h e n ，d a r c h d e a c o n ，l g r o s s d i s c r e t em a t h 1 4 9 ( 1 9 9 6 ) 1 9 2 9 【6 刘彦佩图的不可定向最大亏格 2 0 1 m a x i m u mg e n u sa n dc o m m e c t i v i t y 中国科学，数学专辑( i ) ( 1 9 7 9 ) 1 9 1 一 1 7 】m r s k o v m r a t h ed e c a yn u m b e ra n dt h em a x i m u mg e n u so fag r a p h s m a t h e m a t i c ss l a v a c a 1 9 9 2 ，4 2 ( 4 ) ：3 9 1 4 0 6 【8 】u ，s ，r m u r t y e x t e r n a l n o n s e p e r a b l eg r a p h s o fd i a m e t e r2 i n ：f h a r a r y ( e d ) ，p r o o ft e c h n q u e si ng r a p ht h e o r y a c a d e m i cp r e s s n e w y o r k 1 9 6 9 ，1 1 ：1 1 1 ：1 1 8 【9 】9 h u n g l i n f u ，m i n c h u