(n,k)-排列图的条件连通度(英文)

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R~l-连通度,记为k~l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k~l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.     

几族3-优图

一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 .     

自然数集的分拆及其表示函数

令N表示全体非负整数的集合.对给定的集合A C N及n∈N,令R_1(A,n)表示方程n=a+a',a,a'∈A的解的个数.令R_2(A,n)和R_3(A,n)分别表示方程n=a+a',a,a'∈A在条件aa'和a≤a'下解的个数.一个有趣的问题是:给定i∈{1,2,3},确定所有非负整数集合对(A;B),使其表示函数R_i(A,n)及R_i(B,n)最终相等.文章讨论了相关问题.     

五点八边图的完美T(G)-三元系

设G是Kn的子图.在G的每边外添加一点,将该边扩展为一个3长圈,且所添加的点两两不同,均异于G的诸顶点,这样得到的图形被记为T(G).如果3Kn的边恰好能够分拆成与T(G)同构的一些子图,则称这些子图构成一个n阶的T(G)-三元系.进而,若此分拆的全体内部边又恰构成Kn中全部边的一个分拆,则称这个T(G)-三元系是完美的.对于所有使得完美T(G)-三元系存在的正整数n的集合称为完美T(G)-三元系的存在谱.对于K4的所有子图及K5的7边以下子图G,其完美T(G)-三元系的存在性问题已经在一系列文章中被完全解决.本文将对不含孤立点的全部五点八边图G,确定完美T(G)-三元系的存在谱.     

交叉立方体网络的反馈数

对于简单图G=(V,E),顶点子集F■V,如果由V\F导出的子图G′= (V\F,E′)是不含圈的,则称F是图G的一个反馈点集.点数最少的反馈点集称图的最小反馈点集,最小的点数称为反馈数.文章给出了交叉立方体网络的一个等价定义,用递归的方法构造出交叉立方体网络的诱导树,证明了诱导树的阶数Fibonacci数,进而得到叉立方体网络反馈数的上下界.     

基于一个球的模式分类方法的改进

针对一个球的模式分类(Single Sphere Pattern Classification(SSPC))方法中选取参数C比较困难的问题,提出一种改进的分类方法υ-SSPC.这种方法通过引入一个具有明确物理意义的参数υ,即υ是间隔错误样本占所总样本点的分额的上界,是支持向量的个数所占总样本点数的分额的下界,使参数可以灵活地根据实际问题的精度要求来选取.从而可以快速选取最有效的参数,提高分类预测的精度.     

树状网络上的Web代理服务器最优放置问题

一般网络上Web代理服务器(Web proxy)最优放置问题是一个NP困难问题.此文讨论树状网络上的最优放置问题,改进了已有结果,得到了一个时间复杂度为O(nhk)的多项式时间算法,这里n为网络结点数,h为树的高度,而k为要放置的代理服务器个数.     

e≤2(n-2)条件下的3-优图

记S_3(G)为图G所含有的连通的三结点导出子图的个数。图G称为3-优图,若对任何同点同边数的图H有S_3(G)≥S_3(H),3-优图在网络可靠性综合中起着重要作用。本文给出了在e≤2(n-2)条件下3-优图的刻划,其中n为结点数,e为边数,从而解决了文献[1]结论中提出的问题。     

禁用C4的IC-可平面图中Ck的最大个数

给定图G和H,如果图G不包含图H作为子图,则称图G是禁用H的.用ex_ICP(n,F,H)表示在所有禁用H且顶点数为n的IC-可平面图中,含与F同构的子图的最大个数.本文证明了对任意的k≥5,当n充分大时,有ex_ICP(n,C_k,C₄)=Θ(■).     

Sidon空间和循环子空间码的构造

本文首先给出Sidon空间和Sidon集的构造,用这些Sidon空间我们构造一些码字个数是τ·(q~n-1)/(q-1)并且最小距离是2k-2的循环子空间码,其中τ是一个正整数.进一步,我们给出码字个数是2τ·(q~n-1)/(q-1)并且最小距离2k-2的循环子空间码.     

顾客为子树结构的树上反中心选址问题

顾客为子树结构的树上反中心选址问题是在树T上寻找一点(位于顶点处或在边的内部),使得该点与子树结构的顾客之间的最小赋权带加数距离尽可能地大.给出了该问题的一个有效算法,其时间复杂度为O(cn+sum from j=1 to m n_j),其中n_j为各子树T_j的顶点个数,c为不同的子树权重个数,n为树的顶点数.     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

