平面图的多项式与着色

研究平面剖分图的着色性质,通过讨论图的色多项式的零点问题,分析对图的着色保证相邻的两个区域着不同颜色的最少方法数目,进而给出了平面剖分图的着色方法数目的重要性质.主要研究方法是对平面图的着色提供了一个新的研究渠道,即通过色多项式计算,得出平面剖分前后的着色数目,进而再计算球面剖分图的着色数目.首先,研究"具有一条公共边的两个区域G_n和G_m,及广义剖分图"的着色问题;其次,研究"简单正多面体及球面的三角剖分图"的着色问题.     

平环图着色的性质

利用色多项式的零点问题的性质研究了平面图的着色问题,主要研究平环中具有n个区域以及剖分后得到的图进行着色性质,也就是使得相邻两个区域着不同色.首先,研究了带有n个区域平环图Gn的最小涂色数目,并且该图进行广义三角剖分,研究了广义三角剖分后图的涂色数目的性质;其次,讨论了两个这样图组合在一起,就是两个具有一条公共边Gt和Gs组成区域图的性质,讨论这些图及其广义三角剖分后图的涂色性质.进而证明这些图在剖分前后的着色的性质是不变的.     

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

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图 Hamilton圈的一个充分条件及算法     

方括号多项式与双色多项式

本文研究了纽结的方括号多形式[K(G)]和平面图的双色多项式Z G(q,v)的性质,同时给出它们之间的关系之间,主要是利用这两个多项式的定义和构造来进行研究的.通过对这些性质的研究将有利于研究平面的的着色等问题.     

新型三角多项式图

揭示了传统的三角多项式图的本质是一种随机过程 ,给出了另外 2种新的三角多项式图 ,即新形式的三角多项式图和等欧氏距离的三角多项式图 .通过证明 ,这 2种新的三角多项式图都具有传统三角多项式图所不可替代的优良性质 ,由此拓宽了三角多项式图的应用范围     

Mbius梯的着色问题

色多项式是图论的重要研究内容之一.借助广义Pólya定理和一些代数方法,讨论了特殊图类Mbius梯在不同约束条件下的着色问题,分别给出色多项式的不同表达式.     

一种基于截断多项式的三角域V-系统构造

U-系统和V-系统的出现和发展为连续和非连续信号的有效表达提供了一种新的思路.在对V-系统和三角域自相似剖分分析的基础上,提出了一种基于截断多项式的三角域V-系统构造方法.给出了三角域上的k次V-系统生成元和截断多项式的定义.依据三角域的自相似剖分结构从截断多项式和分片的Legendre多项式出发,构造了一种三角域上的V-系统生成元,并以三角域上的1次V-系统为例对所构造V-系统的表现形式给出了数学解析表达式.对所构造V-系统的性质进行了分析和证明.     

平面图的动态着色

研究平面图的动态着色数,通过定义一个算法得到强导出图.利用颜色对换的思想来研究平面图动态着色的上界问题,得到结论:若G是平面图,则χd(G)≤5.     

任意三角剖分下的C~1-有理样条函数及基函数

采用结点基的方法，结合研究多元多项式样条函数的光滑余因子方法的思想，解决了任意三角剖分下的Ｃ１－有理样条函数的存在性，并得到了任意三角剖分下具有最少自由度的Ｃ１－有理样条函数类．构造了具有３次代数精度的有理插值算子及其相应的全部Ｃ１－广义楔函数的简便的显示表达式。     

网格图的剖分图的强边染色

研究了3种网格图的剖分图的强边着色.网格图的剖分图是指用一个长为2的路去替换网格图的每条边.具体给出了六边形、四边形、三角形的网格剖分图的一种着色方法,以此为基础证明了Sχ′(Γs6)=4,Sχ′(Γs4)=5,Sχ′(Γs3)=7.     

扩容图及其谱性质

目的 研究扩容图的若干性质.方法 用代数分析法研究图的结构.结果 利用图的剖分线图的结构,给出了新的广义线图,我们称之为扩容图.结论 讨论了扩容图的若干基本性质,给出了图与其扩容图参数之间的关系,并由此确定了扩客图谱性质.     

