首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 93 毫秒
1.
针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念.在图中寻找最少点数的概率支配集称为最小概率支配集问题.证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法.基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题...  相似文献   

2.
皮军德  林浩 《河南科学》2007,25(4):537-541
研究了广义区间图的最小全控制集和最小配对控制集的计算问题.对有一个公共交点的直线簇上的区间图,给出了计算其最小全控制集的O(n)时间算法和其最小配对控制集的O(n+m)时间算法.  相似文献   

3.
在[1][2]中许永华对结合环R引入右R-模同态链归纳条件,可以叙述为:设r∈R,令元素r的右零化子r~⊥={x∈R|rx=0}。设M={r~⊥,AOr∈R},则{M,}作成一个偏序集。我们说结合环R满足右R-模同态链归纳条件,如果偏序集{M,}中每一链 (即M的有序子集) 都有最小上界。[3]中对环R引入了一个较之弱的条件,我们将称之为特殊右零化子集归纳条件,这是指,要求偏序集{M,}是个归纳集,即只要求M中每一链都有  相似文献   

4.
求图控制集问题的模拟退火算法的改进   总被引:1,自引:0,他引:1  
图控制集问题要求确定任意简单无向图的最小控制集,是NP-难度的问题.本文针对已有的求解此问题的模拟退火算法进行了两个方面的改进:一是给出了一个更为合理的解的评估函数;二是提出了一个产生邻解的加权随机策略.仿真实验表明,改进后的模拟退火算法在稠密图的随机实例上明显提高了收敛速度.  相似文献   

5.
本文讨论的图都是无向的简单图。未定义的术语和记号参见[1]。1971年,C.st.J.A.Nash-williams证明了:设G是n阶2-连通图,C是G中任意的最长圈,R=V(G)\V(C),若G的最小次δ≥(n+2)/3,则G[R]是独立集。1981年,J.A.Bondy根据整性的组合原则,给出了下列结论:设G是n阶2-连通图,C是G中任意的最长圈,R=V(G)\V(C),若对于G的任意独立集{u,v,w},有d(u)+d(v)+d(w)≥  相似文献   

6.
针对在无线网络中构造连通支配集问题,提出了一种基于圆盘图模型构造连通支配集的分布式算法PS-CDS,算法分为2部分,首先由PS-CDS-1算法构造极大独立集,然后通过PS-CDS-2算法向极大独立集中添加连通节点得到连通支配集.所提出的算法包括功率分配方案,选择能完成邻域广播的最小发送功率.算法的时间复杂度为O(n),消息复杂度为O(nm),近似比为R■/R■(2opt+1)-2.将PS-CDS算法与其他连通支配集算法进行实验比较,结果表明PS-CDS算法所生成的连通支配集规模最小.  相似文献   

7.
二色经典Ramsey数R(k,l)是指具有下述性质的最小正整数r:用两种颜色把r 阶完全图Kr的边任意染色后, Kr中一定存在单色的Kk或Kl, 其存在性的证明并不困难,但具体的Ramsey数的计算却是组合数学中非常困难的问题[1]. 当今学术界关于Ramsey数研究的最新进展详见文献[2]动态综述论文.本文沿用文献[3~7]的方法,构造12个素数阶循环图,得到12个二色经典Ramsey数的新下界.研究简报如下.  相似文献   

8.
欧氏整区为域或域上多项式环的条件已有不少文献给出[1]、[2]。本文给出带有欧氏算法的交换环为域或域上多项式环的一些条件,这些条件较[1]、[2]为弱,可供教学参考。定义1 一个交换环称为带欧氏算法,如果存在一个映射‖‖:a→‖a‖为R到非负整数集的映射,使得如a、b≠0 ∈R,有q、r∈R,使得:  相似文献   

9.
图的控制集理论在图论领域中发展较快.尤其近几十年,图论研究不断深入,控制集理论方面的新参数不断涌现,在科学计算机、编码密码学、优化组合、网络通信、系统监视和网络社会等领域也有着重要的应用.在其基础上提出来的图的定位控制集就广泛应用于通讯网络和监视系统中,已经成为现在编码理论中较活跃的研究方向.即便对最简单的路和圈,找出一个图G的最小定位控制集是非常困难的.就路和圈的定位控制集问题,当r=1和2时的情形已给出结论.本文讨论当r=3时,定位控制集有关路和圈问题的完整结果.  相似文献   

10.
对于给定的n阶连通图G,一个路由选择R是指G中的n(n-1)条路集,其中每个有序点对都有路集中的一条路连接.图G关于R的边转发指数π(G,R)是R中路经过一条边的最大条数.图G的边转发指数π(G)是G关于任何路由选择R的边转发指数π(G,R)的最小值.符号πΔ,n表示所有顶点数为n,最大度至多为△的图中最小边转发指数.当n≥4p 1,且n()[4p [1/3(2p-1)]-1,6p]时,其中p≥1,确定了πn-2p,n的值.  相似文献   

11.
一个完全 [0 - ]单半群 S具有如下性质 :若 0≠ e∈ E(S) ,a∈ S且 ea≠ 0 ,则存在 f∈ E(S)使得 a =f ea.本文利用完全 [0 - ]单半群的这一性质以及 [0 - ]单的完全π-正则半群必是完全 [0 - ]单的这一事实 ,考察了完全π-正则半群环的单位元 ,最终得到如下结果 :设 S是完全π-正则半群 ,则 RS含单位元当且仅当 R〈E(S)〉含单位元 ,且存在 E(S)的一个有限子集 U,使得 S=SU =US.另得到一个关于完全 [0 - ]单半群的一个等价描述 :一个 [0 - ]单半群 S是完全 [0 - ]单的当且仅当 S是左π-正则的且 S包含一个非零幂等元  相似文献   

