【摘 要】
:
设V(G)和E(G)分别是图G的点集和边集,图画在平面上是指将图的顶点集中各点映射到平面上的不同的点,然后将边集的每一条边(u, v)映射为平面上的一条连续的线上使得该线的端点恰
【机 构】
:
中央民族大学数学系,北京100081北京交通大学数学系,北京100081北京交通大学数学系,北京100081北京理工大学计算机科学技术学院,北京100081
论文部分内容阅读
设V(G)和E(G)分别是图G的点集和边集,图画在平面上是指将图的顶点集中各点映射到平面上的不同的点,然后将边集的每一条边(u, v)映射为平面上的一条连续的线上使得该线的端点恰好是顶点u和v的象。如果画法满足以下几条:(1)任何两条边最多相交一次;(2)边自身不相交;(3)有相同端点的两条边不相交:(4)没有三条边交于同一个点;(5)任何一边不过除它端点之外的顶点,则称该画法为图G的好画法。图G的交叉数是指在G的所有好的画法中边交叉点最少的个数,记为cr(G)。满足交叉点个数最少的画法称为图G的最优画法。本文运用计算边交叉的次数和归纳的方法,得出了循环图C(3m.m)m≥3的交叉数是m。
其他文献
土地价格的监测、分析与预测对控制土地的供求关系、调节土地的供求矛盾都有十分重要的意义.然而由于影响地价的因素较多,地价预测模型的研究显得十分必要.本文根据地价变化
本文为确定组合预测中的权重,建立了以平均误差平方和(MSE,the mean square error)为目标函数值的非线性规划,然后利用EXCEL计算权重,据此产生预测值.计算发现,这种方法得到
通过一个互补函数以及光滑近似法的思想,把互补约束均衡问题转化为一非线性光滑规划问题,该非线性光滑规划问题通过SQP算法求解.在一些适当的假设条件下,本文不仅得到了算法
海洋移动目标成像侦察任务是在用户需求和卫星及星载遥感器约束条件下,合理分配成像侦察卫星及星载遥感器资源.本文对海洋移动目标成像侦察任务进行了分解,构建了移动目标潜
描述了战区联勤军事物流运输保障问题,建立了车辆路径优化问题的模型.VRP问题是NP完全问题,阐明了遗传算法是一种有效的全局随机优化方法,并将遗传算法用于该问题的研究中.针
在部队摩托化行军中,由于机械车辆数量多,类型复杂,对道路的依赖性较大,当遇有桥梁、隧道和狭窄路段时,这些地方容易造成车辆拥挤,以至单位时间内通过的车辆减少.在稍纵即逝
对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数.本文得到了星与扇联图的全色数和点
本文讨论带仓储约束的准时排序问题1|s,inver|Cmax.证明了此问题是强NP-难的,并且证明对于这个问题不存在竞争比小于2的在线算法.当公共交货期满足周期性时,排序问题1|(s),in
本文考虑的二次最小二乘问题是一类特殊的非线性最小二乘问题.这类问题在通讯科学、计算生物学等交叉学科中都有广泛的应用.在实际问题中,当问题规模很大的时候.随机多初始点
本文考虑CDT子问题,艾和张基于SDP理论给出了强对偶性条件和证明.本文则给出了仅仅基于数学分析基础的强对偶性条件的一个新证明.该证明更加简单并且更好理解,为在此基础上提