平面三角剖分图中非连通图的Anti-Ramsey数

给定图 G 的一个边染色,如果图 G 的任意两条边颜色都不相同, 那么就说图 G 是彩虹的。 图 H 在图 G 中的 anti-Ramsey 数是使得边染色图 G 中不存在任何彩虹子图 H 的最大颜色数。 图的 anti-Ramsey 数目前得到广泛的研究, 尤其是匹配在多种图类中的 anti-Ramsey 数得到广泛而 深入的研究。 Gilboa 和Roditty 研究了由小的连通分支构成的图在完全图中的 anti-Ramsey 数,而非连通图在平面图中的 anti-Ramsey 数除匹配外结果较少。 本论文将继续以这个方向研究边染色图中 C3 ∪ tP2 这个非连通图在平面三角剖分图中的 anti-Ramsey 数,得到了对任意n ≥ 2t + 3, t ≥ 2, 2n + 3t − 9 ≤ AR(Tn, C3 ∪ tP2) ≤ 2n + 4t − 5。

一种适合VRML应用的平面三角剖分快速算法

产品数据向 Web使能数据的格式转换是实现异地、异构环境下产品信息共享的一条有效途径 .VRML作为三维场景的描述语言得到了广泛应用 ,成为产品数据 Web使能的载体 .为了满足 VRML应用的需要 ,提出了一种改进的从平面多连通域到单连通域的快速切分归并方法 ,介绍了一种任意平面连通域的三角剖分算法 ,并对生成的三角面片进行合并 .整个算法具有速度快。

三正则平面图与平面三角剖分图

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图

简单平面三角剖分图中各生成两部子图的最大次

讨论了简单平面三角剖分图中各生成两部子图的最大次的取值范围 ,否定了郁星星提出的生成两部子图最大次的上界为常数的猜想 ,并且得到下面的主要结果 .(1)设 G是简单平面三角剖分图 .当 n=3时 ,α0 (G) =1;当 n=4时 ,α0 (G) =α1(G) =α2 (G) =1;当 n≥ 5时 ,有 2≤ α0 (G)≤ α1(G)≤ α2 (G)≤ [Δ(G) /2 ],且下界 α0 (G) =2能达到 .(2 )若 l是不小于 3的整数 .则 (a)存在简单平面三角剖分图 G0 ,使得 α0 (G0 ) =l;(b)存在简单平面三角剖分图 G1,使得 α1(G1) =l.

平面三角剖分图的L(2,1)标号

图G的L( 2 ,1)标号是从一个顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1,则 |f(x) -f( y) |≥ 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) |≥ 1.图G的L( 2 ,1)标号数λ(G)是使得G有max{ f(υ) :υ∈V(G) } =k的L( 2 ,1)标号中的最小数k .本文证明了对最大度为Δ的一般平面三角剖分图G ,有λ(G)≤Δ2 -Δ ;当G的直径大于 2时 ,有λ(G)≤Δ2 -Δ ;

非极大部分对偶平面图的刻画与平面三角剖分图的部分对偶最大亏格

图嵌入G的部分对偶G^(A)是选择G的部分边集A做对偶,它是经典的庞加莱对偶G^(*)的推广.与经典的庞加莱对偶不同的是,部分对偶G^(A)的亏格往往不等于G的亏格.类似于黄-刘图的非上可嵌入性刻画定理,对平面图我们先证明了非极大部分对偶平面图结构定理,并由此确定了平面三角剖分图G的部分对偶最大亏格,即当G为3-圈时,G的部分对偶最大亏格为1;否则G的部分对偶最大亏格为其顶点数减1.

平面点集Delaunay三角剖分的分治算法

为发展图形网格化技术,研究了平面点集的三角剖分算法。根据经典算法中在实际应用中遇到的共性问题,提炼了3个工具算法;为了更好地表示平面区域划分的拓扑信息,引入了双链接边表(DCEL)的数据结构。在此基础上,设计并实现了平面集Delaunay三角剖分分治算法,并对特殊退化情况进行了处理,通过计算表明了该算法时间复杂度为O(N*logN)。实验数据结果验证了该算法的正确性、健壮性。

空间封闭点云的八象限三角剖分算法

提出了一种针对空间封闭点云的三角剖分算法.该算法首先根据空间封闭点云的分布特征,将其划分到三维坐标的八个象限中,使每部分点云的包角均小于180°;然后适当旋转各部分点云,使其对应投影平面面积最大化,再运用平面三角剖分方法对其进行三角剖分,从而得到各部分点云的剖分结果;最后将已处理的各部分用三角面片对其边界进行缝合,进而形成空间封闭点云的立体三角化.实验结果表明,该方法剖分速度快、形成的三角网格质量高,能够较好地再现原三维物体的表面特征.

关于两类平面图及相关图的L(2,1)-标号问题

图G的L( 2 ,1) 标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1,则 |f(x) -f(y) | 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) | 1 图G的L( 2 ,1)标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L( 2 ,1)标号中的最小数k Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) Δ2 证明了对平面三角剖分图、立体四面体剖分图、平面近四边形剖分图 。

与四色定理等价的几个命题

本文论述与四色定理等价的几个新命题 .从而给出了平面三角剖分及圈上的 4染色集的一些新性质 .将平面图的 4可染色问题转化为圈上的 4染色来研究 ,这将更便于用计算机来寻找关于四色定理的更简单的证明方法 ,也为探索四色定理的理论证明提供了新的途径和方法 .

一种三维表面重构中的轮廓集拼合新方法

针对切片级三维表面重构中的难点,提出了一种拼合轮廓集的新方法通过对待拼合的轮廓集首尾轮廓进行平面三角剖分方向的判别,将空间轮廓集拼合的三维问题转化为平面多连通域三角剖分的二维问题,并改进了现有的平面多连通域三角剖分算法,巧妙地解决了切片级重构中的轮廓分支对应问题。实验表明,该方法能准确完成复杂轮廓集的表面拼合,具有良好的适应性。

关于图的L(d,1)-标号问题

图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则f(x)-f(y)≥2;若d(x,y)=2,则f(x)-f(y)≥1.图G的L(2,1)-标号数λ(G)是使得G有maxf(v)v∈V(G)=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为Δ的一般图G,有λ(G)≤Δ2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.

关于一个猜想的简单证明

图Ｇ的一个（正常）路着色是一映射φ：Ｖ（Ｇ）→Ｃ，使得Ｃ中任一元素的原象的导出子图是路的不交并，使Ｇ有正常路着色所需要的Ｃ的最小基数｜Ｃ｜，称为Ｇ的路色数，用ｘ（Ｇ；Ｐ∞）表示。Ｊ．Ａｋｉｙａｍａ和Ｅｒａ［３］提出如下问题：是否存在平面图Ｇ使得ｘ（Ｇ；Ｐ∞）＝４？关于这一问题，已有人证明［３，５］；对于任意平面图Ｇ，都有ｘ（Ｇ；Ｐ∞）≤３。

图G_(nK_4)的消圈数

给定图G=(V,E),S?V,若G-S是—个无圈图,则称S是一个消圈集,且称min{|S||S是图G的消圈集}为图的消圈数,简记为▽(G).本文考虑了一类含n个K4拷贝组成的平面三角剖分图G_(nK4),并得到了▽(G_(nK4))=(|V(G_(nk4)/2)|)/2,1≤n≤4,从而证明了Albertson和Berman提出的大森林猜想:每一个平面图的消圈数都不超过其顶点数的一半.对于n≥5的情形,▽(G_(nK4))未被解决.