关于竞赛图弧泛回路性的一类反例

设T(V,A)是p个顶点的竞赛图,若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p),则竞赛图T称为具有弧泛回路性。若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p—1),并且至少存在T的一条弧不含于T的任一p-回路中,则竞赛图T称为具有准弧泛回路性。 为了叙述方便引进下列记号: R(p)——p个顶点的正则竞赛图所组成的集合;     

一类偏向删点及顶点有限制的随机图上的相变

固定α_0∈[0,1)及β∈[0,1/2).该文引入如下随机图过程(G_t)t≥1:设在时刻1及2已存在图G_1=G_2,其中G_1的顶点为v_1,v_2且它们之间有2条边相连.当t≥3时,G_t定义如下:(i)G_(t-1)中任意顶点v不活跃的概率为α_0.顶点不活跃意味着其不能与t时刻新增加的顶点相连.此概率独立于自己以及其他顶点t-1之前的状态;(ii)以概率1-β增加一个新顶点v_t.在G_(t-1)中以概率dw(t-1)/∑vdv(t-1)选一顶点w,其中d_w(t-1)表w在G_(t-1)中的度.若w是活跃的则在v_t与w之间连1条边,否则在v_t上加个环;(iii)以概率β在G_(t-1)中删去一顶点u,其中u被选中的概率为(1-du(t-1)/∑vdv(t-1))/(n_(t-1)-1).此处,n_(t-1)是G_(t-1)的顶点个数.令N_k(t)表G_t中度为k的顶点个数.该文证明了G_t度分布的期望在2β/1-α_0=1附近存在一相变:当2β/1-α_01时,N_k(t)/t的期望是呈指数衰减的;当2β/1-α_01时,N_k(t)/t的期望是呈幂律衰减的.     

有向完美图

Gallai 和 Milgram 曾经证明,有向图 G 的所有结点可用恰好 α(G) 条互不相交的路来复盖,此处 α(G) 为图 G 的内固数.然而这个结果的好多证明都未指出存在着一最优 内固集 S 以及结点集的一个路剖分 μ_1,μ_2,…μ_k,以致对于所有 i,均有|S∩μ_i|=1.Gallai 和 Roy 曾经独立地证明,在一有向图 G 中,令 k 为一条路所能包含的最多的结点的个数,则 k 至少等于图 G 的色数γ(G).同样,我们不知道是否存在一最优色谱(S_1,S_2,…,S_k)以及一条路μ,以致对于所有的 i,均有|S_i∩μ|=1.在本文中引进了下述概念:1.有向图 G 称为α-有向完美,若对于每一最优内固集 S,均存在结点集合的一个路剖分μ_1,μ_2,…,以致对于所有的 i,均有|S∩μ_i|=1(且此性质对 G 的任一子图亦成立).2.一有向图 G 称为 γ-完美,若对于每一最优色谱 (S_1,S_1,…S_k),均存在一条路 μ,以致对于所有 i,均有|μ∩S_i|=1(且此性质对 G 的每一子图亦均成立).3.一长度为2k+1的奇圈系由2k+1条弧 u_1,u_2,…,u_(2k+1) 所给出,并从而确定了一个有2k+1个结点的序列 x_1,x_2,…,x_(2k+1).一条弦,可以是 G 的一条弧,它联结在以上叙列中不相继的两个结点,或者是 G 的一条弧,它平行上述2k+1条弧中的一条弧.一个奇圈称为反有向的,若i)其长度>3,ii)最长     

竞赛图具有弧泛回路性的一个充分条件

