一个健康状态转移模型的探讨

考虑有 m个健康状态 J1 ,J2 ,… ,Jm和 n个死亡状态 D1 ,D2 ,…… ,Dn的疾病死亡模型 ,在某些假设前提下 ,得到了各种状态的转移概率及极限概率 .

图m(G_1(2n,1)*G_2(2n,1))的优美性和奇强协调性

定义图m(G1(2n,1)*G2(2n,1))的概念,证明它是优美图和奇强协调图,还证明图G1(2n,m)也是奇强协调的.

局部引理及其在(r，s)-SAT问题中的应用

一般说来,寻找满足一定结构性质的对象结构是困难的。概率方法提供了解决此类问题的途径:证明满足一定结构性质的对象的概率大于零。在概率方法中,局部引理是一个关键技术。本文介绍了局部引理的基本原理和使用方法,并将其应用到估计(k,s)-SAT问题中临界函数的下界。

一个组合计数问题

文献给出了下述计数问题：由ｎ个０和ｎ个１构成的字符串中，任意前ｋ个字符中０的个数不少于１的个数的字符串有多少？本文给出了求解的一种方法，并用所得结果解决了另一个计数问题．

k-LSAT(k≥3)是NP-完全的(英文)

合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关.即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.

几种特殊图的填充数

应用图的最优填充分解定理和局部最优填充定理,得到了书本图Bm、方型网图F(m;n)(m=1,2,3)和蛛网图W(m,n)(m=1;n=3)的填充数表达式分别为:F(Bm)=m,F(F(1;n))=n,F(F(2;n))=4n-3,F(F(3;n))={3,n=1,9,n=2,14,n=3.F(W(1,n))=n-3,F(W(m,3))=3(m-1).

图论模型及其应用

图论模型方法是处理实际问题的一种有效的数学方法,随着计算机科学的发展,图论得到了快速发展.通过几种重要的图论模型,包括树的模型、染色模型、遍历模型、匹配模型和初等模型等,论述了这些图论模型的特点及其在实际问题中的应用.

几类图的树宽

利用图的树宽分解定理,得到圈Cn的r-冠图Ir(Cn)、方型网图F(m;n)(m=1,2,3)、蛛网图W(m,n)和图PmPn的树宽.

两类特殊图的最优填充

运用图的最优填充分解定理,将强乘积图P3 Pn,P2 Pn与乘积图P2×P2n进行分解,得到了它们的最优填充数.

蛛网图的连通包数(英文)

证明了蛛网图W(m,n)的连通包数为hc(W(m,n))=m+2n-1.通过对蛛网图进行简化处理,即将蛛网图W(m,n)的叶子顶点去掉,得到图G的连通包数为hc(G)=n2?+m.

有关连通图的连通包数的一些结果

通过图的连通包集和连通包数的定义,确定了测地数、包数和连通包数三者之间的大小关系,并通过一些特殊图(完全二部图、分裂图)构造了连通包数为3的3类图.

枫叶图的奇优美性和奇强协调性

首先提出了枫叶图的概念,然后证明了当m≡0(mod2)且k=2m和m≡1(mod2)且k=2m-1,m≥2时,枫叶图的奇优美性和奇强协调性.

简单平图的圈基性质

图的圈基是图的一个重要结构.该文利用代数的思想和方法研究了圈基在简单平图上的一些性质,并计算了一种特殊简单平图的最大圈基值.

5-连通图最长圈上可收缩边的分布

图可收缩边的存在性对于研究图的结构和证明图的归纳性质有着重要作用.该文对5-连通图中最长圈可收缩边的分布情况进行研究,证明了若G不包含某些特殊的2-断片,则最长圈C上至少包含六条可收缩边;进一步证明了若最长圈C中没有包含5度点的三边形则C至少包含两条可收缩边.

谱矩与圈数

图G是一个简单图,其中A(G)表示图G的邻接矩阵,Mk(G)是指图G的k阶谱矩,Mk(G)=tr(A(G)k).也就是说,Mk(G)等于图G中长度为k的闭途径的数目.该文借助谱矩给出了计算任意简单图中圈C3、C4、C5的个数的方法.

蛛网图的偶匹配可扩性(英文)

图G的匹配M是偶匹配,如果G[V(M)]是偶图.图G是k-偶匹配可扩的(1≤k≤(V(G)-2)/2),如果G的每一个基数不大于k的偶匹配都可以扩充为G的一个完美匹配.研究蛛网图的偶匹配可扩性得出的结论是:蛛网图不具有偶匹配可扩性和2-偶匹配可扩性.

鞅的极大函数的Φ－可积性

设ｆ是的极大函数，本文讨论ｈ（ｆ）的几种Φ－可积性（其中ｈ，Φ是凸函数），并给出相关不等式中的常数ｃ的一个上界。