给定悬挂点数的树和单圈图的顶点度函数研究

设G是n阶简单图,G的悬挂点数记作p(G),顶点度函数指数H_(f)(G)定义为H_(f)(G)=∑_(v∈V(G))f(d(v)).考虑在给定悬挂点数为k的n阶树和单圈图中,在f(x)是严格凸函数的情况下,顶点度函数H_(f)(G)的最大值问题.在f(x)是严格凹函数的情况下,同样的结果也适用于顶点度函数H_(f)(G)的最小值问题.通过对这些情况的分析,得出了顶点度函数H_(f)(G)在给定条件下的最值性质.这些结果对理解图论中的悬挂点和顶点度函数的性质具有重要意义.

基于顶点度的模型简化算法

针对基于二次误差度量的边收缩算法在计算大度顶点误差度量时计算量大,且收缩该类顶点关联边时易使关键点发生偏移而引起模型变动过大、简化不够准确的问题,提出了基于顶点度的模型简化算法。该算法不但提高了模型的简化质量,而且加快了模型的简化速度。

基于顶点度的多分辨率表示

针对边收缩算法在计算大曲率面距离公差时计算量大 ,且收缩大曲率面所含的线段时易使关键点发生偏移而引起模型变动过大、简化不够准确的问题 ,本文在边收缩算法基础上提出了加入顶点度控制的算法 ,以减少大曲率面距离公差的冗余计算 ,并提高模型简化质量。实验表明该算法能提高模型简化质量 ,并加快图形收缩的生成速度。

树状六角系统的一些基于顶点度的拓扑指数

根据图的基于顶点度的拓扑指数的定义以及树状六角系统的结构特征,给出了树状六角系统基于顶点度的一些拓扑指数I(C_h)和该六角系统的转向六角形个数以及分枝六角形个数的函数关系式,并得到了相应的极图.

轮图的顶点度距离

顶点度距离是图的一个关联顶点度和顶点间距离的局部指标.针对一类特殊的多圈图——轮图,研究了其顶点度距离及极值问题.结果表明,轮图的顶点度距离在图的中心点取得最大值,在其轮上的顶点处取得最小值.

无向图顶点度数若干问题的分析与论证

用图形来描述某些对象(或事物)之间具有某种特定关系常常感到特别方便。本文感兴趣的是两对象之间是否具有某种特定关系,所以图形中两点间连接与否很重要,但是连接线的方向则无关紧要。

基于顶点重要度的保形网格简化方法研究

为解决许多网格简化方法不能很好地保持模型的重要几何特征问题,提出基于顶点重要度和三角剖分的边折叠简化算法。算法通过特征因子加权顶点重要度作为边的折叠代价,定义法向量夹角因子,控制边的折叠顺序;在折叠过程中对边界特征区域进行冻结处理,以保持模型总体轮廓特征;采用边中点折叠和边邻域网格重建方法完成折叠操作。实验结果表明,模型在大规模简化后,该方法能较好地保持模型的几何特征。

三角网格顶点重要度的自适应Loop细分算法

提出了一种新的自适应细分算法,在顶点的1-邻域内,用与顶点相连较长三条边的端点构成的平面去替代其平均平面,将顶点到其平均平面的距离作为判断顶点重要度的标准,对三角网格进行自适应细分。由于原始三角面片的高密度和形状相似性,以点面距离为细分尺度所产生的误差,可被限制在一个体元之内,与反复修正顶点法矢算法相比,该算法大大减少了计算量。实验结果表明,所提方法在三角网格细分过程中,简化了数据模型,提高了处理速度。

基于顶点重要度和层次聚类树的地形网格简化

为提高基于精细DEM数据的地形网格简化效率,在传统顶点聚类算法的基础上,提出一种基于顶点重要度和层次聚类树的地形网格简化算法。对地形分块顶点进行聚类,引入由顶点特征值和简化误差构成的顶点重要度来筛选簇代表点;根据代表点构建粗化网格,迭代缝合与简化过程直至完成整个地形网格简化;采用内存层次聚类树对简化的中间结果进行组织,将之用于地形多分辨率绘制中,指导网格的简化和细分。实验结果表明,该算法较好地保持了原始地形特征,缩减了内存消耗,中间结果的利用有效提升了地形渲染效率。