关于竞赛图的弧泛迴路性问题,Alspach证明了正则竞赛图具有此性质.朱永津、田丰证明了若竞赛图 T 中任意一个弧(v,v_0)都满足条件 d~+(v_0)+d~-(v)≥p-2,这里 p 为 T 的顶点数,则当 p≥7时,T 中过任一弧存在迴路系列 C_4,C_5,…,C_p.本文提出并证明了若 T 满足以下条件:当 d~+(v)<1/2(p-1)时,在 v 的外邻集 O(v)中有一点 u,d~+(u)≥1/2(p-1);当 d~+(v_1),d~+(v_2)<1/2(p-1)时,有 u_1,u_2∈O(v_1)∪O(v_2),d~+(u_1),d~+(u_2)≥1/2(p-1),且对入次亦满足相应的条件,则当 p≥9和最小次数δ≥4时,过 T 的每一个弧存在迴路系列 c_6,c_7,…,c_p.此充分条件不要求顶点次数的正则性和几乎正则性,对 T 的不正则度 q=(?)|d~+(v)-d~-(v)|一般来说也没有限制.     

关于点集拓扑学中的一个定理

若 A\cup B≠D(c),则存在(c,v_0)∈D(c),使\bar{\lambda}(v_0)a.故存在 n_0,使当 n≥n_0时\bar{\lambda}(v_0)<β_n,\underline{\lambda}(v_0)>α_n。利用常规证法(参见[1]中p.122)可知,必存在R~1×X 中的有界开集 U,满足 E(V_0)\subset U,\partial D=\phi,\bar{U}(α_n_0,β_n_0)×X。由 D 的定义知,存在{n}的子列{n_k}及 Z_n_k∈\mathcal{C}_n_k,使使 Z_n_k→(c,v_0)。不失一般可设诸 Z_n_k 均属于 U。由(2)式及\mathcal{C}_{nk}的连通性,并注意到\bar{U}(α_n_0,β_n_0)×X,可知当 n_k≥n_0时有\mathcal{C}_{nk}\cap \partial U\not=\phi,取 y_n_k∈\mathcal{C}_{nk}\cap \partial U,则{y_n_k|k=1,2,…}是列紧的。故存在{y_n_k}的子列{y~n_k_i}及 y~*∈\partial U,使 y~n_k_i→y~*。显然y~*∈D,故 y~*∈\partial D \cap D,此与\partial U\cap D=\phi矛盾。所以(5)式成立。     

弧哈密顿竞赛图的一个性质

§1.引言 设T是有p个点的一个竞赛图,T称为是弧k回路的,若T的每一条弧在一个长度为k的回路上.T也称为是弧哈密顿的,若T是弧p回路的.在第二次全国图论学术交流会上,邵品琮和张存铨提出下列猜想:     

C2(4,k) 中的强支撑可迹图

