k度Steiner最小权网络的线性时间算法

已知平面上n个固定点集合N和m个可动点集合M,求互连点集N∪M的最短连通网络,要求这个连通网络满足：（1）固定点的度为1,可动点的度为k(k≥3）;（2）n=2 （k-2）m。网络中每条边的权与可动点的位置有关,问题是如何确定这m个可动点的位置,使这个连通网络的权最小,这个问题称为k度Steiner最小权网络问题。本给出了k为偶数,边权值为L1距离时计算最小权网络的O(n ln k)时间算法。     

K度Steiner问题

给定平面上n个固定点 (称为正则点 )的集合N和m =n - 2k- 2 个可动点 (称为Steiner点 )的集合M ,其中k( 3≤k≤n)是确定的正整数 要求互联点集V =N∪M的网络的拓扑在正则点的度为 1 ,Steiner点的度不超过k ,这种网络称为k度网络 确定m个Steiner点的位置 ,使互联这n m个点的k度网络总长度最短 显然这个最短的k度网络一定是树 ,我们称这个树为k度Steiner最小树 (kDSMT) ,并称这个问题为k度Steiner问题 本文得到了kDSMT的一些结构特征 ,并提出了一些有待进一步研究的问题     

微积分中的三点注记

对∞∑n=1（-1）^n=1 1/（n＋k1）＋（n＋k2）＋…＋（n＋km）n≥1 1≤k1〈k2〈…〈km m≥给出求和方法。对四类方程f（x,y,z）=0证明在奇异点处,无切平面。对n维单位球体体积Vn（n≥2） n=5 V5体积最大,lim n→＋∞Vn=0     

平面格点形心问题研究

在组合论和数论中，平面格点形心问题是对给定的自然数k，求这样的最小整数n(k)，使得当n≥n(k)时，平面上任意几个格点中必存在k个格点的形心也是格点。显然n(1)=1，并容易求出n(2)=5。文献［1］用较复杂的组合设计方法确定出n(3)=9。本文提出一种简易的方法，给出n(3)=9的新证，并得到n(4)的改进上界。     

Baskakov算子的点态正逆估计

对于定义在 [0 ,∞ ]上的 Baskakov算子 Vn(f ,x) =∑∞k=0f kn Vn,k(x) ,此处 Vn,k(x)≡n +k -1k xk(1 +x) - n- k,本文给出了 Baskakov算子的点态正逆估计     

平面上n点集的k－子集

本文引进平面上ｎ点集的凸壳和层的概念．用其研究平面上ｎ点集的ｋ－子集的一个最大值问题．对于ｋ＝２给出精确值．对于ｋ＝３给出初步讨论。     

平面上n点集的k—子集

本文引进平面上ｎ点集的凸壳和层的概念，用其研究平面上ｎ点集的ｋ－子集的一个最大值问题，对于ｋ＝２给出精确值，对于ｋ＝３给出初步讨论。     

逐行(列)扫描判定点集是否在多边形内部的算法

提出一种基于点集排序,逐行（或逐列）扫描平面点集S,判定点集S中的点是否在多边形L内部的算法,该算法的时间复杂性在最坏情况下为：max(O(n log n),O(km log m)次比较和O（km)次乘法,其中n为点集S的点数,m为多边形L的顶点数,k=min(u,v),其中u,v分别为点集S中的点分布的行数和列数,该算法思路简单,易实现,且在一般情况下,效率比已有的算法高。     

高维空间的最大距离

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

关于Hosoya指标和Merrifield-Simmons指标的k色极图

图的Hosoya指标定义为图中包含空边集在内的对集总数.图的Merrifield-Simmons指标定义为图中包含空点集在内的点独立集总数.考虑点数为n的k色连通图的集合Gn,k,证明了Tur n图Tn(k)是Gn,k中Hosoya指标最大且Merrifield-Simmons指标最小的图,还确定了k=2,3时Gn,k中Hosoya指标最小且Merrifield-Simmons指标最大的图.     

泛圈图的一个新的充分条件

设G是一个阶为n的2－连通简单图,αv表示G中包含点v的最大独立集的点数,对任意uv不属于E,设Tuv=V\(N(u)∪N（v)),αuv=min{αu,αv}。本文证明了：如果对于任一对不相邻点u,v,｜N（u)∩N(v)｜≥min{αuv-1,｜Tuv｜},则除了一些特殊图外,对于G的任一点x和任意整数k(4≤k≤n),G包含长度为k县包含点x的圈。     

