某些广播图的构作

<正> 1.引言 广播图G的广播方式见文,在讨论广播问题时,我们使用下述定义: 定义1 图G中某结点u的广播时间t(u)是完成以u为源结点的广播所需要的最少单位时间数。 定义2 图G的广播时间t(G)是指G中结点广播时间的最大值。即 定义3 若n阶广播图G满足t(G)=[logn],则称G为n阶合格广播图。 定义4 若n阶合格广播图G的任一真生成子图G′,有t(G′)>t(G),则称G为n阶极小     

时变网络中零等待时间最短路问题的一个对偶算法

时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点t,图G中的每条弧(i,j)∈A都附有两个参数:弧的传送时间b(i,j,u)和弧的传送费用c(i,j,u),它们都是在弧的顶点i上的出发时间u的函数.找出从源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.假设除源点外,在其它任何顶点都不能等待,b(i,j,u)是满足u b(i,j,u)≥0( (i,j)∈A,u=0,1,…,T)的任意整数,c(i,j,u)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.     

超立方体网络广播容错路由算法

研究了具有大量错误结点的超立方体网络中的广播容错路由算法.假定Hn是一个局部3维子立方体连通的n维超立方体网络,并且每一个基本的3维子立方体中分别最多有1个和2个错误结点,从理论上证明了在最坏情况下基于shouting广播通信模式的广播容错路由算法分别经过最多1.5(n-1)和2(n-1)时间步,就可以将源结点的信息广播到Hn中的所有正确结点中;通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n+1,支持了理论分析结果.     

一维非线性抛物型方程组具有初值的空间周期解问题

