关于距离出现的次数问题研究

本文研究了对于给定平面上的点,考察任意两点间距离至少存在多少种不等距离,以及至多出现多少次最短距离、最长距离问题,同时解决了任意距离至多出现多少次的问题。     

平面n点构图中锐角三角形个数研究

在组合几何基础上,对n点构图(任意3点均不共线)中的锐角三角形个数问题进行了研究.通过研究具体的n点构图,证明了平面上的9个点,至多可排出54个锐角三角形.对于一般的n点构图,证明了9个以上的点构成的三角形中至多有64.17%的锐角三角形,且对于任意n,必存在一个n点构图使得这n个点构成的三角形中至少有50%的锐角三角形.     

任意两点间距离均为偶数的点集及构造方法

给出了任意两点间的距离均为偶数的点集的若干例子,以及构造方法;解决了在1维、2维、3维、n维空间中构造满足任意两点间的距离均为偶数的有任意多的有限个点的点集的问题。     

一般递归函数定义中极小化次数问题的研究

研究了定义递归函数过程中极小化运算的次数问题，证实了任意一个递归函数可以从初始子数出发，经有限次复合，递归和至多一次极小化运算而得到。这一结论对计算复杂性理论有明显的意义。     

高维空间的最大距离

任意n个不同点在平面上的最大距离仅能出现n次,在3维空间中,最大距离出现次数最多为2n-2。有学者证明：在4维空间中最大距离可出现[n^2/4]次。现给出n个不同点在2k(k=2,3,…,n）维空间中最大距离可出现[(k-1)n^2/2k]次。     

$P_n$和$C_n^k$的Ramsey数

称Fk为图F的k幂次图,如果V(Fk)=V(F),且Fk中的任意两个顶点相邻当且仅当在F中的距离至多为k.给定图G和H,Ramsey数R(G,H)为最小的正整数N,使得完全图KN的任意红蓝-边着色都会含有一个红色的子图G或者蓝色的子图H.证明了渐近阶R(Pn,Ckn)=(n-1)(χ(Ckn)-1)+σ(Ckn)+o(n),其中k是常数.     

关于平面点集中次空凸五边形的个数问题

设P表示处于一般位置的平面点集,P的子集T所确定的凸多边形CH(T)称为次空凸多边形,若CH(T)的内部至多含有P中的1个点.研究了P能确定的不交的次空凸五边形的最大个数问题.     

部分标号图的重构问题

本文引入了“同邻点对”概念,应用此概念证明了定理1—4,连同作者以前的工作一起彻底解决了:“至多五点未标的P阶图G可由它的任意五个主子图重构”。这一结果比F.Haray和B.Manvel的结果前进了一大步。     

无4-圈和5-圈的平面图的k-frugal列表染色

在图G的一个正常点染色c中,对于图中任意一点v,如果每种颜色在点v的邻点中至多出现k-1次,这个染色就称为图G的一个k-frugal染色。关于无4-圈和5-圈的平面图的k-frugal列表染色问题,有以下两个结论:(1)对于一切不含4-圈和5-圈的平面图,如果其最大度满足Δ≥3k+8,其k-frugal列表色数小于等于「Δ/(k-1)+2;(2)一切不含4-圈和5-圈的平面图,则其k-frugal列表色数小于等于「Δ/(k-1)+5。     

一类水平线性互补问题的一个不可行内点算法的收敛性

作为单调水平线性互补问题的推广，引入了Ｐ＊（κ）阵水平线性互补问题（简称Ｐ＊（κ）－ＨＬＣＰ）．证明了Ｙ．张的算法能被推广以解决Ｐ＊（κ）－ＨＬＣＰ问题，这个推广算法在运算过程中是独立于分类数κ的．如果这个算法的起始点是一对任意的正数，那么算法将达到Ｑ－线性收敛；如果起始点是一对足够大的正数，此算法经过至多Ｏ（（ｋ＋１）４ｎ２ｌｎ（（ｘ０）ｒｓ０）／ε次运算得到ε－逼近解，其中（ｘ０，ｓ０）是一对起始点