论文部分内容阅读
图的交叉数是图的一个重要概念,是与非平面图复杂性、色数、亏格以及其他性质息息相关的一个重要参数。它起源于二战期间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。
第四章是对本文的总结及对未来工作的展望。