图的交叉数有关问题研究

来源 :湖南师范大学 | 被引量 : 5次 | 上传用户:truby
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的交叉数问题是在近代图论中发展起来的一个重要概念,是表征一个图的非平面性的一个重要参数,是拓扑图论中的前沿难题.它起源于上世纪五十年代Turan在砖厂碰到的一个实际应用问题(Tu-rans Brickyard Problem)逐渐发展成为图论学科中非常活跃的一个分支,其理论在电路板设计,草图识别与重画以及生物工程DNA的图示等领域有广阔的应用,因而吸引着国内外许多学者的关注.它研究的主要是如何把一个图画在平面上或曲面上,使其产生的交叉数目最少,通常采用的是纯数学方法的证明.一般地,确定图的交叉数是十分困难的,事实上,Garey和Johnson已经证明了确定一般图的交叉数是一个NP-完全问题.目前,能确定交叉数的图类很少.确定图类的交叉数主要集中在一些特殊图类上,如完全图Kn,完全2-部图Km,n,完全3-部图K1,m,n,简单的图之间的笛卡尔积,循环图等.   本文尝试应用并创新某些新的方法,主要研究了如广义Petersen图.联图.笛卡尔积图等一些典型图类的交叉数.其主要结构如下:   一.交代了图的交叉数的起源、研究背景、研究工作的理论与实际意义,以及较为详细介绍了目前交叉数的研究在国内外的发展动态   二.给出了图的基本概念及本文常要用到的引理和性质.   三.研究了与联图有关的图的交叉数,主要研究了一个典型有两条悬挂边的六阶图与路和圈的联图的交叉数.   四.证明了一个特殊六阶图与路和圈的联图的交叉数..   五.探讨了与轮图有关的交叉数问题,在假定著名的Zarankiewicz猜想对m=7的情形成立的基础上,确定了6-轮W6与路Pn的联图的交叉数和6-轮W6与星图Sn的笛卡尔积图的交叉数.   六.讨论了一类Petensen图的交叉数,主要确定了当κ≥3时,广义Petensen图P[3κ-1,κ]交叉数的上界和下界.   七.给出了本文的总结和对未来工作的展望.
其他文献
本文隶属于Torsion Theory领域,该领域是近10年来在国际上发展非常迅速的一个代数学分支.在这一些相关的文章中我们研究了三角范畴中的挠偶以及它的构成.并且通过介绍刚性子范
随着智能手机等数码产品的迅速普及,图像已成为人们传递信息的重要媒介。然而在现实生活中要捕获到清晰的图像是一个非常困难的任务,这是因为相机的抖动或者场景中物体的运动使
有关中国A股市场上市公司不分红、少分红的争议由来已久,近年来,上市公司整体分红水平略有提高,但“铁公鸡”依然不少,中小股东的权益未能得到有效保护。最近,证监会将再次改
离散动力系统广泛的用来描述自然科学,社会科学,工程技术等领域中出现的数学模型。相应的超空间上诱导的动力系统是指以原系统中的非空闭子集为点赋予某种度量或者拓扑所生成
摘 要:灌云县农村固体废弃物主要构成为农作物秸秆、畜禽粪便和生活垃圾,具有产生量大、种类多、污染重和收集困难等特点,这已经影响到农村的可持续发展。本文根据灌云县农村固体废弃物产生的实际情况,从农村产业结构调整、生态农业发展等方面探讨了农村固体废弃物治理。  关键词:农村固体废弃物 生态农业 产业结构调整 环境管理  灌云县拥有耕地面积128.34万亩,治理农村生态环境对于促进种植业的健康发展非常重
《热土》虽有很强的形式美感,但它不是依赖于形式美感而获得艺术的历史价值,它所展现的更是一种“思想”的力量。《热土》的图形基底,是人所熟知的中国地图和长城。以中国地
Dade基是构造有限群的不变式环的参数系的一种工具,即Dade基的轨道的顶端陈氏类构成了不变式环的一组参数系.当域是无限域时,群作用下的表示空间一定存在Dade基(见文献[1]).本
图论的研究开始于200多年前。关于图论的第一篇论文是Euler于1736年发表的。他用图的方法解决了哥尼斯堡Konigsberg七桥问题。自从二十世纪六十年代以来,图论在科学界非常活跃