Mycielski图及最优1-平面图的交叉数的研究

来源 :北京交通大学 | 被引量 : 1次 | 上传用户:xxzzxx_100
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的交叉数是图的一个重要概念,是与非平面图复杂性、色数、亏格以及其他性质息息相关的一个重要参数。它起源于二战期间Paul Turán在砖厂碰到的一个实际难题,逐渐发展为图论学科中非常活跃的一个分支,吸引着国内外许多学者的关注。交叉数的研究发展至今,已经成为图论中非常重要的研究热点。由于求一般图的交叉数问题是一个NP-问题,因此到目前为止只对少数一些特殊图类有相关结果。   本文主要研究了Mycielski图的交叉数,在已有研究成果Mycielski图的交叉数为0和0的充要条件下得到了Mycielski图的交叉数为2的充要条件,并随之得到了Mycielski图的一些新性质。此外,我们还研究并证明了一类非平而图--最优1-平面图的交叉数。全文共分为4个章节。   第一章中较为详细地交代了交叉数的起源,理论与实际意义。介绍了目前交叉数在国内外的发展动态。同时还简要介绍了交叉数的相关定义和符号及本文的基本内容。   第二章中着重研究了Mycielski图的交叉数问题。第一节中证明了Mycielski图的一些新性质。第二节中得到了Mycielski图的交叉数为2的充要条件。   第三章中着重研究了一类非平面图-最优1-平面图的交叉数并且解决了最优1-平面图交叉数问题,最终得到结论:最优1-平面图G(V,E)的交叉数为cr(G)=|V|-2。   第四章是对本文的总结及对未来工作的展望。
其他文献
Besov和Triebel是两类重要的函数空间,形成于20世纪60-80年代,近年来在PDE领域得到了广泛的应用。这两类空间是二进制分解和函数空间q(Lp),Lp(q)相互结合的产物。很自然地,很多人
本文主要研究了满足函数方程I(x,I(x,y(x,I(x,y)=I(x,y)的连续D-蕴涵算子和由一致模生成的R-,S-,QL-蕴涵,同时基于它们给出了上述函数方程的解的刻画.   第一章,主要回顾了三角
模型未知试验和计算机仿真试验的设计与建模有许多方法,本文选择了四种不同类型的仿真模型,用三种试验设计方法,考虑了大小不同的试验方案,并选用四种建模方法进行比较,其中对于模
在大数据时代,高维数据广泛呈现在生物信息,金融经济和图像处理等领域,其共同特征之一是预测变量具有稀疏性.选择最相关的预测变量是高维数据分析的主要研究内容之一,具有极其重要
众所周知,绝对值方程组Ax-|x|=b的求解是NP难的,其中A∈Rn×n,b∈Rn为给定的数据,|x|表示的是对x∈Rn的每一个分量均取绝对值的向量.本文考虑求解绝对值方程组Ax-|x|=b的两种数值方
本论文旨在研究半环上半模的结构与性质,半模的基础结构是可换幺半群,且它的“系数”部分是半环,因此在性质上与环上模有着本质的区别,给出半模同态f:M—→N,kf=0是f为单同态的必要