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

北京交通大学硕士学位论文中文摘要 中文摘要 摘要： 图的可嵌入性的概念源于平面性，早在3 0 年代初，波兰数学家k k u a t o w s k i 和 其后美国数学家h w h i t n e y ，s m a c l a n e 在图的可嵌入性方面做过精湛的研究他 们在该方面都创立了各自的理论5 0 年代，中国数学家吴文俊基于代数拓扑学中的 理论揭示了判定图的平面性的个判断准则，其后又得到许多学者的改进，提出了 更好的算法，如刘彦佩【1 1 基于确向树，使算法的复杂性上达到了线性顶峰，在图的 平面性和平面嵌入上做出很大的贡献随着研究的深入，到7 0 年代，n o r d h u a se ， s t e w a r tb ，w h i t ea 2 1 等人提出了图在曲面上的可嵌入性问题，其中最大亏格问 题及图的上可嵌入性是重要的组成部分 亏格是圈的一个拓扑不变量，本文主要总结和研究了图在曲面上嵌入的最大 亏格，揭示了图的某种属性或含有一定特征的图对其最大亏格的影响全文分为三 部分： 在第一章中，首先介绍了图论中图的参数的基本定义，综述了固的嵌入性理 论的基本知识，从图的平面嵌入引出了图在曲面上的嵌入，重点叙述了图的最大亏 格理论，两个确定最大亏格的基本定理，一个是x u o n g 的理论【4 】，一个是n e b e s k 哲 理论f 5 1 ，两者都足同绕着与图的最大亏格十分密切的参数b e t t i 亏数的大小，揭示 了最大亏格的计算方法之后，黄元秋 6 】在n e b e s k 艘论 5 】的摹础上，给出了参 数b e t t i 亏数与图的特征结构的关系，为从罔的结构上来研究罔的最大亏格开辟了 一个新的途径 在第二章中，介绍了一些目前已得到的关于图的最大亏格与某些图的参数的 理论结果，这些参数包括顶点的度，图的连通度，直径，围长，割点，独立数，嵌入 的面的度数，着色数，正则性，2 - 因子等对于图的直径，黄元秋和刘彦佩f 1 0 1 得到 了一类直径为4 的不含虬子图的简单连通图的最大亏格的下界，但是该下界并非 是紧的下界在第二节中，通过分析和证明改进了他们的结果，并发表了文章【2 9 】， 文章中得出改进的结果为紧的下界最后，对于任意的有限无向的无环图。给出了 一种构造上可嵌入图的方法 第三章为结束语，对最大亏格的某些方面的研究，文中提出了自己的看法，希 望所指出的想法能够给以后的研究工作带来益处 关键词：亏格，b e t t i 亏数，上可嵌入性 分类号：0 1 5 7 5 北京交通大学硕士学位论文 a b s t r a c t a b s t a c t ： a b s t r a c t t h ec o n c e p to ft h ee m b e d d a b l i l i t yo fg r a p hc o m e 8f r o mt h ep l a n a r i t y i nt h e b 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 nk k u a t o w s k ia n dm a t h e m a t i c i a no ft h e u n i t e ds t a t e sh w h i t n e y , s m a c l a n ed i dt h ec o n s u m m a t er e s e a r c hi nt h ee m b e d - d a b h h t yo fg r a p h t h e yf o u n dt h et h e o r yb yt h e m s e l f i nt h e5 0 s w e n j u nw ut h e m a t h e m a t i c i a no fc h i n a ，p r o v e dar u l ea b o u tt h ep l a n a r i t yo fg r a p hb a s e do nt h e a l g e b r at o p o l o g y a n ds o m es c h o l a r sl a t e ra m e l i o r a t e dt h i sr e s u l ta n db r o u g h tf o r - w a r dt h eb e t t e ra r i t h m e t i c y a n p e i 1 】l i um a d ec o m p l i c a c yo fa r i t h m e t i co nt h e t o p i tm a d eg r e a tc o n t r i b u t i o ni np l a n a r i t ya n de m b e d d a b i l i t yo fg r a p h t h r o u g h r e s e a r c ho ft h ep r o b l e m ，i nt h e7 0 s ，n o r d h u a se ，s t e w a r tb ，w l l i t ea 2 】b r o u g h tf o r - w a r dt h ep r o b l e mo fg r a p he m b e d d i n go ut h es u r f a c e a n dt h em a x i m u mg e n u s a n du p - e m b e d d a b i h t yo fag r a p ha r et h ei m p o r t a n tp a r t sa b o u tt h eg r a p he m b e d - d i n go nt h es u r f a c e ， t h e g e n u si sat o p o l o g i c a li n v a r i a n t t h i st e x ts u mu pa n dr e s e a r c hm a x i m u m g e n u so ft h eg r a p hw h i c hh a ss o m ep r o p e r t i e so ra n yo n ec h a r a c t e r t h ea l lt e x ti s p a r t i t i o n e dt ot h r e ep o r t i o n s i nc h a p t e r1 ，f i r s tt h e r ea r es o m ee s s e n t i a lk n o w l e d g ea b o u tg r a p hi n c l u d i n g t h et h e o r yo fe m b e d d a b i l i t yo fg r a p hf r o mt h eg r a p he m b e d d i n go np l a n et os u r - f a c e ，t h et e x tm o s t l yd e p i c t st h et h e o r y o fm a x i m u mg e n u s i ti n c l u d e st w oe s s e n t i a lt h e o r y , o n ei sx u o n g st h e o r y 4 j ，t h eo t h e ri sn e b e e 蚴st h e o r y 4 t h e yb o t h u s et h ep a r a m e t e rb e t t id e f i c i e n c yt oc o n f i r mt h ec o m p u t i n gm e t h o do fm a x i m u m g e n u s s u b s e q u e n t l ya c c o r d i n gt ot h en e b e s k 哲st h e o r y 5 ，y u a n q i uh u a n g 6 p r o - r i d e sac o n n e c t i o nb e t w e e nb e t t id e f i c i e n c ya n ds t r u c t u r a lc h a r a c t e ro fg r a p h i t i n a u g u r a t e san e ww a yo fr e s e a r c ho fm a x i m u mg e n u sf r o mt h es t r u c t u r a lc h a r a c t e r o fg r a p h i nc h a p t e r2 s o m er e s u l t st h a th a v eb ek n o w na b o u tm a x i m u mg e n u sa n d p a r a m e t e r so fg r a p hc o u l db er e c a p i t u l a t e d t h e s ep a r a m e t e r si n c l u d ed e g r e eo f v e r t e x ，c o n n e c t i v i t yo fg r a p h ，d i a m e t e r ，c u t - v e r t i c e s ，i n d e p e n d e n c en u m b e r ，d e g r e eo f e m b e d d a b l er e g i o n ，c o l o rn u m b e r ，r e g u l a r ，7 - f a c t o ra n ds oo n a b o u td i a m e t e ry u a n - q i uh u a n ga n dy a n p e il i u 1 0 p r o v et h el o w e rb o u n do fm a x i m u mg e n u so fg r a p h gw i t hd i a m e t e rf o u rn o tc o n t a i n i n gc o m p l e t es u b g r a p hk 3 b u tt h i sr e s u l ti 8 n o ts h a r p i nt h es e c o n ds e c t i o n ，t h et e x ti m p r o v et h er e s u l t ih a v ep u b h s h e da a r t i c l e 2 9 i nt h ea r t i c l e ，i ts h o w st h a tt h er e s u l ti ss h a r p l a s t f o rt h ed i s c r e t i o n a l 北京交通大学硕士学位论文 a b s t r a c t f i n i t eu n d i r e c t e da c y c l i cg r a p h ，am e t h o do fc o n s t r u c t i n gu p - e m b e d d a b l eg r a p hi s p r o v i d e d i nc h a p t e r3 , i ti st a g t h e r ea r es o m em yo p i n i o n sa b o u tt h em a x i m u mg e n u s i h o p et h a ti tc o u l dp r o v i d eal i t t l eh e l pf o rt h ew o r ko fr e s e a r c hi nt h ef u t u r e k e y w o r d s ：g e n u s ，b e t t id e f i c i e n c yn u m b e r ，u p - e m b e d d a b i l i t y c l a s s n o ：0 1 5 7 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国家 有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 签字日期：年月日签字只期：年月日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名：签字日期：年月日 北京交通大学硕士学位论文第一章绪论 1 图的基本概念 第一章绪论 一个图g ，是由非空的顶点集v ( g ) ( 称顶点) 和顶点集中无序的点对( 称为 边) 的集合e ( g ) 构成的，用g = ( v e ) 表示，其中，e = ( u ， ) iv u ，州iy 在一 个图中，与顶点v 关联的边的个数，称为顶点”的度，用d ( ) 表示 定理1 1 1 设图g = ( k 日) ，有n 个顶点，顶点集y = 口1 ，忱，地，) ，有m 条 边，则 d ( 口) = 2 m 口v 假若我们将y 中的顶点依它的度为奇数或偶数而分为奇顶点或偶顶点，则上 述定理左边是y 中奇顶点度数与偶顶点度数之和有此定理即可得知一个推论 推论1 1 2 在任何图中，奇顶点的个数为偶数个 着图的所有顶点v ，都有d ( v ) = k ，称图是自币则的设u 和v 为罔g 的任意两个 顶点，“和v 之日j 的距离，记为d g ( u ， ) ，表示g 中连接u 和v 之间的最短路的长度，一 个图的直径，记为d f g l ，使g 中所有两点距离的最大者 若边的端点重合为一个点，称为环若两个顶点之问的边多于一条，称之为重 边一个既没有环也没有重边的图称为简单图如果图的顶点集和边集都是有限 的，罔称为有限图若图的顶点集中的点对是有序的，图称为有向图，丰 反称为无 向图每一对不同的顶点都有一条边相连的简单罔称为完全图n 个顶点的完全图 记为。 有两个图g 和日，若v ( h ) y ( g ) ，e ( h ) e ( g ) ，称日为g 的子图，记 为日g 假设y 7 是y 一个非空子集，以y 为顶点集，以两个顶点均在y 中的边 的全体为边集所组成的子图，称为g 的由导出的子图，记为g f y ，】，g v 是指 从g 中删除y7 中的顶点以及与这些顶点关联的边所得到的图假设是e 一个非空 子集，以为边集，以e 中的边的顶点为顶点集所组成的子图，称为g 的由e 导出 的子图，记为g e 1 ，g e 是指从a 书删除e 中的边所得到的图 在图g 中，若p = 札o e l t l e 2 8 是一个顶点和边的交替序列，使岛= ( - 1 撕) ，= 1 ，2 ，膏，称p 为从u o n u k 的途径，u o 到“分别称为p 的起点和终 点p 的长度为k 在一个途径中，若任意两条边皆不相同，则称之为迹若在迹中任 意两个节点皆不相同，则称之为路起点和终点相同的途径，迹和路分别称为闭途 径，闭迹和圈长为k 的圈，按k 是奇数还是偶数，称k 圈是奇圈或偶圈若一个图中 北京交通大学硕士学位论文第一章绪论 任意两个节点之间存在一条路，则称此图足连通的图g 的每一个连通的部分，称 为它的一个连通分支 如果图g = ( ve ) 的顶点集v 可以划分为个子集k ，k ，使得在任意 子集中的任何两个顶点都不相邻，则称它为n 部图最常用的是二部图，一般记 为g = ( k ，阮；e ) ，如果h ，k 两个集合的顶点都相邻，则称完全二部图，常记为。，。， 其中l i = n 1 ，l k l = n 2 定理1 1 3 一个图g 是二部图，当且仅当在g 中无奇圈， 设为图g 的一个节点，g - u 表示从g 中去掉节点 以及与关联的所有边所得 的图，若图g - u 的连通分支数大于图g 的连通分支数。皿称u 为g 的一个割点若y 的 子集y 使得g y7 不连通，! l l u 称为g 的顶点割个元素的顶点割是k 顶点割若g 至 少有一对互异的不相邻的顶点，萸u g 所具有的k 顶点割中最小的k ，称为g 的连通 度，记为( g ) ；若k ( g ) k ，则称g 为七一连通的设e 为图g 的一条边，g e 表示 从g 中去掉边e 所得到的图，若图g e 的连通分支数大于图g 的连通分支数，则 称e 为g 的割边若e 的子集彰使得g 不连通，则称为g 的边割k 个元素的边割 是k 边割g 的所有k 边割中最小的k ，称为g 的边连通度，记为k ( g ) 对于图中的任一个顶点子集，如果其中的任何两个顶点存此图中均不相邻， 则称它为独立的顶点集相仿地，对于边的一个子集，如果其中任何两条边均不与 同一个顶点关联，m 称它为图的一个对集可见，对集足边的对立集进而，如果一 个对集于冈中的所有顶点都关联，则称它为完美对集容易看出，并不是所有的图 都有完美对集 图g 的一个k 顶点着色是指k 种颜色1 ，2 ，府对于g 的各顶点的一个分配称着 色是正常的，如果任意两个丰h 邻顶点都分配到不同的颜色当g 有一个正常k 顶点着 色时，就称g 是k 顶点可着色的，简称k 可着色g 的色数是指g 为k 可着色的数枷i 勺最 小值，记为x ( g ) 若x ( c ) = 七，则称g 是k 色的g 的围长是指g 中最小的圈的长度 不含圈的图称为无圈罔连通的无罔图称为树设连通图g = ( k e ) 有一个 树t = ( k e ) ，称树丁为图g 的支撑树 2 曲面 存拓扑学中，曲面是指无边缘的二维紧闭流形事实上，可以视为平面上的一 个偶数条边的正多边形，每边分配一个方向且两两成对，将同一对边依同方向合 面为一所得到的在合而为一的过程中，可以收缩或伸长，但不能断裂 例如，在图1 2 1 中，虚线的两端表示同个点左图为球面，或视为含无限远 点的平面右图为射影平面 2 北京交通大学硕士学位论文 第一章绪论 4 口 璋蔫乎薯 封髟警蕾 图1 2 1 球面与射影甲面 定理1 2 1 曲面闭曲线公理 在曲面上的任何一条闭曲线，要么有两侧( 左侧和右侧) ，要么只有一侧，二者 必居其一 有两侧的闭曲线被称为双侧曲线，否则成为单侧曲线从图i 2 1 可以看出，在 球面上的任何一个闭曲线均有两侧，然而，存射影平面上，则不同了，有的闭曲线 有两侧，也有的闭曲线如虚线所示，只有一侧如何判断曲面上的一条闭曲线足有 两侧还是只有一侧呢? 这就要引进可压缩性的概念若果曲面上的一条闭曲线，可 以沿某侧连续地收缩到一点，则称它为可压缩的 可以看出，单侧闭曲线不足可压缩的双侧闭曲线足可压缩的一个衄面，若其 上的所有闭曲线全是双侧的，则称它为可定向的；否则为不可定向的在图1 2 i 中， 球面是可定向的而射影平面足不可定向的 我们将球面写为n 口一1 ，即沿多边形边缘走一周所经过边的次序用幂区别方 向即射影平面记为n o 一般地，有 啡p o ) 全是可定向的曲面，0 0 表示球面q q ( q 1 ) 全是不可定向的曲面 3 图的嵌入 将一个图g = ( k e ) 的顶点放在一个曲面s 上用点表示，不同的顶点相应不 同的点，然后，将图g 的边作为连接相应端点的两点之间的连续曲线如果所有代 3 蟮一嘶 玩 o ，：i = q on 。m = qq 北京交通大学硕士学位论文 第一章绪论 表边的曲线自身无重点，而且彼此之间除端点可能公共外，再无其他公共点，则 称g 在曲面s 上的这种实现，为它在s 上的一个嵌入 若记“( g ) 为g 在曲面s 上的一个嵌入，则s 肛( g ) 将由若干连通部分组成一般 而言，在这些连通部分中可能有的不与圆盘( 单位圆的内部区域) 拓扑等价由于这 样的连通部分的出现，对于这里所研究的问题无关紧要，所以只限于讨论所有这 些连通部分都与圆盘拓扑等价的情形并将这种嵌入称为胞腔嵌入那些连通部分 被称为这个嵌入的面因为总讨论这种嵌入，也就简称为嵌入下面凡提及嵌入均 指胞腔嵌入 一个图可嵌入到球面上，称图足可平面的 定理1 3 1 e u l e r 平面定理 如果g 是一个连通的平面图，g 有p 个顶点，q 条边和r 个面，则 p q 4r = 2 设非空图g ，e = 让 为图g 的一条边，g 的初等剖分，是指删除边e ，加入一个新 的顶点w 和新边u w ，v w 图g 的一个剖分图足指g 经过一系列的初等剖分后等到的 图如果图驯司构于g 或者日同构于g 的一个剖分，则称日同胚于g 一个图g 。同胚 于g 2 ，着存在图g 3 使得g l 和g 。均同胚于g 3 可见同肝是一个等价关系这样着g 足 一个平面图或非平面图，则任何一个同肝于g 的图也是一个平面罔或非甲面图明 显，g 如果包含一个1 f 平面的子图，则g 也是一个非平面图通过上述事实，得到一 个判定图足否为甲面图的著名k u r a t o w s k z 定理首先看一个引理，该引理指出了 两个重要的非平面图 定理1 3 2 图蚝和k 3 ，3 均为非平面图 硷7 粼 定理1 3 3 k u r a t o w s k i 定理 一个图g 是平面图当且仅当g 不包舍子图同胚于恐或恐3 4 北京交通大学硕士学位论文第一章绪论 曲面是一个紧的，定向的2 维流形，曲面可被认为是在球面上按上一系列的手 柄，手柄的数量定义为该曲面的亏格一个图g 的亏格是指图g 可嵌入的所有曲面 中最小的亏格数，记为，y ( g ) 例如，平面图是亏格为。的图，恐和凰，3 是亏格为1 的 图对于图在曲面上的嵌入，有以下著名的e u l e r 定理 定理1 3 4 j 阢l e 啶理 p q r = 2 2 n 其中，p 为图g 的顶点数，q g j 图g 的边数，r ) 0 图g 在曲面上绷包腔嵌入的面 数，n 为曲面的亏格 若一个图嵌入( 不一定是2 胞腔嵌入) 在曲面上，满足上式，则可得此嵌入为2 胞 腔嵌入 4 最大亏格 设g 是一个有限、无向的连通图，本文以后考虑的图若没有明确指明，均指 这类图图g 的最大亏格是指这样的一个最大整数k 使得g 在亏格为k 的定向曲面上 有2 一胞腔嵌入，记为7 m ( g ) 设7 ( g ) 是图g 的亏格则有如下定理 定理1 4 1 一个连通图g 在曲面s k - k 有绷包腔嵌入当且仅当，y ( g ) k z m ( g ) 其中，七指曲面的亏格 因为一个图g 在任意曲面上至少有一个面，根据e u l e r 公式，可以得到图g 的 最大亏格有如下上界： 协( g ) 【生笋j 这里，p ( g ) = l e ( g ) i i v ( c ) i + 1 称为图g 的罔秩数 若图g 满足9 m ( g ) = i 壁譬l ，则称g 是上可嵌入的设围g 的圈秩数为偶数或 奇数，则g 在曲面s 上是上可嵌入的，当且仅当存在一个g 在s 上的嵌入有一个或 两个面关于图的上可嵌入性，j u n g e r m a n 和x u o n g 得出了自己判定条件 设图g 有一个支撑树t ，称支撑树t 为图g 的一个分裂树，若g e ( t ) 的连通 分支至多有一个含有奇数条边明显，如果g e ( t ) 是连通的，n t 为一个分裂 树下面给出上可嵌入的图的一个特性 定理1 4 2 j u n g e r m a n x t l d 叼定理【4 】 一个图g 是上可嵌入的当且仅当g 有一个分裂树 5 北京交通大学硕士学位论文 第一章绪论 关于图的最大亏格有两个主要的基本定理一个是x 札伽提出的计算最大亏 格的理论，另一个是n e b e s k l 7 得到的 设g 为罔，x 为g 的一个边子集，c x 表示从g 中去掉x 中的所有边得到的 图设r 为图g 的一棵生成树，g e ( t ) 的一个连通分支k 称为g 的关于丁的奇边分 支，若果k 的边数为奇数；否则k 称为偶边分支记号f ( g ，t ) 表示g e ( t ) 的所有 奇边分支数称d g ) = m i ( g ，t ) 为g 的b e 饿亏数，这里m i n 取遍g 的所有生成 树t 易知，p ( g ) 与( g 1 同奇同偶x u o n g 给出了一个图g 是上可嵌入的充分必要 条件及其最大亏格由卢( g ) 和( g ) 所表达的一个公式 定理1 4 3 x “m 9 【4 】 设g 为图，则 ) m ( g ) = ( 卢( g ) 一( g ) ) 功g 是上可嵌入的当且仅当( g ) 1 由上述定理知图的最大亏格由圈秩数芦( 研和b e t 巧亏数d a ) 确定，由于移( g ) 决 定于g 的边数和顶点数，所以p ( g ) 容易算出，这样确定图的最大亏格的关键足确 定图的f ( g ) 的大小e 6 e s 自口理论给出了一个计算方法 定理1 4 4 n e b e s k o 定理【5 】 设g 为一个图，a e ( g ) 为g 的一个边子集，c ( g a ) 表示g a 的所有连通分 支数；6 ( g a ) 表示具有圈秩数为奇数的g 的所有连通分支数删 f ( g ) = m a z c ( g a ) + b ( a a ) 一i a l 一1 ) 这里的m a z 是取遍g 的所有的边子集a 黄元秋【6 】通过e 6 e s 哲理论得到一个更富有图信息的( g ) 表达式，此结果展 现出的是图的一个特征结构 设f 1 ，尼，最为图g 的k 个不同子图 2 ) ，记号岛( 日，尼，足) 表示g 中 两端点分别在某两个b 和最0 t ，1ss ，t 七) 中的所有边 定理1 4 5 设g 为图若f ( g ) l 则存在g 的边子集a 具有下列性质： 1 ) c ( g a ) 22 ，且对g a 的任意连通分支f ，有p ( ，) = l ( m o d 2 ) ； 2 1 对g a 的任意连通分支只跟g 的一个点导出子图j 3 ) 对g a 的女个不同连通分支只，易，足 2 ) ，i 点g ( f l ，易，风) i 2 k 一3 ；特别地，当七= 2 时，l 岛r ( f l ，如) l l i 4 ) f ( g ) = 2 c ( g a ) 一i a i 一1 6 北京交通大学硕士学位论文第一章绪论 上述定理的条件为( g ) 1 ，根据x u o n g 的理论，可知图g 为一非上可嵌入 图此定理从上可嵌入性的对立面揭示出图为非上可嵌入所具有的结构特征刑用 反证法，根据此定理并利用图的特征来确定图是否为上可嵌入的，是一个常用的 方法下面为该定理的一个推论，它在证明图的上可嵌入性方面也是极为有用的 推论1 4 6 设图g 为七一连通( 七1 ) ，a 为图g 的一边子集 1 ) 对g a 的任意连通分支f ，则i e ( a ，f ) i k ；e ( a ，f ) 表示一个端点属于f ，另 一个端点不属于f 的边集 2 ) 川= ；i e ( g ，f ) i f 这里求和取遍g a 的所有连通分支f 7 北京交通大学硕士学位论文 第二章最大亏格与图的参数 第二章最大亏格与图的参数 图的最大亏格是刻划图在某个定向曲面上是否2 胞腔嵌入的一个特征参数，对 这一参数的研究是拓扑图论中的主要问题之一，而确定一类图的上可嵌入性问题 本身就是确定图的最大亏格问题结合图的一个或多个参数，许多文献都给出了若 干上可嵌入的图类或最大亏格的下界，下面先介绍目前的有关这方面的若干结果， 第二节将介绍一个推广的结果 1 已有结果 从图的参数来研究图的最大亏格是解决该问题的一个很好的方法，这样得到 的各种图类的最大亏格为以后研究一般图类的最大亏格提供了好的研究基础图 的参数主要有连通度，直径，围长，割点，嵌入的面的度数，着色数，正则性，2 因 子等，这些参数都被用于最大亏格的求值中 最大亏格与连通度 定理2 1 1 f 2 0 1 设图g ，每个点的度数至少为舅后为其连通度，则g 的最大亏 裆1 】l f ( g ) 的下界如表2 1 j 所示 k 简单图非简单图 ( z ( g ) + 2 ) 4 ( f l ( g ) 3 ) 口 2 ( 卢( g ) + 2 ) 3 ( f l ( g ) 3 ，5 ) 了 ( z ( a ) + 2 ) 3 ( 3 ( g ) 3 ，5 )( z ( g ) + 2 ) 3 ( f l ( g ) 3 ，5 ) 4 3 ( g ) 2z ( g ) 2 袁2 1 上述事实表明4 边连通的图均为上可嵌入的，即最大亏格为l 壁孕i 根据这一事 实，在求解最大亏格时，可将图分为边连通度为1 ，2 ，3 三类来计算彳醍多最大亏格 的求解也是这样做的 最大亏格与顶点度数 图g 的一个2 因子是指g 的一个2 正则支撑子图显然，2 一因子中的每个连通分 支是一个圈若f 为图g 的一个磐因子且f 中的每个圈的长度均为k ，则称f 为g 的 一个k 一边形2 - 因子 定理2 1 2 2 5 1 设g 为有限无向的连通图，对任意 y ( g ) ，记如( 口) 毒k ( m o d a ) ，则 下表中列的图类是上可嵌入的 8 北京交通大学硕士学位论文第二章最大亏格与图的参数 椭值 ”z 一边形乒因子”条件 连通性条件 扫 有 琏通( 且无环) j 有琏通 2 无无 3有无 表2 1 2 最大亏格与割点 一个陶g 中长度为k 的圈，称之为融瑟 定理2 1 3 【2 1 】设g 为图且g 的每一条边属于一个争囤若g 中最多舍有两个割点， 则f ( g ) 1 ，即g 是上可嵌入的 定理2 1 4 2 1 】设g 为图且g 的每一条边属于一个3 圈若七( g ) 2 ，则( g ) k ( g ) 一1 ，这里七( g ) 表示g 中割点个数 最大亏格与面度 g 为一有限无向连通图，设陶g 为嵌入在曲面后的面为，的度是指这个面的 边界占用的边的条数( 重复得边记数两次) 定理2 1 5 【2 2 1 设简单连通图g 嵌入在某个( 定向或不定向) 曲面s 上，则 卵) s1 + f 掣j f e f , j fj 7 。 f 为g 在曲面嵌入后的所有面的集合 从上述定理容易得到，若简单连通图g 嵌入在某个曲面s 上，使得每个面的度 不超过5 ，则该图是上可嵌入的 最大亏格与着色数 对于一个连通或不连通图g ，g 的点着色数，记为x ( g ) ，是指最小的整数七使 得g 的每个定点能用自种不同的颜色染色且任意两个相邻的顶点染不同的颜色g 表 示为一个图g 的补图 定理2 1 6 【2 4 设g 为七一边连通图，= 1 ，2 ，3 ，k g 为g 的补图( 不一定连通) ，若x ( g ) = n ，则有 = i l | i 女l 一 俨嘲 。 z 茁 n n n 僦 啪 ，-_，、_、 2 ，下面将论证集合是一个空集假设该集合不是空集令g y i 是该集合中具有 最小阶的陶g 是一个亏图，令a 是一个最小的n e b e s k 9 ，根据引理2 2 1 ( n ) ，g - a 的 每一个连通分支有奇的b e t t i 数，所以g a 的每个连通分支必然是一个四边形否 则，就会存在一个图g ，使得i v ( ) i i v ( a ) 1 让已定义为g a 的连通分支，对 应于g a 中的顶点。 根据引理2 2 3 ，令z a v ( g ) ，且有2si e ( z a ，a ) i 3 令d o = 钰) ，d i = n ( z a ) ，d 2 = v ( a a ) 一n ( z a ) 如果z y ( g ) ，且满足m i n d ( x ，z ) l z y ( e 。) ) = 后， 则称x 为距离k 的点定义e ( q ，d j ) = x a y a e ( g a ) i x a d ；，y a d s ，其 中0 i ，j 2 下面的定义是为以后论证作准备 a l = z a y e ( d 2 ，d 1 ) l 存在毛。中的一个距离l 的点关联于瓦。中的一个距 离2 的点或者乃。中一个距离2 的点关联于已。中的一个距离3 的点和死。中的一个距 离1 的点，a d 1 一 孰) a 2 = z y a e ( d 2 ，d 2 ) ix a 不关联a 1 的任意边，y a 关联a 1 的一条边，乃包 含一个点既关联于瓦。中的一个点也关联于死。中的一个点， d 1 ) u z a y a e ( d 2 ，d 2 ) i z a 不关联于a 1 的任何一条边，y a 关联于a 1 的至少两条边 a 3 = z 4 y a e ( d l ，d 1 ) i 存在死。中的一个距离2 的点关联于弓。中一个距离1 的 点 根据上述e ( g a ) 的边子集，基于图g 现定义一个有向图g a ( i ) v ( g , ) = y ( g _ ) ； ( 托) 如果。 y a = ( u ：la ) u ( d 1 ，d o ) ，就添加从点纵到点如的两条弧 ( i i i ) 如果z 讹e ( g a ) 一f ，就添加0 ，讹) 和b a ， ) 两条弧 通过有向图g j 的定义，容易得到 北京交通大学硕士学位论文 第二章最大亏格与图的参数 衄( z ) = d e 9 一( z a ) ， x a v ( g a ) “y ( 玄) 其中，d e g - ( z a ) 表示有向图否j 中点z a 的入度因此有向图否j 顶点的入度的总 和为2 q ( o a ) 计算一下有向图g j 的入度的总和，令z 是y ( g j ) 中的任意一个顶点 ( 1 ) 当顶点x a d o 时，显然有d e g - ( z ) = 0 ( 2 ) 当顶点x a d 2 时 ( i ) 顶点。j 4 关联a 2 的边，但是不关联a 1 的任何一条边 情况1 ：顶点x a i l i 少关联a 2 的两条边，贝j d e g 一( 。d ) 24 情况2 ：顶点z 关联a 2 的一条边e ，令z l y l 是e ( g ) 的一条边对应于边e 根据疋是 一个四边形和2 茎i e ( z a ，a ) i 3 ，那么存在z 1 y ( 正。) r d e g ( z i ) = 2 在罔g 中， d ( z 1 ，z 1 ) = 4 令y ( 已。) = 缸1 ，钇，x 3 ，。4 ，在瓦。中，顶点z 2 必定关联e ( g a ) 一e 的 一条边使得d ( z 2 ，2 1 ) 4 ( 事实上，d 2 ，z 1 ) = 4 ) 。同样对于顶点z 3 和x 4 因此， d e g - ( 。 ) 4 ( i i ) 顶点x a 不关联a 2ua 1 的任何一条边 令矿( 疋。) = z 1 ，x 2 ，x 3 ，舶) 在咒。中，顶点z 必需关联e ( g ) 一e 7 中的一条边 使得d ( 。l ，旬) s4 ( 事实上，d ( 。2 ，z 1 ) 一4 ) ，同样对于顶点x 2 ，z 3 和z 4 因此d 印一( z a ) 4 ( i i i ) 顶点x a 不关联a 2 中的任何一条边，但是关联a 。中的边 情况l ：顶点x a 至少关联a 1 中的两条边，j i i u d e g 一( 。a ) 4 情况2 ：顶点x a 关联a l 中的一条边e ，令。1 y l 是e ( g ) 中的一条边对应于边e 令 y ( e ) = 奶，x 2 ，x 3 ，z 4 ) 且d ( z 1 ，z 1 ) 3 在b 。中，设z 3 不关联z 1 ，那么如必然关 联e ( g ) 中的一条边，设这条边为e 那么e 7 e ( g a ) 一e 贡献了一个入度因 此，d e g 一( x a ) 23 ( 事实上，当d e g 一( z ) = 3 时，e ，e ( d 2 ，d 1 ) ) ( i 口) 顶点z 既关联a 2 中的边也关联a l 中的边 情况1 ：顶点。 至少关联a l 中的两条边，n d e g 一( z ) 4 情况2 ：顶点z 关联a 1 中的一条边e 令茁1 y l 为e ( g ) 中的一条边对应于边e 令 y ( 瓦。) = 奶，现，x 3 ，缸 且d ( z 1 ，z 1 ) 23 在疋。中，设不关联z l ，那么铂必然关 联e ( g r a ) 的一条边设该边为e ，那么e a 2 或者e e ( g a ) 一e 对于前者，e 必 然为顶点名 贡献两个入度，对于后者，e 贡献一个入度因此，d e g - ( z a ) 3 ( 事实 上，当d e 9 一( z a ) = 3 时，e e ( d 2 ，d 1 ) ) 北京交通大学硕士学位论文第二章最大亏格与图的参数 所以，对于顶点x a d 2 ，有d e g 一( x a ) 3 令m = x a d z l d e g 一( x a ) = 3 ) 可以得到 d e g 一( z a ) 4 i d o l i m i ( 1 ) o e d 2 ( 3 ) 当顶点o a d 1 时 根据有向图g j 的定义，连接d o 和d l 的边贡献两个入度为顶点茹 令z 1 y 1 是 e ( g ) 中的一条边对应于这条边( 1 e ( z 。) ) 令y ( b 。) = z l ，x 2 ，x 3 ，钆) 在已。中， 设黝不关联z l ，在e 中，存在z 2 y ( 。) 使得，如果d ( z 3 ，z 2 ) 4 ，当。3 不是 通过勉或z 4 连接z 2 时，x 3 必然关联e ( g a ) 中的一条边设该边为e 由e e ( g ) 一 e j l ! i d e g ( x a ) 3 当茹3 是通过x 2 或3 1 4 连接勿时，z 2 或姐关联e ( g a ) 中的一条边设 该边为e 由e e ( g a ) 一e 或e a 3 ，e 贡献至少两个入度因此，d e g ( x a ) 3 所以，对于所有z a d 1 ，有 咖一( z a ) 3 t d - f + m ( 2 ) z a e d t 通过( 1 ) 式和( 2 ) 式，得到 4 d 2 i i m i + 3 d 1 i + 1 m = 卸( g a ) 一l d l i 一4 4 p ( g a ) 一7 根据引理2 2 2 ，有( g ) = 2 p ( g a ) 一1 一q ( a a ) 2 ，矛盾所以定理得证 口 对于该定理中，为了能够说明得到的上界是最好的，下面构造了无限的一类 图，且满足定理得条件，其中点m 到点n 有偶数个长为2 的路，不难计算出该图的亏 数等于2 ，见图2 2 1 1 4 z 凹 d 鄱 = g 北京交通大学硕士学位论文第二章最大亏格与图的参数 m 3 构造上可嵌入的图 图2 2 1 上文中叙述了图的基本参数与最大亏格的结合，此外对于图的最大亏格，有 一个新的途径就是通过删除或增加顶点和边来研究图的最大亏格或上可嵌入性 的变化 设g 足一个有限无向的简单连通图，记号e i ( g ) 表示g 的边子集：e 面( g ) = e e ( g ) l g e 是连通的，日- m ( a e ) = 7 m ( g ) ) 对于图g ，若e m ( g ) o ，则 称g 足7 m ( g ) 一可约的，否则称g 是7 m ( g ) 一不可约的黄元秋在图的可约性和不可 约性【2 7 】方面给出了一些定理 引理2 3 1 设e 为图g 的任意边，若g e 是连通的，则f ( g ) 一l f ( g e ) ( g ) + 1 ，即f ( g e ) = ( g ) 一1 或者( g e ) = ( g ) + 1 定理2 3 2 设图g 是，y 肘( g ) 一不可约的，当且仅当( g ) = 0 定理2 3 3 设图g 是伽( g ) 一可约的，且满足e 矗( g ) = e ( g ) 口，则g 必是孕边 连通的，且f ( g ) = 1 ，即g 是上可嵌入的 下面我们通过向图中加入一个特殊的顶点，使得图变成一个上可嵌入的图 定义2 3 4 对于任意有限的无向图g = ( k e ) ，给图g 添加一个8 点，表示增加一 个新的顶点8 ，对于