平面网格点中无直角的最大点集构造

本文首先介绍了关于点集中无直角的最大点集的研究现状;然后讨论了在二维平面上m×n网格点中无直角的最大点集的构造,通过利用坐标投影法和代数法,分别证明得到此最大点集的基数为m+n-2;最后给出一些关于二维平面网格点中有待解决的新问题.     

图GP(n,t,k)的点传递性

定义图GP(n,t,k)有顶点集V(GP(n,t,k))={ui,vi∣i∈Zn},边集E(GP(n,t,k))={uiui+1,uivi,vivi+t,uivi+k∣i∈Zn}.讨论了图GP(n,t,k)的自同构映射的性质,给出了它是点传递图的充分条件,进一步分别得到了GP(n,t,k)是Cayley图和拟Cayley图的充分条件.     

线性矩阵方程的斜Hermit{P,k+1}Hamilton解

给定矩阵P∈C~(n×n)且P~*=-P=P~(k+1).考虑了矩阵方程AX=B存在斜Hermite{P,k+1}(斜)Hamilton解的充要条件,并给出了解的表达式.进一步,对于任意给定的矩阵∈C~(n×n),给出了使得Frobenius范数‖-‖取得最小值的最佳逼近解∈C~(n×n).当矩阵方程AX=B不相容时,给出了斜Hermite{P,k+1}(斜)Hamilton最小二乘解,在此条件下,给出了对于任意给定矩阵的最佳逼近解.最后给出一些数值实例.     

一类图的色唯一性

让W_(n,n-2)表示删去轮形图W_n中一条轮辐所得到的图.W(n,n-2,k)表示在W_(n,n-2)中由k个点u_1,u_2,…,u_t组成的独立集取代W_(n,n-2)中的2度点u,使得u_j(j=1,2,…,k)仅与u所相邻的两个点x,y相邻接而得到的。本文证明了当k=2,n≥4为偶数时,这类图是色唯一的。     

一类非本原有向图第k个顶点指数集

非本原有向图的广义本原指数是本原有向图的广义本原指数的推广,文中主要给出了围长为2的n阶k-本原(非本原)有向图的第k个顶点指数[expD(k)]的最好上界：(1)若n≥7,则expD(k)≤n^2-7n k 14;(2)若n=3,5,则expD(k)≤2n k-6;(3)若n=4,6,则expD(k)≤2n k-5,并且确定了相应的指数集.     

一种确定多值函数w=n(/)z某个单值解析分支的方法

多值函数w=n(/)z可分出n个单值解析分支wk=(n(/)z)k(k=0,1,2,…,n-1).本文给出了由给定某点z=z0函数值w=w(z0)所确定的单值解析分支的一种求解方法.     

S(3,n)的k-边优美的图标号

设k为非负整数,G是一个p点q边图,如果将G的边用k,k+1,k+2,…,k+q-1进行标号,而顶点标号模p运算后各不相同,则称G是k-边优美的.对于所有满足G为k-边优美图的非负整数k所构成的集合称为图G的边优美指标集.该文给出了图G=(V,E)为k-边优美的定义,根据轮图的特殊性质,讨论了S(3,n)为k-边优美图的必要条件.根据所得的必要条件,利用递归的方法构造S(3,n)的k-边优美图标号并给出详细证明,从而完全解决了当n为偶数时S(3,n)的边优美指标集问题.     

一类变形的McMullen集的维数及其应用

研究了平面上一类变形的Mc Mullen集R=∑∞k=1a00b-kxkyk,(xk,yk)R,其中整数a,b满足|a|≥|b|1或者|b|≥|a|1,有限整数点集R{(i,j),i=0,1,…,n-1,j=0,1,…,m-1},得到了这类自仿射集的Hausdorff维数和Box维数的计算公式.并且作为其应用给出了自仿射集R=∑∞k=1a bb a-kxkyk,(xk,yk)R相应的Hausdorff维数和Box维数,其中整数a,b满足|a-b|≥|a+b|1或者|a+b|≥|a-b|1有限整数点集R{(i+j,-i+j),i=0,1,…,|a-b|-1,j=0,1,…,|a+b|-1}.     

排列图的代数性质

构造了一种新的Cayley陪集图,并且证明了这种Cayley陪集图能够被表示成〈n〉上的k-置换集V(An,k)上的置换图An,k,进一步说明了得到广泛深入研究的(n,k)-排列图An,k是基于对称群的Cayley陪集图,从而是点传递的.