基于顶点凸凹性多边形的核的算法

简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。基于简单多边形各顶点的凸凹性,提出了一个判断核的存在性以及得到核多边形的顶点序列的新算法。利用多边形凹点所在的部分相邻边剖分由多边形凸点组成的初始核多边形,实现了核的顶点坐标的求解。该算法便于实现,可广泛地应用于摄像机定位等涉及可见性的问题。     

PL/SQL在求解最短路径问题中的应用

图论中的一个典型的问题就是最短路径和最小代价问题.本文介绍了一种基于Oracle的表、视图及存储过程求解最短路径(最小代价)的方法,该方法使得解决复杂的有向图问题更加容易,而且不需要很多代码.     

给定割点数的单圈图的第二大谱半径

谱图理论的一个主要问题是研究图的结构性质如何由图的谱性质反映.割点数是图的重要结构参数,讨论了单圈图的割点数和谱半径之间的联系.在刻画了给定割点数的单圈图中具有最大谱半径图的结构基础上,延续这一讨论,刻画了在某些情形下,给定割点数的单圈图中具有第二大谱半径的图的结构.     

计算图的色多项式的一种新的方法：缩点递推算法

为了更深入地探索图的色多项式与图的结构之间的关系，以及提高求色多项式的算法速度，给出了一种有效的求色多项式的缩点递推算法。     

多孔介质不混溶二相驱动问题的一种新的差分解法及其收敛性分析

考虑不相混溶不可压缩二相驱动问题的数值解，提出了一种新的非均匀网格上的差分解法：用箱型差分格式解浓度方程，用块中心差分格式解压力方程．该法在时间和空间剖分非均匀的情况下关于时间和空间具有二阶精度的误差估计．由于该法关于压力是五点差分格式，关于浓度是九点差分格式，求解工作量与传统的有限差分方法求解的一样，但比有限元方法的工作量要少得多，且该法计算稳定，易推广到三维问题中去。     

x_3（G）＋x_3（_G~－）的可达下界

引入了最佳配点、最佳配邻点集的概念，讨论了３－色数的界，给出了ｘ＿３（Ｇ）＋ｘ＿３的可达下界．     

TSP最短路径的必要条件初探

对于被访问城市数为n的不对称旅行商问题,构造了一个n行和n列的方阵,每一行上的n个元素为同一个被访问城市;每一列上的n个元素为n个互不相同的被访问城市.依次从该方阵的第一列到第k列上各取出一个城市,同一行上不存在两个被取出的城市,这样取出的城市序列就构成了一条长度为k的路径.主要讨论最短路径的性质:如果一条长度为(n-1)的最短路径能被产生,则该路径上的任一长度为k的路径都为最短路径,k=1,2,…,n-2.该性质为旅行商问题算法研究的基础.     

Ore定理的一个注记

对简单图G=(V,E),Ore定理告诉我们如果对G的每一对不相邻的顶点u,v都有d(u)+d(v)≥|V|,则G有哈密尔顿圈.证明了,若G仅包含一对不相邻的顶点u,v,满足d(u)+d(v)＜|V|,G仍有哈密尔顿圈.     

收缩临界5-连通图最长圈上的5度点

讨论收缩临界5-连通图最长路和最长圈上5度点的分布情况,刻画收缩临界5-连通图的结构.