§1 引言和预备引理 考虑如下的具有初值的一维非线性抛物型方程组的空间周期解问题。(?)/((?)t)u_j(t,x)=a_i(t) e~2/((?)x~2u)(t,x) f_j(1,x,u_j(1,x))……,u_R(1,x),(?)/((?)x)u_j(t,x),……,(?)/((?)x)u_n(t,x))(1)(t,x)(?)〕0,T〔×R_s R=〕-∞,∞〔,j=f,……,n,u_j(0,x)=(?)_1(x),x(?)R,(2)u_j(t,x 2A)=u_j(t,x),对一切(t,x(?)0,T〔×R,j=1,……n (3)其中a_(?)(t)是已知的正值连续函数,T 是给定的正数,曲(?)(t,x,u,u~*)作为x 的函数(t,u,u~*)     

最小广播图研究

广播是计算机网络上信息的传播过程。在此过程中,一个结点将信息传给其它所有结点。本文采用结点最大度数分段法,给出对B(n)上界的新估计;确定了B(19)的值;同时给出了B(20),B(28),B(34)的新上界值。     

多端口模型中的链式广播算法分析

根据广播黑盒子的分类,分析了多端口模型中多消息链式广播算法,深入探讨了算法的理论基础和理论模型;重点研究链式广播算法的时间复杂度,通过与k树算法性能的对比,说明该算法是一种更接近最优广播周期的算法.     

树的D(r)-点可区别边染色

图G的一个正常边染色是指对G的每条边分配一种颜色使得任意相邻的两条边的颜色不同.图G的正常边染色f称为D(r)-点可区别边染色,如果对G中任意两个距离不超过r的顶点u,v∈V(G),有C'(u)≠C'(v),其中C'(x)={f(xy):xy∈E(G)}.图G的D(r)-点可区别边色数是指对图G进行D(r)-点可区别边染色所需要的最小色数,记为'r(G).文章讨论了树的D(2)-点可区别边染色及D(3)-点可区别边染色问题,通过逐层染色的方法,得到了树的D(2)-和D(3)-点可区别边色数的上界,并给出了线性时间的染色算法.另外,通过边染色与全染色的关系,得到了树T的D(3)-点可区别全色数不超过Δ(T)+3,D(2)-点可区别全色数不超过Δ(T)+2.     

二阶耦合拟线性抛物组边值问题的周期解

本文利用有限维正交投影方法证明了下述边值问题u_j1-a_j(u_j)_(xx)+σ_ju_j+f_j(t,x,u)=g_j(t,x),(t,X)∈G=(0,π)×(0,π),-α_(j1)u_(jx)+β_(j1)u_(j)|_(x=0)=0α_(j2)u_(jx)+β_(j2)u_(j)|_(x=π)=0 j=1,…,n在假设条件(4)-(6)成立时,于少有一周期解u_j∈W_1~(2,1)(G)。当a_j(u_j)=u_j时,文[7]讨论了此种情形,但是我们得到的结果u_j∈w_2~2(G)且u_(jx)∈W_1~(2,1)(G),比文[7]的结果强得多。     

不具Lipschitz条件的Browder变分不等式解的Ishikawa迭代算法

在Hilbert空间H中,得到映象T:H→H不具Lipschitz连续性条件的Browder变分不等式(Tu—f,y—u)≥φ(u)-φ(y),任意y∈H的带有误差的Ishikawa迭代算法;结果改进和推广了文献中某些已知的结果．     

时变网络最大流问题的过剩流量收缩算法

时变最大流问题是最大流问题的一个推广．设图G=（y,A）是一个有向图且有唯一的发点s和收点P．图G中的每条弧（i,j）∈A都带有两个参数：弧上流的传送时间b（i,j,u）和弧的容量f（i.j.u）,它们都是时间u的函数．时变最大流问题就是找出从s到P满足容量约束的最大流,并要求此最大流的传送时间不能超过一个预先给定的时间限制T.假设：除发点外,流在其他任何顶点都不能等待;b（i.j.u）是正整数;l（i.j.u）是任意的非负整数．提出了该问题的一个过剩流量收缩算法,并讨论了这个算法的复杂度．最后,给出了一个数值算例。     

BLOW-UP OF A CLASS OF SEMILINEAR PARABOLIC VARIATIONAL INEQUALITIES

In this paper we study the blow-up behavior for a class of semilinear parabolic variational inequalities;whereK = {u ∈L~2(0,T;H_0~1(Ω))|u(x,t)≥ψ(x) a. e. (x,t) ∈Ω×(0,T), u(x,0) = (x)},andis a uniformly elliptic operator.We prove the following main theorem.Theorem Let u(x,t) be a local solution of problem (I),u∈C(0,T;H~2(Ω)∩H_0~1(Q)),u_i∈L~2(0,T;L~2(Ω)), and following conditions are satisfied.(1) There exists a continuously differentiable function G(x,s) and a positive number α,such that     

R~n上超线性椭圆型方程组整体极小解的存在性

本文考虑下列超线性椭圆型方程组-△u_i=f_i(x)g_i(u_1,u_2…,u_n)x∈R~n i=1,2,…,n 的整体极小解的存在性。所谓极小极是指 u=(u_1,u_2,…,u_n),u_i∈C_(loc)~(2+α)(R~n),sup(1+|x|)~(n-2)|u_i∞|<+∞且满足对任何φ∈C_0~∞(R~n),∫R~n▽u_i▽φdx=integral from x∈R~n R_nf_i(x)g_i(u_1,u_2,…u_n)φdx。本文用拓扑度方法证明了,在 f_i(x)、g_i(u)满足一定条件下,方程组存在正的整体极小解。     

具有间断初值和边值的一维渗流方程的哥西问题和第一边值问题

当u_i(i=0,1,2)是有界连续函数时,[1]讨论了哥西问题,第一、二边值问题以及解的若干性质。本文是[1]的推广。 广义解是这样定义的:u(t,x)在G(R,D)内部连续,0≤u(t,x)≤(?)_2,在u_i(i=0,     

拟线性椭圆方程在RN上的结点径向解的存在性

研究了RN(N≥2)上的拟线性椭圆方程-div(|u|p-2u) |u|p-2u=f(|x|,u),x∈RN,u∈W1,p0(RN)的具任意多个结点的径向解的存在性,其中1相似文献   

定时截尾试验Weibull分布参数的近似置信区间

该文研究了Weibull分布大样本定时截尾试验,给出了总试验时间的极限分布,在给定任一参数的条件下,利用一种全新的途径得到了一另一参数的近似置信敬意 ,设产品寿命x服从Weibull分布W（λ,b),对受试产品xi进行定时时间t0的截尾试验,得到观察数据Si=min(xi,t0)。由于总试验时间S=S1 S2 … Sn近似服从正态分布：S-E（S）/（VarS)^1/2=√n(S-u)/(2u-u^2)^1/2∞N(0,1),由此可以得到参数（u,v)的联合置信域D：u≥1 β^2/2β^2(u-S/1 β^2)^2 S^2/2(1 β^2) 。由于Jacobi变换地列式|J|≠,因此区域D的任意一点(u,v)都能找到唯一的点(λ,b)与之对应,对于任一给定的λ,参数曲线u=u(b),v=v(b)与区域D的边界曲线正好有2个交点,解方程:(1 β^2)u^2(b)-2S.u(b)-2β^2v(b) S^2=0,得到了2个根b1(λ),即为参数λ的置信水平1-α的置信区间:b1(λ)≤b≤b2(λ).     

一类双边退缩的抛物型方程的Cauchy-Dirichlet问题——解的唯一性和极值原理

文[1]中讨论了下述Cauchy-Dirichlet问题. (I) (c(u))t=(a(u)u_x)_x+(b(u))_(xt) 在Q_r中 u(0,t)=0,u(1,t)=2 0相似文献   

退缩抛物型方程解的存在性与爆破

分析了退缩抛物型方程ut=a(u)(△u b(u))的初边值问题，证明了当a(u),b(u)满足一定的条件时方程解的存在性，且方程解在有限时刻T爆破，给出了T的一个上界。     

构造二叉树的一个算法

给出一个算法，该算法输入一棵二叉树的前序遍历和中序遍历的结点序列，构造出该二叉树，该算法具有Ｏ（ｎ）时间复杂度，是解决该问题的最优算法，其中ｎ为二叉树的结点数     

Positive Solutions of Four-order Dierence Equations with Two Point Boundary Value Problems

Positive solutions of fourth-order dierential equations withtwo point boundary value problems are investigatedin[4,6].Inthis paper we investigate a similar problemfor dierence equations.Wedenote byZthe set of all natural numbers.Fora,b∈Z,a相似文献   

关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.