关于图的交叉数

来源 :北京交通大学 | 被引量 : 0次 | 上传用户:majianfeipubin
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的交叉数是将G画在平面上时交叉次数的最小值,记为cr(G)。其中画法满足: (1)任何两条边相交叉的边最多交叉一次; (2)边不能自身交叉(3)有相同端点的两条边不交叉; (4)没有3条边交叉于同一点。称含最小交叉数的画法为最优画法。一般而言,确定图的交叉数是一个完全NP-问题,给出给定图的交叉数的具体值是项非常困难的工作。对交叉数的研究主要集中在对完全图,n部图,广义Petersen图,循环图,笛卡尔积图的交叉数的计算上。目前知道交叉数的图类很少,其中知道交叉数的图类主要集中在简单图的特殊图与路,与星图,与圈,简单的特殊图之间的笛卡尔积图等。 本文共分两章。 第一章中综述了本篇文章主要要用的基本概念,以及前人给出的关于交叉数的已有结果。 第二章中给出了一些新的结果: 循环图C(11,4)和C(13,4)的交叉数。 两个笛卡尔积图的交叉数。 一个三部图的交叉数。
其他文献
本文就生态城市规划设计方面应该遵循的原则、要求,以及规划设计的内容和指标体系作了简要的阐述,并提出了保护自然生态环境的重要性。
期刊
本文共分四个部分。第一章简要叙述了SQP算法与SSLE算法的发展历史和概况,介绍了近期发展的一些新成果,考察了这些算法全局收敛性与局部超线性收敛性的条件,讨论了其中存在的问
不定复射影空间及其全实类空子流形是微分几何中一类重要的研究对象.本文以截面曲率为常数作为基本前提,考虑了不定复射影空间在特殊类型下其中的全实类空子流形,通过计算给出
学位
Markov过程是以俄国数学家A.A.Markov的名字命名的一种随机过程,它的应用范围极其广泛.不仅在数学其它分支和工程技术中有着广泛的应用,在社会科学中,如经济学、保险学、金融
”投资与消费”在金融数学甚至经济学中是一个最为重要的主题.最初的工作集中于动态最优投资与消费问题,可见于Merton发表于上世纪60年代末和70年代初的论文.在Merton的文章中
细胞神经网络(CNN)是一种实时、连续及并行运算的信息处理系统,它源于Hopfield的反馈神经网络和Neumann的细胞自动机。作为一类非线性动力系统,它具有复杂的动力学性质;同时,