给定面对的最小正则平面图

论文摘要

图论是应用数学理论的重要分支。图论的广泛应用,促进了它自身的发展。尤其是近几十年来,随着计算机技术的出现和进步,图论理论有了飞速的发展并取得了惊人的成绩。 本文所研究的具有给定围长的最小正则图称为笼,找笼问题是图论中的一个经典问题。关于找笼问题已经有了一些精确的结果。 Harary和Kovacs引进了给定围长对的笼的概念,即把具有给定奇数围长与偶数围长的最小正则图也称为笼。对于偶数围长为4及其它一些特殊情况,已经给出了精确结果。本文把问题局限于平面图来考虑,并且仅考虑奇偶面对而不是奇偶圈。 令G为一个平面图,ν,ω和ε为大于2的整数。如果ω和ε分别为图G的最小奇数面和偶数面,则称(ω,ε)为G的面对,并称G为一个(ω,ε)—图。如果G是一个ν—正则图,也就是G中的每个顶点的度均为ν,则称它为一个(ν,ω,ε)—图。具有最少顶点数的(ν,ω,ε)—图中的顶点数记作f(ν,ω,ε)。由欧拉公式,(ν,ω,ε)只能有(3,3,ε),(3,5,ε),(3,ω,4),(4,3,ε)和(5,3,ε)五种可能的情形。 Connie M. Campbell给出了关于(3,3,ε)与(3,ω,4)的结果,本文更正了其中关于(3,3,ε)的结果,并完成了对其余三种情形,也就是(3,5,ε),(4,3,ε)和(5,3,ε)的研究。 本文设计了生成具有较小顶点数的(ν,ω,ε)—图的算法,从而给出了f(ν,ω,ε)的上界,再利用欧拉公式,证明了f(ν,ω,ε)的下界,并最终给出了f(ν,ω,ε)的精确结果,从而完成了对给定面对的最小正则平面图问题的研究,从而为给定面对的最小正则平面图问题的研究画上了一个完美的句号。

论文目录

• 摘要
• Abstract
• 0 前言
• 1 基本概念
• 2 关于笼及其扩展问题的进展
• 2.1 笼的研究现状概述
• 2.2 对于给定围长对的正则图的问题
• 2.3 给定度集合的图和笼
• 2.4 对于给定面对的正则平面图的问题
• 2.5 本文的工作
• 3 对于f（3，3，ε）的研究
• 4 对于f（4，3，ε）的研究
• 5 对于f（5，3，ε）的研究
• 6 对于f（3，5，ε）的研究
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢
• 大连理工大学学位论文版权使用授权书