路与完全图的笛卡尔积图和广义图K(n,m)的关联色数

Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数.     

匹配可扩图的结构

设G是一个有限的简单连通图。D（G）表示V（G）的一个子集，它的每一个点至少有一个最大匹配不覆盖它。A（G）表示V（G）-D（G）的一个子集，它的每一个点至少和D（G）的一个点相邻。最后设C（G）=V（G）-A（G）-D（G）。在这篇章中，下面的被获得。⑴设u∈V（G）。若n≥1和G是n-可扩的，则（a)C(G-u)=φ和A（G-u)∪{u}是一个独立集，（b)G的每个完美匹配包含D（G-u)的每个分支的一个几乎守美匹配，并且它匹配A（G-u)∪{u}的所有点与D（G-4）的不同分支的点。⑵若G是2-可扩的，则对于u∈V（G），A（G-u）∪{u}是G的一个最大障碍且G的最大障碍的个数是2或是│V(G)│.⑶设X=Cay(Q,S),则对于u∈Q,(a)A(X-u)=φ=C（G-u)和X-u是一个因子临界图，或（b)C(X-u)=φ和X的两部是A（X-u)∪{u}和D（X-u)且│A(X-u)∪{u}│=│D(X-u）│。⑷设X=Cay(Q,S),则对于u∈Q，A（X-u)∪{u}是X的一个最大障碍且X的最大障碍的个数是2或是│Q│。     

色多项式的显示公式

本文利用完全图K_n恰有k个分支S~((n))={K_i∶1≤i≤n}-因子个数N(K_n,k)及第二类Stirling数S(n,k)之间关系,导出图的色多项式的显示公式刻画,并给出几类色多项式及用Stirling数表示的完全i部图的色多项式的显式公式。     

广义Frame与广义Frame的商

本文将frame、frame同态、商frame与核的概念在范畴意义下作推广,并且证明Frame范畴是广义Frame范畴的反射子范畴.进而讨论了一个广义frame A的商与A上核函子之间的关系.特别地,我们证明了A上全部核函子所构成的范畴N(A)是一个广义frame.     

恒同映射类的最少不动点数

<正> §1.引言设 K 是一个连通的有限的单纯复形,|K|表示其多面体,并且 f:|K|→|K|是恒同映射类中的任一映射,即 f(?)1.用Φ(f)表示 f 的不动点集,并用“个数(Φ(f))”表示Φ(f)中点的个数,即 f 的不动点的几何个数.当 f 遍历恒同映射类,个数(Φ(f))的下确界,即 K 的恒同映射类的最少不动点数,记作 m(K).已经证明(见[4]定理2或[2]定理1.4):如果 K 是二维连通的,则 m(K)=1或0,按照 K 的示性数 x(K)≠0或=0.对     

一类图设计的构造

设Kv是一个v点完全图,G是一个有限简单图,Kv上的一个图设计G-GD(v)是一个对子(X,B),其中X是Kv的顶点集合,B是Kv的一些与G同构的子图(称为区组)的集合,使得Kv的任意一条边恰出现在B的一个区组中．文中讨论的简单图是C(r)10,即带有一条弦的10长圈(含有11条边),其中r表示弦的两个端点之间的顶点个数,1≤r≤4．给出了C^（r）10-GD(v)的存在谱：v=0,1(mod11)且v≥11．     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

新题征展(23)

A.题组新编1 .设集合 M ={3,4,5},N ={6 ,7,8,9,1 0 }.( 1 )映射 f:M→ N ,使对任意的 x∈ M都有 x f( x) xf ( x)是奇数 ,这样的映射f的个数是 (　　 ) .( A) 2 5　　 ( B) 50　　 ( C) 75　　 ( D) 1 2 5( 2 )若映射 f :M→ N,使对任意的 x∈ M都有 x f( x) xf ( x)是偶数 ,这样的映射f的个数是 (　　 ) .( A) 0　　 ( B) 50　　 ( C) 75　　 ( D) 1 2 5(吴新华供题 )2 .函数 y =x 5- x的值域是;函数 y =x - 5- x的值域是.(向国华供题 )3.已知圆 C:( x - a) 2 ( y - a) 2 =a2 ,直线 l:3x 4 y 3=0 .( 1 )若圆上有…