【摘 要】
：
本文主要研究几类特殊图的交叉数问题.一个图G是平面图当且仅当它的交叉数为0.因此交叉数是图的一个很重要的拓扑性质.图的交叉数问题是图论研究领域中的一个重要方面.相对于
论文部分内容阅读
本文主要研究几类特殊图的交叉数问题.一个图G是平面图当且仅当它的交叉数为0.因此交叉数是图的一个很重要的拓扑性质.图的交叉数问题是图论研究领域中的一个重要方面.相对于其它较为成熟的图的研究理论而言,图的交叉数的研究显得不是特别系统.至于其原因,主要在两个方面：一方面是确定一个图的交叉数是很困难的.就这类问题的复杂度而言,Garey和Johnson在文献中证明了确定任意一个图的交叉数问题是NP-完备的.另一方面是人们在研究这类问题时,往往很大程度上依赖于研究对象自身的特殊性结构,故很多方法并不能推广到一般性情形,这样导致了这方面的研究,很难形成系统性的方法。
本文基于众多的图的交叉数的研究结果,对这方面的研究和进展作了一次整合,集中关注循环图的交叉数,并得到了一些结果,具体有如下：
(1)循环图C(3m,m)的交叉数为m(m≥3)；(2)循环图C(16,4)的交叉数为8。
其他文献
蚁群算法是通过模拟真实蚁群之间相互作用的行为而提出的一种随机搜索算法,与遗传算法、粒子群算法、模拟退火算法、禁忌算法等启发式算法一样是应用于求解组合优化问题的启
本文研究了二维奇摄动系统的第一类型边值问题,对该问题具有纯边界层和阶梯状空间对照结构的情形分别做了讨论。 第一章给出一些关于奇摄动的基本概念和前人的工作,然后简
本论文研究两台同类机极大化机器最小负载的排序问题。模型要求在两台速度之比为q的机器上加工工件,并已知工件加工时不可中断,目标是使负载最小的机器其加工时间最大化。本
非线性布尔函数广泛应用于对称密码系统中,它在整个系统的安全性方面扮演着重要角色.-个n元布尔函数,(x1,x2,…,xn)可看作二元域F2上的一个多元多项式,为了有效抵抗密码系统
在这篇文章中,我们构造了一种Level Set模型对生物大分子的分子场进行特征提取和分析。对于3维大分子的分子场上的体数据,我们定义了一个新颖的跟踪几何活动轮廓线的变分方程
Hausdorff测度与维数是分形几何中两个基本且重要的概念。一般而言,计算一个分形集的Hausdorff测度与Hausdorff维数是非常困难的,尤其是Hausdorff测度的计算。对于满足开集条
三角差集在数据通信方面有很多应用,还可以用于很多编码的构造。完美差族可以看作一类最优的三角差集。Ge,Ling与Miao利用差族来构造雷达阵列[8]。通过对三角差集、差族、还
吕家坨矿业公司使用掘进机已有10余年,使用过EBZ-75型(水采专用)、EBZ-90型、EBH-132型、S150J型4种掘进机。EBZ-75型掘进机是适用我公司早期水采掘进巷道,EBZ-90型、EBH-132
ECT B样条曲线是基于典范ECT组在每个节点处由一个关联矩阵按几何连续连接而产生的，若每个关联矩阵都是非奇异、下三角、全正的矩阵，则存在非负的、具有最小支撑基和归一的ECT
由于红外线具有出色的夜视功能.能穿透一定浓度的烟、雾、霾等介质并且对温差具有极强的敏感性,因此近年来在军事国防、遥感监测、公共卫生防疫等方面得到了广泛的应用。但在