一类4-正则图的最小折数纵横扩张

纵横嵌入是图论中的一个有很强应用背景的问题。作为其基本的一步就是研究一个嵌入的纵横扩张。虽然确定最小折数扩张已经从理论上得到了解答，但并未给出很好的算法。本文提供了这方面的一些结论，并进一步研究了一类4－正则图g，得到了确定这类图最小折数纵横扩张的一个线性算法。     

几类4-正则平面图的最小折数纵横扩张

主要讨论了4类4-正则图的最小折数纵横扩张,对任意阶这样的的4-正则图都给出了它的一个最小折数纵横扩张,并给出了最小折数与阶数之间的关系.     

一类4-正则图的最小折数纵横扩张

提出了一类新的4-正则图,并讨论了其最小折数纵横扩张,设计出求最小纵横扩张的线性时间算法,给出了最小折数与阶数之间的关系.     

某些平面图的最小折数

讨论了4类4-正则平面图的最小折数纵横扩张.     

某些平面图的最小折数

讨论了4类4-正则平面图的最小折数纵横扩张。     

一种基于改进FCM的自动图像分割算法

针对FCM进行图像分割时需要人为确定聚类数的问题,提出一种改进的基于FCM的图像分割算法.该算法先对图像进行4叉树结构的子图分解(即原图等分为2×2的4幅子图,子图再等分为2×2的4幅子图),待子图满足一定条件时进行聚类数为2的FCM聚类分割;然后将分割好的区域根据其大小及相邻区域直方图的巴氏距离进行合并,得到最终的分割结果,从而避免了聚类数目的直接确定.实验结果表明:该算法能够获得很好的分割效果;对子图进行聚类分割减少了每次参与聚类的对象数,从而在一定程度上降低了算法的计算量.     

FCM聚类算法与改进层次聚类算法的结合

模糊c-均值聚类算法(fuzzy C-means 简称FCM)和层次聚类算法是两种非常重要的聚类算法.由于FCM算法对初始聚类中心敏感,并且需要人为确定聚类类别数,这样收敛结果易陷入局部最优解.通过对这两种聚类算法的分析,首先对传统的凝聚层次聚类算法提出了改进,然后用改进的凝聚层次聚类算法得到最佳聚类数和初始聚类中心,最后用FCM算法进行再次聚类,以此得到更好的聚类结果并且减少了执行时间和迭代次数.     

图的冠积和边冠积的b-染色

用构造染色法和贪心算法研究限制最大度和最小度的任意两个图、 两个同阶图, 任意两个完全图的冠积与边冠积的b-色数和m-度, 以及在此基础上推出的部分图类的广义冠积和广义边冠积的b 色数和m-度.     

多重分割框架下的两类新本体学习算法

多重分割本体学习算法的本质是将整个一维实数轴分割成k段,并依次分配给本体图上的k个分割类的顶点.在具体学习过程中,对不符合预定规则的本体样本对进行惩罚,进而得到最优本体函数.给出两类多重分割框架下的本体学习算法,并且利用统计学习理论中覆盖数逼近的方法对第一类本体学习算法进行理论分析.     

最小费用排序问题

两类最小费用排序问题—费用函数满足三角不等式的最小费用排序问题和费用函数不满足三角不等式的最小费用排序问题.利用排序问题的O(nln(n))算法、图论和网络流理论分别给出了这两类问题的离线的最优多项式算法,并分别给出了这2个算法的最优性和计算复杂性分析.     

四正则图的自动生成及纵横嵌入的线性算法

刘彦佩教授论述的纵横嵌入术已为超大规模集成电路 (VLSI)的平面设计提供了较完备的理论体系 ,本文以此为依据建立的算法能自动生成任意点数的四正则图例 ,并对其进行双极定向和双极标数 ,进而画出其纵横嵌入图 .在对四正则图进行双极定向时 ,根据吸收规则的原理 ,设计了一种在计算机上易于实现的算法 ,该算法已成功地绘制了含有几个点及至近千个点的四正则图的纵横嵌入图 .     

三角拼图的超边幻和标号

幻类标号是由数论中幻方的概念而提出的一类图标号,图标号问题已引起广泛的关注与研究.本文主要研究三角拼图的超边幻和标号问题,给出其超边幻和标号的算法和严格的数学证明.     

基于核的有向强连通图计算机随机生成算法

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。     

关于图的星荫度的一个注

图G的曼荫度vas(G)定度为对G进行项点着色且使得G中同色顶点导出的子图的每个连通分支都为星时所需的最少色数,本文证明了平面图和外平面图的曼荫度的平凡上界事实上也是最好的上界.     

6-阶图与路的笛卡儿积交叉数

图的交叉数是指把图画在平面上边与边产生的交叉数目的最小值。图的交叉数只在好画法中得到,好画法是指满足边自身不交叉,相关联的边不交叉,任意两条交叉的边至多交叉一次的画法。图的交叉数已被证明是一个NP-完全问题,由于其难度,要知道图的确切交叉数是非常困难的。到目前为止,只知道少数图的交叉数,其中大部分是特殊图的笛卡儿积图的交叉数,比如路,圈以及星图与点数较“少”的图的笛卡儿积交叉数。在这些基础上,应用数学归纳法,把相关结果拓展到4个6-阶图与长为的路的笛卡儿积交叉数。     

几种特殊图形的分数色数研究

图的着色问题是图论中的一个重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.本文研究了一些特殊图形的分数色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明.