文档介绍：谨以此论文献给我的导师及家人
------------------孟盼盼
极小非平面图的性质及边传递图的路径问题
学位论文答辩日期:
指导教师签字:
答辩委员会成员签字:
ii
独创声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的
研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其
他人已经发表或撰写过的研究成果, 也不包含未获得
(注:如没有其他需要特别声明的,本栏可空)或其他教育机构的学位或证书使
用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明
确的说明并表示谢意。
学位论文作者签名: 签字日期: 年月日
---------------------------------------------------------------------
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定,有权保留并
向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人
授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用
影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息
研究所将本学位论文收录到《中国学位论文全文数据库》,并通过网络向社会公
众提供信息服务。(保密的学位论文在解密后适用本授权书)
学位论文作者签名: 导师签字:
签字日期: 年月日签字日期: 年月日
iii
极小非平面图的性质及边传递图的路径问题
摘要
极小非平面图(即 Kuratowski 子图)是任一真子图均为平面图的非平面图,
它是一个临界图,自身具有非平面图的特点,而它的任一真子图又满足平面图的
所有特征。探讨极小非平面图的性质对于研究非平面图和平面图的特征有很大的
帮助。边传递图建立在群理论的基础上,它的任意两条边 e1 、e2 之间存在一个同
构映射 Aut() G ,使得()ee12.Caley 图是一类重要的传递图,且大多数Caley
图既有边传递性又有点传递性,使得它在网络问题的研究中有广泛的应用。
等介绍了 15 类 Caley 图。Caley 图的路径问题是图论的一个
重要研究方向。
本文的主要工作有:
1. 介绍了非平面图 3 个典型的表示指标——交叉数、 Kuratowski 子图和临
界边,概述了图的连通性、强正则图及Caley 图的研究现状;
2. 利用 Euler 公式,给出了极小非平面图的边数、顶点数以及围长之间的关
系表达式;
3. 利用 Brooks 定理,从色临界图的角度讨论了极小非平面图的染色性质;
4. 非平面图中必含有 Kuratowski 子图,但对给定非平面图的任意边,则不一
定属于其 Kuratowski 子图。利用 Frank Harary 的方法构造了一类特殊的非平面
图,使得它的任意一条边都属于其 Kuratowski 子图;
5. 利用极小非平面图和桥的性质,证明了非平面图与边传递图和正则图的两
个关系定理:
(1)交叉数为 1 的边传递图是极小非平面图;
(2) r / 2( 6) 度正则图是非平面图;
6. 利用 Menger 定理和Whitney 定理的推广形式,研究了边传递图中不相交的
路的条数,并给出了 MBn 的最短路的长度及算法。
关键词:极小非平面图;非平面图; Caley 图;边传递图; MBn
iv
On the Properties of Minimal Non-Planar Graphs and Routing
Problems in Edge-Transitive Graphs
Abstract
Minimal non-planar graphs, which are also called Kuratowski subgraphs, are
non-planar graphs with their subgraphs are planar. Obviously,minimal non-planar
graph is one kind of critical graphs, because it meets all the properties of non-planar
graphs,