12.
用Rabinowitz全局分歧定理, 研究二阶Dirichlet边值问题结点解集的全局结构, 其中r为正参数, a: [0,1]→[0,∞)连续且允许其在[0,1]的 部分真子区间上恒为0, f: R→R在0和∞处是渐近线性的且有两个非0零点.  相似文献   

13.
定义并研究ZpZps[ξ]-的一类线性子模, 即ZpZps[ξ]上的线性斜常循环码, 其中ZpZps[ξ]和Zp[ξ]是Galois环, p是素数. 首先讨论ZpZps[ξ]线性码的生成矩阵; 其次通过对Zps[ξ]上斜常循环码生成多项式的讨论, 给出ZpZps[ξ]上斜常循环码的生成集, 并举例说明.  相似文献   

14.
考虑一类非线性三阶常微分方程边值问题{-u(3)(t)=λf(t,u(t)), a.e. t∈[0,1],u(0)=u'(0)=0, u'(1)=αu'(η)正解集的全局结构,其中 f:[0,1]×R→[0,∞)为L1-Carathéodory函数,0<η<1 且 1<α<1/η为常数。在f满足线性增长的条件下,运用Rabinowitz全局分歧定理得到其正解集的全局结构。  相似文献   

15.
用Guo-Krasnoselskii不动点定理给出半正二阶离散周期边值问题{Δ2 u(t-1)+a(t)u(t)=λf(t,u(t)),t∈[1,T]?,u(0)=u(T),Δu(0)=Δu(T)正解的存在性和多解性结果,其中λ>0为参数,[1,T]?={1,2,…,T},f:[1,T]?×[0,∞)→?连续且存在常数...  相似文献   

16.
R上无限维交换代数.研究了C[a,b]上面的半范数Np(f(x))=[∫ba|f(x)|pdx]1p(0<p<∞)与半模N∞(f(x))=maxaxb[|f(x)|]的关系,通过这种关系证明了Np(f(x))对0<p<∞不是C[a,b]上的稳定半范数.给出了C[a,b]上不是连续半模的一个实例.  相似文献   

17.
以具有直链或支链结构的溴代正丁烷、溴代异丁烷为烷基化试剂,设计合成了互为异构体的N-正丁基吡啶六氟磷酸盐([n-C4pyr][PF6])和N-异丁基吡啶六氟磷酸盐([i-C4pyr][PF6])离子液体,在配比为V甲醇:V甲苯=1∶3和V乙醇∶V甲苯= 1∶3的混合溶剂体系中,培养出了晶型完整的异构体单晶体,并通过单晶X衍射技术,确定了异构体单晶体的晶体结构。[n-C4pyr][PF6]属于单斜晶系,空间群为P2(1)/n,晶胞参数为a=2.62(3)nm, b=0.68(7)nm,c=0.72(7)nm,α=90.00(4)°,β=90.00(5)°,γ=90.00(4)°,Z=4.00,V=1.27(2)nm3,Dc=1.47mg/m3,μ=0.27mm-1,F(000)=576.00;[i-C4pyr][PF6]属于单斜晶系,空间群为P2(1)/c,晶胞参数为a=1.06(19)nm,b=0.97(18)nm,c=1.33(3)nm,α =90.00(4)°,β=113.00(3)°,γ=90.00°(4)°,Z=4.00,V=126.33(4)nm3,Dc=1.48mg/m3,μ=0.27mm-1,F(000=576.00。晶体结构分析表明:N-丁基吡啶六氟磷酸盐离子液体异构体的空间群存在一定的联系,P2(1)/n属于P2(1)/c的变型,异构化影响了阴阳离子之间的相互作用以及晶体堆积的空间网络形成,异构化对N-丁基吡啶六氟磷酸盐离子液体异构体的晶格能的影响显著,对热分解温度的影响较小;异构体的熔点相差29.10℃而凝固点相差为14.57℃,在冷却结晶过程中均出现过冷现象,进一步有效验证了其晶体学的研究结果。  相似文献   

18.
在复数域中讨论二阶迭代泛函微分方程 x″(x[r](z))=c0z+c1x(z)+…+cmx[m](z), z∈C, 的解析解,其中r,m是非负整数,c0,c1,…,cm是复值常数,并且x[i]表示x的i次迭代。在α(α表示线性化的特征值)是单位根的情形以及α在共振点附近且满足Brjuno条件的情形,给出了解析解的结果。  相似文献   

19.
设A⊆B是具有单位元的交换环的扩环, x是环B上的未定元, R:=A+xB[[ x]], S是环A的一个乘性子集。证明了若S是A的非零因子的乘性子集且对任意的s∈S,(∩snA,n≥1)∩S≠Ф,则R是S-Noether环当且仅当A是S-Noether环, B是S-有限A-模。
                相似文献   

20.
设R为k[x,y,z]的收缩且其对应收缩同态为φ. 证明了如果R的超越次数为2, 且满足下列条件之一 , 则存在p,q∈R, 使得R=k[p,q]:   1) R为inert子代数, 不含坐标, 并且φ为某多项式的梯度; 2) R为2 赋值代数.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号