关于图的可嵌入性的若干结果

《关于图的可嵌入性的若干结果》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、吕长青硕士学位论文答辩委员会名单姓名职称单位备注洪渊教授华东师范大学主席董纯飞教授华东师范大学束金龙副教授华东师范大学戴浩晖讲师华东师范大学秘书学位论文独创性声明本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果．据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名；翌L墼盔日期：五盟互鎏玉目勰日学位论文使用授权声明本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版．有权

2、将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅．有权将学位论文的内容编入有关数据库进行检索．有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。学位论文作者签名：日期易乞畜2塑盔纽互国勰日导师签名；El期碣a垃幽丝生壬唆第一章概述图论是组合数学的一个主要组成部分，近几十年里，它已经发展成数学的一个重要分支。由于图论的本身魅力和其在信息社会中一些学科领域诸如计算机，运筹学，系统工程以及物理学，电子学，生物学，化学等方面的广泛应用，因此，越来越受到科学界尤其是数学界的重视和关注。由于像组合数学，代数学，拓扑学以及概率方法的结合，现代图论除了传统

3、的研究领域外已发展为包括代数图论，拓扑图论，以及随机图论等分支在内的多个新的领域，促进了图论发展．图的嵌入性理论及图的亏格是拓扑图论的一个重要的问题。自从Nordhaus(文献【26])等引入图的最大亏格概念以来，图的最大亏格以及图的上可嵌入性引起了广泛关注。§1．1基本概念设图G=(VE)，其中V为顶点集，V=v(c)={721，V2，⋯，‰)，IVI=u称为图G的阶数，E为边集，E=E(C)={e1，e”．．，e。}，IE

4、=E为图G的边数．设(u，V)∈E，则称顶点u与u相邻接，记为U—u，否则不相邻，记为“≠u。若U和"是边e的两个端点(记为e=(Ⅱ，")=¨口)，则

5、称“(")与e关联．与"关联的边数称为"的度(次)，记作deg(v)=d(v)。图G中最大、最小的度数分别记为A(c)和d(G)。若△(G)=6(G)，则称图G为正则图．记∥(G)=E一"+1称为图G的Betti数。如果一条边有相同的顶点，则称这条边为环，如果有两条边有相同的顶点则称这两条边为重边，没有环和重边的图称为简单图．如无特别说明，本文所研究均为有限无向简单图G的一条途径是指一个有限非空序列W="oe。u。e2⋯e≈‰，它的项交替地为顶点和边，使得对1≤{Sk，岛的端点是VH和w。；其中，％和讯分别称为∥的起点和终点，而V-，"。，⋯，‰一，称为缈的内部顶点．整数k称

6、为Ⅳ的长．若途径w的边e。，e。，⋯，ek互不相同，则W称为迹。称一条途径是闭的，如果它有正的长且起点和终点相同．若一条闭迹的起点和内部顶点互不相同。则它称为圈．一个图的最小的圈的长称为这个图的围长。若途径W的边"o，u一．，强互不相同，则W称为路。包含G的每个顶点的路称为G的Hamilton路}类似地，G的Hamilton圈是指包含G的每个顶点的圈。第一章概述2G的两个顶点Ⅱ和u称为连通的，如果在G中存在从“到"的路。连通是顶点集v(v)上的一个等价关系。于是存在v(c)的一个分类，把v(a)分成非空子集K，K，⋯，K，使得两个顶点“和”是连通的当且仅当它们属于同一个子集K

7、。子图G[H】，G[％]，⋯，G[K】称为G的连通分支。若G只有一个分支，则称G是连通的；否则，称G是不连通的。若v(c)的子集y’使得v(u)一V’不连通，则y’称为v(c)顶点割。k顶点割是指有k个元素的顶点割。若G至少有一对相异的不相邻顶点，则G所具有的k顶点割中最小的≈，称为G的连通度，记为K(G)。若K(G)≥k，则称G为k连通的．对V(C)的子集s和s’，用暇∥]表示一个端点在S中，另一个端点在s’中的所有边的集合．所谓G的边割是指形为旧s’]的E(G)的子集，其中s是v(c)的非空真子集。一个k边割是指有k个元素的边割。若G是非平凡的，G的所有k边割中最小的k，

8、称为G的边连通度，记为K’(G)。若一’(G)≥k，则称G为k边连通的．称图耳为图G的子图，如果V(H)∈V(G)，甄胃)∈E(G)，并且{PH是妒。上的限制。G的生成子图是指满足V(H)=v(v)的子图日．假如y7是y的一个非空子集．以V’为顶点集，以两端点均在y’中的边的全体为边集所组成的子图，称为G的由y’导出的子图，记为G【y‘]。连通的无圈图称为树。G的生成树是指G的生成子图，它同时又是树。此外还有些未给出的术语与记号将在文中给出或参阅文献[3，21]。§1．2圉的可嵌入与图的亏格曲面是一个紧