停机位分配问题的顶点着色模型及算法

给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以"先到先服务"原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解.     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

基于数据手套的逼真虚拟手的实现

在基于头盔、数据手套的虚拟现实系统中虚拟手的实现效果十分重要,传统的虚拟手模型将手掌和各手指分割为多个刚体,当虚拟手运动时在刚体连接处产生重叠或裂缝,严重影响了沉浸感。在此根据虚拟手的运动特点对其进行整体建模,并快捷地对数据手套采集的原始关节数据进行校正,在可编程图形硬件上利用顶点混合算法将校正后的数据作用于虚拟手模型来产生皮肤变形,在满足实时性的同时提供了逼真的视觉效果。最后还通过搭建实验系统验证了所述方法的可行性。     

图Kn3的若干染色

利用穷举法和组合分析法讨论了图Kn3的邻强边染色和邻点可区别的全染色,通过构造具体染色得到了图Kn3的邻强边色数和邻点可区别的全色数。     

图m(G1(2n,1)*G2(2n,1))的优美性和奇强协调性

定义图m（G1（2n,1）＊G2（2n,1））的概念,证明它是优美图和奇强协调图,还证明图G1（2n,m）也是奇强协调的.     

关于一类立方图的可圈性研究

设G为无向图,如果对G的每一个定向D,都存在S（D）包含V（G）使在D中改变所有恰与S（D）中一个顶点相关联的弧的方向后所得的图为有向哈密尔顿图,则称G为可圈图．Klostermeyer和Soltes证明了P4k^3（k≥1）是不可圈图,现证明对任意整数n≥3,Pn^3是可圈图当且仅当n为奇数．     

mC_7的点可区别全染色

考虑m个长为7的圈点不交的并mC7的点可区别全染色问题.通过构造以色集合为元素的矩阵,利用色集合事先分配法及递归法确定染色,得出了mC_7的点可区别全色数的确切值.结果表明VDTC猜想对图mC_7成立.     

(P~2)_n和(P~3)_n的D(3)-点可区别全染色

图的染色问题是图论研究的经典领域,在网络结构和实际生活中都有着广泛的应用,随着计算机和通讯、电力网络的日益发展,染色问题成为近年来图论研究的热点.图的D(β)-点可区别全染色又是染色问题中的难点.通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系.讨论了幂图Pkn(k=2,3)的点可区别全染色,使得距离不大于3(D(3))的任意2点都有不同的色集合,得到幂图Pkn(k=2,3)的D(3)-点可区别全染色数.     

近完美匹配全覆盖点

利用匹配理论中的Gallai-Edmonds结构定理,首先得到了在一个有近完美匹配的图中判定一个顶点为近完美匹配全覆盖点的充要条件,然后对每一个顶点都为近完美匹配全覆盖点的图类给出了一个刻画.同时,也给出了一种构造这类图的方法.     

若干直积图的邻点可区别VE-全色数

应用穷染递推的方法研究了路与路(圈、星、扇、轮、完全图)构成的直积图的邻点可区别VE-全染色,并给出了具体的染色方案,进一步得到了邻点可区别的VE-全色数.