K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

级数求和的一些初等方法

“级数求和”也可以叫“数列求和”。如果级数sum from k=1 to ∞(a_k=a_1 a_2 … a_n ……)的部分和序列S_n=a_1 a_2 … a_n 有极限lim S_n 存在,就把这个极限叫做级数sum from k=1 to ∞(a_k) 的和。在中学数学里,曾提到许多数列的求和问题,例如无穷递缩等比数列的求和公式为:     

关于整系数线性型的两个问题

设a_1,a_2,…,a_k是正整数,(a_1,a_2,…,a_k)=1。线性型f_k=a_1x_1+a_2x_2+…+a_kx_k(x_1,x_2,…,x_k取非负整数)所不能表出的最大整数及f_k不能表出的正整数的个数分别以M_k及N_k表示。关于如何求出M_k是一个尚未完全解决的问题,柯召教授首先讨论了k=3的一个情形。在柯召教授的指导下,陆文端又讨论了k=3的另外一些情形。J.B.Roberts对a_1,a_2,…,a_k成算术级数的情形得出了M_k的公式。除重穆推广柯召教授的结果证明了下面的一个定理:命D_i=(a_1,a_2,…,a_i),     

解线性方程组的0.618方法

线性方程组 a_(11)x_1+a_(12)x_2…a_(1n)x_n=b_1 …………………………………………… a_(n1)x_1+a_(n2)x_2+…+a_(nn)x_n=b_n 的解法有多种,本文给出一个新的解法——“0.618”方法,并证明了解法的收敛性及唯一性。     

多项式根的k次方之和的新解法

若xj(j=1 ,2 ,… ,n)是n次方程a_nx~n+a_(n -1) x~(n -1) +… +a_1 x +a_0 =0的n个根 ,将给出一种求这n个根x_1 ,x_2 ,… ,x_n 的k次方之和sum from i=1 to n(x_i~k)的新方法。     

关于均匀钱币投掷过程的可达性