基于顶点局部特征度的网格模型分割算法

网格模型的简化要兼顾保持细节特征和快速这两个基本原则,而对网格模型进行分割可以有效提高模型简化效率。提出了一种基于顶点局部特征度的网格模型分割算法。分割时,网格模型要求分割成大小适中、密度差异相对明显的连续区域,区域边缘平滑,且所有三角形均属于某个区域。通过引入顶点局部特征度的概念对区域生长算法进行了改进。

图的修正的k-顶点彩虹连通度

路P称为图G的修正的顶点彩虹路,如果P中所有的顶点着不同的颜色或者除端点外其余内部顶点着不同于端点的颜色且内部顶点染色各不相同.图G称为是修正的k-顶点彩虹连通的,如果对于G的任意两个顶点u和v,G都有k条内部不交的修正的顶点彩虹u-v路.使得图G是修正的k-顶点彩虹连通图的最小颜色数目k称为图G的修正的k-顶点连通度,记做rvc*k(G).文中给出了C_n,W_n,K_(p,q)和K_n的修正的k-顶点彩虹连通度.

拟单圈图的调和指数

调和指数是一个与图的边和顶点度的相关概念,调和指数在图中代表了一种度量图的边权重的方式.设图G是n阶的简单图,图G的调和指数H(G)定义为H(G)=∑_(uv∈E(G))2/d(u)+d(v),其中E(G)表示图G中的边,d(u)和d(v)分别在图G中表示顶点u和v的度.拟单圈图是一类特殊的图,它不是单圈图,且在图G中存在点u∈V(G),使得G-u为连通的单圈图,则图G就称为拟单圈图.针对d(u)≥2的情况下,给出了拟单圈图的调和指数的下界,并在此情况下刻画了极图.

满足邻集交和点度和的图的Hamilton性质

结合关于独立数的邻域交条件,给出了图G为Hamilton图的关于最小度的新度和条件,并且证明了在此种条件下3连通图G是Hamilton连通的。

图的最小顶点覆盖问题的面上DNA解法

1994年 ,Adlem an提出一种解决 NP完全问题的新方法— DNA计算 .之后又出现了许多关于 DNA计算的改进操作并增加了其可靠性 ,其中面上操作是一种很有效的方法 .本文利用 DNA计算的固态处理 (面上计算 )解决了图论中又一 NP完全问题—图的最小顶点覆盖问题 .构造了含有 6个顶点 10条边的图的顶点集子集对应的数据池之后 ,进行了一系列的合成、杂交、清洗、变性等生物操作 ,得到所有覆盖对应的 DNA序列 ,然后通过编址过程得到所要求的最小覆盖 .

图的度和与圈可扩性

讨论了两个点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶n≥3,如果G中任意一对不同的顶点u,v满足d(u)+d(v)≥n+1,则G是完全圈可扩的。

顶点法矢在自适应Loop细分算法中的应用

本文根据一种新的面积角度加权顶点法矢计算公式对顶点平坦度方法进行了改进,考虑到了三角面片的面积和形状对三角网格顶点法矢的综合影响。使顶点法矢的计算结果更为准确,也使求顶点平坦度的算法得到了优化。

图的度和与扩圈

本文讨论了两顶点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶 ,如果G中任意一对不相邻的顶点u,v满足 ,则G中任意一个满足 的圈C是可扩的。这里圈C的下界是最好可能的。由此进一步得到,如果G中任意一对不相邻的顶点u,v满足 ,则G是完全圈可扩的。

改进的最小顶点覆盖问题的贪婪算法

通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完成算法的实现,从而降低了算法的时间复杂度,且更易于编程.该算法在最坏情况下的时间复杂度为O(|V|2).

图的最小度与路可扩性

讨论了图的最小度与路可扩之间的关系,得到当δ(G)≥2/G+1,则图G是路可扩的。这里δ(G)的下界是最好可能的。

3-连通无爪图的度和与泛圈性

若图G中不含同构于K1,3的导出子图，则称G为无爪图．笔者讨论了3-连通爪图中三个顶点的度和与泛圈性之间的关系，给出了图是泛圈的一个充分条件，得到了如下结果：设图G是n阶3-连通无爪图，如果σ3（G）≥n＋1，则G是泛圈的．