共查询到19条相似文献,搜索用时 93 毫秒
1.
有向图D=(V,A)的核K是顶点集V的一个子集,其中K中任意两点在D中均不相邻,并且对V\K中任意一个点v,都存在K中的一个点u,使得(v,u)是D中的一条弧.一般有向图核的存在问题是NP-完全的.Bang-Jensen和Gutin在他们的著作[Digraphs:Theory, Algorithms and Applications, London:Springer-Verlag, 2000]中提出公开问题(Problem 12.3.5):刻画有向循环图核存在性.本文研究了几类特殊有向循环图核的存在问题,并给出了Duchet核猜想(对任意一个不是有向奇圈的无核有向图,都存在一条弧,使得删除这条弧所得到的图仍然是无核的)的一类反例. 相似文献
2.
设D是一个有向伪图,如果对于任意两个点u和v,D有一条生成(u,v)-路或一条生成(v,u)-路,则D是弱哈密尔顿连通的;若既存在一条生成(u,v)-路又存在一条生成(v,u)-路,则D是强哈密尔顿连通的.一个有向伪图D的线图L(D)是D的弧集作为其点集,对于任意两个点a,b∈A(D),(a,b)是L(D)的弧当且仅当存在D中的点u,v,w满足a=(u,v)并且b=(v,w).本文刻画了两类有向伪图T及T’,使得L(D)是弱哈密尔顿连通的当且仅当D∈T,并且L(D)是强哈密尔顿连通的当且仅当D∈T’. 相似文献
3.
广义de Bruijn和Kautz有向图的距离控制数 总被引:1,自引:0,他引:1
对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?).图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者.本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件.从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= .在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= . 相似文献
4.
如果存在正整数k使得对于D中任意两点u和v(允许u=v),在D中都有从u到v的长为k的有向途径,则称有向图D是本原的.给有向图的每条弧赋以符号+1或者-1得到的图S称为带号有向图.如果带号有向图S中包含SSSD途径对,即包含两条有相同的起点,相同的终点,相同的长度,并且有不同的符号的途径对,则称S是不可幂的.在本文中,我们将Lewin M提出的lewin数的概念从本原有向图推广到本原不可幂带号有向图,给出了本原不可幂带号有向图S的lewin数l(S)的若干上界,并提出了一个公开问题. 相似文献
5.
设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界. 相似文献
6.
有向循环图强连通度的下界 总被引:1,自引:0,他引:1
为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)定义如下: 相似文献
7.
对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界. 相似文献
8.
设D=(V,A)为简单有向图,其中V=V(D)和A=A(D)分别表示D的顶点集合和弧集合。x,y∈V(D),xy∈A(D)表示D中从x到y的弧。有向图D称为强连通的如果对D中任何两顶点u和v,D中有一条从u到v的有向路,也有一条从v到u的有向路。 相似文献
9.
设有向图 D_1=(V_1,A_1),D_2=(V_2 A_2).称有向图 D_2:D_2=(V,A) 为 D_1,D_2的半强积,如果 V=V_1×V_2,A={((u_1,v_1),(u_2,v_2))|u_1=u_2且(v_1,v_2)∈A_2或者(u_1,u_2)∈A_1且(v_1,v_2)∈A_2}. 相似文献
10.
《应用数学学报》2016,(2)
本文利用多重插入法,对局部内(外)半完全有向图及其扩张有向图的可迹性作了讨论.首先,证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}满足d(x)≥n-1,d(可)≥n-2,或d(x)≥n-2,d(y)≥n-1,则D是可迹的.同时还证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}有min{d~+(x)+d~-(y),d~-(x)+d~+(y)}≥n-1,D是可迹的.其次,证明了n阶连通的扩张局部内半完全有向图D,如果任意不相邻的控制点对{u,v}和任意不相邻的受控点对{x,y}同时满足(1)d(u)≥n-1,d(v)≥n-1;(2)d(x)≥n-1,d(y)≥n-2或d(x)≥n-2,d(y)≥n-1,则D是可迹的.最后,利用逆图的性质把这三个结论推广到n阶连通的局部外半完全有向图与n阶连通的扩张局部外半完全有向图中. 相似文献
11.
In this paper,the automorphism group of G is determined,where G is a 4 × 4 upper unitriangular matrix group over Z.Let K be the subgroup of AutG consisting of all elements of AutG which act trivially on G/G,G /ζG and ζG,then (i) InnG ■ K ■ AutG;(ii) AutG/K≌=G1×D8×Z2,where G1=(a,b,c|a4=b2=c2=1,ab=a-1,[a,c]= [b,c]=1 ;(iii) K/Inn G≌=Z×Z×Z. 相似文献
12.
考虑了具有结构阻尼和外阻尼的非自治非线性粘弹性梁方程的拉回D_δ,E_1-吸引子.首先利用Galerkin方法,证明了在齐次边界条件和初始条件下系统在V×H和D(A)×V中的整体解的存在唯一性;其次通过先验估计,证明了系统的拉回吸收集的存在性;最后证明了系统满足拉回D_δ,E_1-条件(C),从而证明了系统的强拉回D_δ,E_1-吸引子的存在性. 相似文献
13.
14.
本文讨论积分方程组(?)解的性质,其中G_α是α阶贝塞尔位势核,0≤β〈α(n-α+β)/n,1/(q+1)+1/(r+1)〉(n-α+β)/n,1/(r+1)+1/(p+1)〉(n-α+β)/n.我们用积分形式的移动平面法证明上述积分方程组的正解是径向对称且单调的. 相似文献
15.
若G1和G2是两个图,G1和G2的Kronecker图定义为V (G1×G2)= V (G1) × V (G2 E(G1 × G2)= {(u1,v1)(u2,v2)。在本文中,我们计算了p-部完全图 m1,m2,...,mp 和完全图Kn 的Kronecker积的顶点参数,m1 ≤ m2 ≤ ... ≤ mp,2 ≤ p ≤ n, and n ≥ 3 ,扩展了Mamut和Vumar的相关结论[Inform. Process. Lett. 106(2008)258-262]. 相似文献
16.
研究了一类新的非线性延迟积分不等式φ(u(t))≤(n_1(t)+∫_o~(a(t)) f_1(s)w_1(u(s))ds)(n_2(t)+∫_o~t f_2(s)w_2)(u9(s))ds),t∈R_+得到了新的结论,推广了已有的若干结果.并举例说明其应用. 相似文献
17.
重新确定了广义超特殊p-群G的自同构群的结构.设|G|=p~(2n+m),|ζG|=p~m,其中n≥1,m≥2,Aut_cG是AutG中平凡地作用在ζG上的元素形成的正规子群,则(i)若p是奇素数,则AutG=〈θ〉×Aut_cG,其中θ的阶是(p-1)p~(m-1);若p=2,则AutG=〈θ_1,θ_2〉×Aut_cG,其中〈θ_1,θ_2〉=〈θ_1〉×〈θ_2〉≌Z_(2m-2)×Z_2.(ii)如果G的幂指数是p~m,那么Aut_cG/InnG≌Sp(2n,p).(iii)如果G的幂指数是p~(m+1),那么Aut_cG/InnG≌K×Sp(2n-2,p),其中K是p~(2n-1)阶超特殊p-群(若p是奇素数)或者初等Abel 2-群.特别地,当n=1时,Aut_cG/InnG≌Z_p. 相似文献
18.
令{β(s),s≥0}表示R~3空间中的标准Brown运动,|W_r(t)|表示由{β(s),s≥0}产生的观察至时间t且以r为半径的Wiener sausage的体积.由中心极限定理可知,(|W_r(t)|-E|W_r(t)|)/(?)弱收敛至正态分布.本文研究这种情况下的中偏差. 相似文献
19.
通过θ-图中除了含有一个4圈的θ-图外,其余的θ-图都是邻接谱唯一图的有关结论,研究了几类特殊θ-图的Laplacian谱唯一性问题.即:θ-图θ_(s_1,s_2,s_3)(|s_i-s_j|≤2,1≤i≤3)、圈长为3或4的θ-图以及θ-图θ_0,u,v(u+v=1(mod 2)). 相似文献