设样品空间Ω={0,1},{X_m,m≥1}为一列相互独立的具有相同分布的随机变量满足P(X_1=0)=P(X_1=1)=1/2.Ω_n=ΩXΩx……XΩ为Ω的n维乘积空间,Ω_n~k={(a_1,a_2,…,a_n)|(a_1,a_2…,a_n)∈Ω_1,sum from i=1 to n ai=k},k=0,1,2,…,n.对Ω_n中之每个元素A定义TA(X_1,X_2,…)=(?)易见T_A(X_1,X_2,…)就表示事件A在过程{X_m,m≥1}中首次出现的时间。设A,B为Ω_n中任意二个不相同的元素,如果P(T_A相似文献   

愉快图的充分条件

本文给出了一个n个顶点的圈C_n:x_1 x_2 x_3……x_n x_1加上两条边K_(k1) x_(k2),x_(k_1) x_(k3)(其中k_3=k_2+2,k_2=k_1+k-1)是愉快图的充分条件,并完成了它们的证明。     

关于矩阵乘积的奇异值的一个不等式及其应用

约定 A(≥0)>0为(半)正定 Hermite 矩阵。如果复矩阵 A=(a_(ij))(∈C~(n×n))的特征值都是实数,规定其特征值满足λ_1(A)≥…≥λ_n(A),用σ_1(A)≥…≥σ_n(A)表示 A 的n 个奇异值,规定{δ_1(A),…,δ_n(A)}与{a_(11),……,a_(nn)}为同一集合且|δ_1(A)≥…≥|δ_n(A)|。当实向量 x=(x_1,…,x_n)与 y=(y_1,…,y_n)的分量按递减顺序排列为 x_[1]≥…≥X_[n]与 y_[1]≥…≥y_[n]时,若(?)X_(i)≤(?)y_[i],k=1,2,…,n,则称 y 弱控制 x,记为 x相似文献   

不定方程 a_1x_1 a_2x_2 … a_sx_s=n 的Frobenius问题

对于 n 和 a_1,a_2均是正整数,且(a_1,a_2)=1的二元一次不定方程 a_1x1 a_2x_2=n,能够找到仅与 a_1,a_2有关的整数 g(a_1,a_2)=a_1a_2-a_1-a_2,使得当 n>g(a_1,a_2)时,不定方程有非负整数解,而当 n=g(a_1,a_2)时,不定方程没有非负整数解。求 g(a_1,a_2)的问题就是二元一次不定方程的 Frobenius 问题。本文解决如何求仅与不定方程 a_1x_1 a_2x_2 … a_2x_2     

等差数列的两个充要条件

我们知道,如果{a_n}为等差数列(以下简记为A·P),那么它的通项和前n项和分别是: a_n=a_1 (n-1)d ① S_n=na_1 n(n-1)d/2 ② 整理,得 a_n=d_n (a_1-d) ③ S_n=d/2n~2 (a_1-d/2)n ④ ③、④二式表明:当d≠0时,A·P的a_n是n的一次式,S_n是n的二次式;当d=0时,A·P的a_n是常数,S_n是n的一次式。 现在的问题是:如果一个数列的通项a_n=kn b(k,b为常数),那么这个数列是否是A·P?如果前n项和S_n=pn~2 q~n r,这个数列是否是A·P?下面的两个定理分别解决了这个问题。 定理1 数列{a_n}为A·P的充要条件是:a_n=kn b(其中k,b是常数)。     

有限模格的自同构

本文给出有限模格自同构的充分必要条件,从而得出寻求有限模格自同构的方法。定义1 a是格L的元,1最格L的最大元,若在L中存在k个元组成序列。 a_1=Ⅰ>a_2>a_3>…>a_(k-1>a_k=a其中a_1复盖a_(i+1)(i=1,2,…k-1),称a为k层元,又称a到I的距离为k。定义2 若格L的k层元为a_(k_1),a_(k_2),…_(k_3);k+1层元为a_(k+1),a_(k+12),…a_(k+1)■称s×t矩阵(c_(ij))为k层元复盖k+1层元的关系阵。     

Ms—的一个算法

设a_1,a_2,…,a_s均为正整数,(a_l,a_2, …,a_s)=1,线性型f_i=a_1x_1 a_2x_2 … a_ix_i,x_i≥0,i=1,2,…,s,所不能表出的最大整数记为M_i。本文证明了,M_s可以表示为 sum from i=2 to s(a_ik_i)-sum from j=1 to s(h_ja_j), h_j≥1.其中k_i(i=1,2,…,s)是使等式 a_ik_i=a_1x_(1i) …a_(i-1)x_((i-1),i)i a_(i 1)x_((i 1),i) … a_sx_(si),x_(1i)≥0,…,x_((i-1),i)≥0,x_((i 1),i)≥0,…,x_(si)≥0成立的最小正整数。并通过h_i的确定,给出M_s的一个算法。     

n元一次不定方程的一种解法

不定方程a_1X_1+a_2X_2+…+a_nx_n=b (n≥2,6,a_i∈Z,i=1,2…n),当n=2时可用公式求解,但当n>2时目前还没有求解公式.本文用代数方法解决了这一问题。     

判别Hamilton图的一个方法

本文研究寻找Hamilton的圈的一个方法,证明了如下定理:设G是单图,V(G)={V_1,V_2,…,V_n},则G是Hamilton图的充分必要条件是X_(ki)取1或0时,方程组(*)有解,其中sum from i=1 to n sum from j=1 to n x_(ki)x_(k+1)jV_iV_j=1而x(n+1)j=x_(1j) sum from i=1 to n x_(ki)~2=1 sum from i=1 to n x_(ik)~2=1 而V_iV_i=1 当V_i和V_j邻接时, 0 当V_i和V_j不邻接时。     

独立随机变量平方和的极限定理

设X_1,X_2,…为相互独立的随机变量序列,EX_k=0。EX_k~2=μσ_k~2.k=1.2,…B_n=sum from k=1 to n (σ_k~2),X_n~2=sum from k=1 to n(X_h~2)。若各X_k再满足一些条件,则我们有     

一类捕食者——食饵模型的稳定性分析

在这篇论文中,研究了系统x_1′=—a_1x_1 bx_1x_3,x_2′=nx_1 (a_1 a_2)x_2,x_3=—cx_3 dx_1x_3的非负平衡点的稳定性,一般说来,如果-a~2_1—a_1a_2 a_(2n)<0就能得到一个非负的O(0,0,0)的稳定性。     

关于MYCIELSKI方程的推广

Jan Mycielski 曾研究一类不定方程:x~xx~y=Z~z;x~xy~zZ~y=x~yy~z=z~x。本文将来上述方程推广为x_1~(x_2)x_2~(x_3)………x_k~(x_y) x_2~(x_1)=1(?),x>2,z>1,k≥3x_1~(x_1)x_2~(x_3)x_3~(x_4)………x_(k-1)~(x_(k-1))x_(k-1)~(x_k)=x_k~(x_2),x~2>1,k≥3x_1~(x2)x………x_(k-2)~(xk-1)x_(k-1)~(xk)=x_k~(x1),x_2>1,k≥3对于这些方程,我们分别地给出整数解(6-1)、(6-2);(7-1),(7-2)和(8-1),(8-2)。     

范式dk=a_1x_1+a_2x_2+…+a_nx_n的解法

令d,a_1,…,a_n为非负整数,K是使(1)dk=a_1X_1+a_2X_2+…+a_nX_n,X_i≥0,i=1,…,n成立的最小正整数.(1)式叫做d关于a_1,a_2,…,a_n的范式,简称n元范式.在文[1]、文[2]中,对n=2的情形,给出了范式的解法.本文在此基础上,解决n(>2)元范式的解法.     

关于两种群Volterra模型扇形稳定性的研究

Lotka-volterra模型是指: x=x_1(a_(10) a_(11)x_1 a_(12)x_2) x_2=x_2(a_(20) a_(21)x_1 a_(22)x_2) (Ⅰ)根据生态系统的意义,总是假定: x_i≥0,a_(10)>0,a_(ii)<0(i=1,2)设E(x_(10),x_(20))是(Ⅰ)和平衡点,若x_(10)>0,x_(20)>0称E为(Ⅰ)的第一类平衡点;若x_(10)~2 x_(20)~2≠0,x_(10)·x_(20)=0称E为(Ⅰ)的第二类平衡点。 一个时期以来,由于生态学等学科的需要,许多学者对Lotka-volterra模型的第一类     

一类有限可分扩张的本原元

本文利用Galois理论讨论了一类特殊的域的扩张,获得了如下主要结论: 定理 设n_1,n_2…,n_k是任意k个正整数,域F的特征chF=0,或者chF与n_1,n_2…,n_k互素, 又设x_1,x_2…x_k是F上的k个不相关不定元,则有