设2≤h≤3,l0,k≥0是整数,C_h(l,k)是由h-边连通简单图组成的集合,图G∈C_h(l,k)当且仅当对图G的任意一个二边割或三边割X,图G-X的每个分支都至少有︱V(G)-k︱/l个点.设e=u_1v_1和e'=u_2v_2是图G的两条边.若e≠e',G(e,e')是将图G中的边e=u_1v_1和e'=u_2v_2分别用路u_1v_ev_1和u_2v_e'v_2替换得到的图(其中,v_e,v_e'是不在V(G)中的两个新的点).若e=e',G(e,e')是将图G中的边e=u_1v_1用路u_1v_ev_1替换得到的图,也记作G(e).若对任意的e,e'∈E(G),G(e,e')都有支撑(v_e,v_e')迹,则称图G是强支撑可迹的.作者证明了,若图G∈C_2(4,k)且|V(G)|5k,则要么图G是强支撑可迹图,要么存在e,e'∈E(G),使得G(e,e')可以收缩成一个有限图类F中的图.当k=4时,F被完全确定了.     

关于亚纯函数的奇异方向

本文讨论了无穷级亚纯函数结合导数涉及重值的奇异方向,得出如下结果:定理 设f(z)为|z|<∞中的亚纯函数,其级ρ(r)为熊庆来无穷级,则必存在从原点发出的半直线 B:arg z=θ_0(0≤θ_0<2π)具有如下性质:对于任意的正整数 l,p,k;任意的正数 ε 及一切有穷复数 α,β(β≠0),若((2+1/k)(k+2)-2)/l+((2+2/k)(k+1))/p<1,则有(?)(log{(?)_(l-1)(r,θ_0,ε,f=α)+(?)_(p-1)(r,θ_0,ε,f~((k))=β))/(ρ(r)logr)=1     

包装{(p,p-1),(p,p)}图对和 Slater 问题

设 G 是一个简单无向图.V(G),E(G)分别表示 G 的顶点集和边集.(?)表示 G 的补图.我们以 S_(?) 表示 n 1阶星图 k_(1,n-1).称 G 是(p,p—k)图,如果|E(G)|=|V(G)|—k.称|V(G)|为图 G 的阶.设 G_1,G_2是同阶图,(?)_1是 V(G_1)到 V(G_2)的一个双射,(?)_2是 V(G_2)上的一个置换,我们用(?)_2(?)_1表示 V(G_1)到 V(G_2)的双射,其作用为     

对称QL算法对角元的收敛条件

文[1]指出,在QL算法收敛性讨论中,仅有β_1~(K)→0并不能保证α_1~(k)收敛,并证明在加上条件:|α_1~(k)-σ_k|μ0”后,可确保α_1~(k)趋于T的某个固定特征值。本文首先对QL算法收敛性给出了一个精确的定义,然后给出一个与[1]不同的确保收敛的条件: “若{σ_k}_k=1~∞极限存在且β_i~(k)→0,则有α_i~(k)→λ_i(j=1,2,…,m)”条件“{σ_k}_k=1~∞极限存在”与“α_1~(k)-σ_k|→0”互不包含,在具体应用中,对后者无法判别(如[3]中给出的NS位移)或不成立的某些场合,前者具有独到的优点。     

积图P_m×C_(4n)的k-优美性

是一一映射。(参见[1、2]) 简单图G_1=(V_1,E_1)与G_2=(V_2,E_2)的积图G=G_1×G_2=(V,E)指的是:V=V_1×V_2,而点(v_1,v_2)与(ν′_1,v′_2)间有边且或且。 本文讨论积图P_m×C_(4n)的k-优美性,这里m,n,k皆为正整数,而P_m表示m个点的链,C_(4n)表示4n个点的简单回路。     

浅议数学归纳法及教学中易出现的问题

皮亚诺公理的第 5条性质 :任意一个正整数集合 ,如果包含 1 ,并且假设包含x ,也一定包含它的后继x + 1 ,那么这个集合包含所有的正整数 .这条性质就是数学归纳法的依据 ,通常称为数学归纳法原理 .这一原理可以用数学符号来表示 :数学归纳法原理 :如果S是正整数集合N+的一个子集 ,且满足 :① 1∈S ;　　②若k∈S ,则k + 1∈S ,那么S =N+.根据数学归纳法原理 ,可以得到数学归纳法 :设 p(n)是一列与正整数有关的数学命题 ,如果满足 :①p(n)当n =n0 (n0 是使 p(n)正确的最小正整数 )时正确 ,即 p(n0 )正确 ;②在假设 p(k) (k≥n0 ,k∈N+)正…     

带非光滑核的多线性Marcinkiewicz积分的加权界

我们引入了带非光滑核的多线性Marcinkiewicz积分算子.设p_1,…,p_m∈(1,∞)和p∈(0,+∞)满足1/p_1+…+1/p_m=1/p,记P=(p_1,…,p_m),又设向量权ω=(ω_1,…,ω_m)∈A_p和v_ω=Π_(k=1)~mω_k~(p/pk),得到了Marcinkiewicz积分算子从L~(p_1)(ω_1)×…×L~(p_m)(ω_m)到L~p(v_ω)的常数界.     

CLASSIFICATION OF POSITIVE SOLUTIONS TO A SYSTEM OF HARDY-SOBOLEV TYPE EQUATIONS

In this paper, we are concerned with the following Hardy-Sobolev type system{(-?)~(α/2) u(x) =v~q(x)/|y|~(t_2) (-?)α/2 v(x) =u~p(x)/|y|~(t_1),x =(y, z) ∈(R ~k\{0}) × R~(n-k),(0.1)where 0 α n, 0 t_1, t_2 min{α, k}, and 1 p ≤τ_1 :=(n+α-2t_1)/( n-α), 1 q ≤τ_2 :=(n+α-2 t_2)/( n-α).We first establish the equivalence of classical and weak solutions between PDE system(0.1)and the following integral equations(IE) system{u(x) =∫_( R~n) G_α(x, ξ)v~q(ξ)/|η|t~2 dξ v(x) =∫_(R~n) G_α(x, ξ)(u~p(ξ))/|η|~(t_1) dξ,(0.2)where Gα(x, ξ) =(c n,α)/(|x-ξ|~(n-α))is the Green's function of(-?)~(α/2) in R~n. Then, by the method of moving planes in the integral forms, in the critical case p = τ_1 and q = τ_2, we prove that each pair of nonnegative solutions(u, v) of(0.1) is radially symmetric and monotone decreasing about the origin in R~k and some point z0 in R~(n-k). In the subcritical case (n-t_1)/(p+1)+(n-t_2)/(q+1) n-α,1 p ≤τ_1 and 1 q ≤τ_2, we derive the nonexistence of nontrivial nonnegative solutions for(0.1).     

具有大稳定域的线性多步方法

§1.引言 解常微分方程初值问题:的线性k步方法为 sum from j=0 to k (α_jy_(n j)=h sum from j=0 to k (β_jf_(n j),(2)其中α_0~2 β_0~2≠0,α_k≠0.当β_k≠0时,(2)为隐式k步法;当β_k=0时,(2)为显式k步法. 若将(2)应用于单个方程 y′=λy,Reλ<0,则得差分方程 ρ(E)y_n=μσ(E)y_(?),μ=λh,     

构建最小k 重控制集的概率算法

点集D ⊆ V (G) 称为图G 的k 重控制集, 如果D 满足V (G) - D 中任意结点在D 中至少有k 个邻居. 在无线网络中, 最小k 重控制集(MkDS) 用以构建健壮的虚拟骨干网. 构建虚拟骨干网是无线网络中最基本也是最重要的问题. 在本文中, 我们提出一种快速的分布式概率算法来构建k重控制集. 我们构建的k 重控制集的期望大小不超过最优解的O(k²) 倍. 算法的运行时间复杂度为O((Δ logΔ+log log n)n),其中Δ = max{|D(p)|}, D(p) 是以p 为中心半径为1 的圆盘中的结点, 最大值的比较范围是给定集合中所有的p 点.     

交替码的最小距离下限的扩张及其译码

在[1]中定义如下的一般交替码:令(?)(1.1)这里所有元素∈GF(q~m),p_1,p_2,…,p_n 为非0;α_1,α_2,…,α_n 各不相同;B 为非奇异阵,且 mt相似文献   

k—full整数的分布（Ⅱ）

设k≥2是固定整数。自然数n称为k-full,如果对n的任一素因子p,均有p~k|n。以A_k(x)表示不超过x的k-full整数的个数,则可将A_k(x)写成如下形式: 这里γ_(i,k)(0≤i≤k-1)是非零常数,△_k(x)A_k(x)之误差项,本文在Riemann猜想成立的假设下证明了下结面论: 定理设。若Riemann猜想成立,则有:对k≥10成立。对2≤k≤9则得到了关于△_k(t)dt之渐近估计,其误差项为O(x_k~(a′+2))(ε>0)。     

关于超空间连通性的一个注记

本文回答了由E.Klein与A.C.Thompson在其著作《Thery of Correspondences》中提出的一个问题。主要结果是:若X是一度量空间,且在X中存在一条弧,则在P(X)中有一条序弧α,满足条件i)α(0)是连通子集;ii) (?)α(t)是不连通的。     

常系数线性齐次递归式的一般解公式

本文给出常系数线性递归式 a_n=α_1a_(n-1)+α_2a_(n-2)+…+α_pa_(n-p),a_0=c_0,a_1=c_1,…,a_(p-1)=c_(p-1)的一般解公式 a_n=sum from k=0 to p-1(sum from i=k to p-1 c_iα_(p-i+k))F_(n-p-k)(n≥p),其中(?)