任意三角剖分下的C^1—有理样条函数及其函数

采用结点基的方法，结合研究元多项式样条函数的光滑余因子方法的思想，解决了任意三角剖分下的Ｃ＾１－有理样条函数的存在性，并得到了任意三角剖分下具有最少自由度的Ｃ＾１－有理样条函数类，构造了具有３次代数精度的有理插值算子及其相应的全部Ｃ＾１－广义楔函数的简便的显示表达式。     

几类特殊平面图的圈包装问题

给定一个无向连通图G，圈包装问题就是求G的边不相交圈的最大数目．此问题在一般图下是APX困难问题，在平面图下是NP困难问题．主要证明了在几类特殊的平面图下多项式时间可得到最优解．主要考虑外平面图，系列平行图和平面欧拉图这三类特殊的平面图．     

Thomassen与曲面嵌入图的着色

曲面嵌入图的着色的研究起源于Heawood地图着色定理.本文在对原始文献进行研究的基础上,论述Thomassen在三色定理与列表着色、曲面嵌入图的着色、色多项式和着色的数目等方面的工作.他的研究受到了Mohar,Thomas和Hutchinson等许多数学家的关注.     

小圈二重覆盖三角剖分图

近三角剖分图是一连通平面图,其内面均为三角形,而其外面可能不是．图Ｇ的一个二重覆盖（ＣＤＣ）指它的一个圈族Ｃ,使得Ｇ的每条边恰属于Ｃ的两个元素．令Ｇ为一个具有ｎ个节点的２－连通平面图,Ｃ为Ｇ的一个ＣＤＣ．若｜Ｃ｜≤ｎ－１,则称Ｃ为Ｇ的一个小圈二重覆盖（ＳＣＤＣ）．本文证明每个近三角剖分图均存在一个ＳＣＤＣ．     

平面点线集三角剖分的扫描算法

提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O(NlbN),其中N是点线集中点的数目与线段端点数之和.     

Voromoi图和Delaunay三角剖分的计算及应用

论述了Ｖｏｒｏｎｏｉ图及其几何对偶Ｄｅｌａｕｎａｙ三角剖分的计算方法，重点探讨了Ｄｅｌａｕｎａｙ三角剖分的优化性质及其有限元网格自动生成过程中的应用，在此基础上提出了一种自动生成三角形有限元网格的新算法。     

对偶图的H圈分解和相应的平图4着色

阐明了平图中的H圈与对偶图中的森林Fi及顶点4着色的依存关系,提出了一种基于H圈分解的任意平图的顶点4着色方法。介绍了20面体平图中的24个H圈及对偶图中的24个森林Fi及24种顶点4着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的4着色方案数。得到任意平图及其对偶图均能分解出H圈和森林Fi,任意平图及其对偶图均为可4着色的。得到了当平图为三角剖分图时,对偶图为多边形组合,H圈个数必大于其对偶图中的H圈的个数。平图为多边形组合时,其对偶图为三角剖分图,H圈的个数必小于对偶图中的H圈的个数。平图中森林Fi的个数或4着色方案数等于对偶图中的H圈的个数;对偶图中的森林Fi′的个数或4着色方案数等于平图中的H圈的个数。     

关于一些无三角形的平面图选择数的一个注记（英文）

对每一顶点给定至少为k种颜色的列表,若图G可以正常着色,称G是k-可选择的.本文利用差值转移的方法和最小反例图的结构性质,证明了每个不含三角形且无6-圈,8-圈和10-圈的平面图是3-可选择的,丰富了平面图列表染色的结果.     

基于约束三角剖分的k-means聚类

提出基于约束三角剖分的k-means聚类算法.笔者首先按照约束三角剖分规则对数据点集进行三角网格化,删除大于给定阈值的长边形成k个连通子图,每个连通子图作为一个子类;然后对删除长边的孤立数据点在其邻域内进行局部划分,将其归到最接近的子类中.实验结果表明本文算法无需事先输入聚类数目,可以发现任意非凸形状簇.