关于图的分数k-因子存在性的一些结果

设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。     

关于互连网络群论模型的一簇猜想

连通图生成的Cayley图是作为互连网络的群论模型提出来的概念。猜想:设G=(V,E)是具有顶点集{1,2,…,n}(n>2)和m条边的连通图。如果m=2r,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并;如果m=2r+1,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并。特别地,对于k=r和星网络,这个猜想的特殊情形是1998年由师海忠提出来的。     

两个多色顶点Folkman数的界*

对于正整数a1,a2,…,ar以及无向简单图G, 当且仅当对G的任意一种顶点r着色,都对某个i∈{1,2,…,r}存在顶点都着有颜色i的ai阶的完全子图, 则记G→(a1,a2,…,ar)v。对于k＞max{a1,a2,…,ar},顶点Folkman数定义为Fv(a1,a2,…,ar;k)=min{｜V(G)｜:G→(a1,a2,…,ar)v,KkG}。借助于计算机 得到了18≤Fv(2,2,2,3;4)≤Fv(2,3,3;4)≤30。     

T函数的圈结构特征

T函数是n位字到n位字的一个映射,并且输出的第i位仅与第0,1,…,i位有关,0≤i≤n-1。可逆T函数在密码学上有重要的应用。深入研究了一般可逆T函数的圈结构,利用T函数的结构和参数特性,首次从理论上证明了可逆T函数的任一圈结构的长度都是2的方幂这一重要特征,并分别从不同的角度给出了由可逆T函数f(x)mod 2k的圈结构判定f(x)mod 2k+1圈结构的两种不同判定方法。基于此进一步分析了可逆T函数的圈结构特征,提出了可逆T函数圈结构特征为2n-tX2t的判定方法。     

逐段单调三次样条插值

设(x_i,y_i)(i=0,1,…,k)为平面上的一组点,α=x_0相似文献   

Ω上三重积分优化复化Simpson数值算法

设空间区域 Ω={(x,y,z)|α≤x≤b,φ_1(x)≤y≤φ_2(x),φ_1(x,y)≤z≤φ_2(x,y)}。(1)f(x,y,z)在Ω及其邻域内具有四阶连续偏导数,φ_1(x)与φ_2(x)在[α,a]内可导,φ_1(x,y)与φ_2(x,y)在Ω的投影(xoy面)区域上具有连续偏导数。下面介绍三重积分 I=∫∫∫f(x,y,z)dxdydz (2)的优化复化Simpson数值积分算法。首先将Ω进行划分,把[α,b]分为2m等分,步长与分点为 h_1=(b-α) /2m,x_i=α+ih_1(i=0,1,2,…,2m)。 (3)在x_(2i+1)处把[φ_1(x_(2i+1)),φ_2(x_(2i+1))分为2n等分,步长与分点为 g_(1,2i+1) =((φ_2(x_(2i+1)))-(φ_1(x_(2i+1))))/2n (i=o,1,2,…,m-1), (4) y_(2i+1,j)=φ_1(x_(2i+1))+jg_(1,2i+1) (j=0,1,2,…,2n)。     

国防科技大学研究生院二○○○年博士生入学考试数值分析试题

一、选择题 (每小题 3分 ,共 1 2分 )在下列各题的备选答案中 ,请把你认为正确的答案的题号填入括号中 ,少选、多选均不给分。1 .下列命题正确的有 (　　　　 )。( 1 )数据 {xi,fi}ni=0 的 m次样条函数 Sm( x)满足条件S( m)m ( xi) =f ( m)i 　　 i =0 ,… ,n　　 ( 2 )利用数表 {xi,fi}ni=0 构造的拉格朗日插值多项式 Ln( x)是一个不超过 n次的多项式。( 3)设 α是 f( x) =0的根。如果 f( x)在区间[α-δ,α+δ]上二次连续可微并且 f′( x)≠ 0 ,则 x0 ∈ [α- δ,α+ δ],牛顿迭代收敛。( 4 )三次样条函数是一个三次多项式。2 .下列求积…     

图的分数[a,b]-因子存在的一个条件

图G的孤立韧度定义为I(G)=min｛｜S｜/i(G-S):S!V(G),i(G-S)≥2｝,若G不是完全图;否则,令I(G)=∞。论文给出了图的分数[a,b]-因子的存在性与图的孤立韧度的关系。证明若δ(G)≥I(G)≥a-1+a/b,则图G有分数[a,b]-因子,其中a相似文献   

有限点集上的极小问题

1.引 言 设X={x_1,x_2,…,x_m},H为X上的连续函数空间.对于f∈H,取 ||f||=sum from i=1 to m|f(x_i)|。 给定X ×(-∞,∞)上的非负二元函数F(x,y)及K∈H,我们提出极小问题如下:寻找一个P∈K,使它满足     

一类最佳二次样条插值

若已知区间[a,b]的一个分划△:a=x_0相似文献   

LR(0) grammars generated by LR(0) parsers

Summary Let be an LR(0) parser of a given LR(0) grammar G. Generally, does not only parse the words generated by G but also the words of some other LR(0) grammars different from G. In this paper we shall define a class of LR(0) parsers and shall present a characterization and a method for the construction of all LR(0) grammars which can be parsed by a given LR(0) parser.     

一个新的(t0, t, n)门限签名方案

提出了一个新的(t0,t，n)门限签名方案。该方案适用于签名成员中存在特殊成员的情形。与已有的(t0,t,n)门限签名和(t0,t,n)门限签名相比，该方案具有如下特点：(1)系统中存在特殊与普通两类成员，他们在签名中的作用不同；(2)当参与签名的一般成员达到绝对多数时，可强行对消息签名。     

Algorithms for (0, 1, d)-graphs with d constrains

Let G be a graph with vertex set V(G). Let n, k, d be non-negative integers such that n+2k+d≤|V(G)|?2 and |V(G)|?n?d are even. A matching which saturates exactly |V(G)|?d vertices is called a defect-d matching of G. If when deleting any n vertices the remaining subgraph contains a matching of k edges and every k-matching can be extended to a defect-d matching, then G is said to be an (n, k, d)-graph. We present an algorithm to determine (0, 1, d)-graphs with d constraints. Moreover, we solve the problem of augmenting a bipartite graph G=(B, W) to be a (0, 1, d)-graph by adding fewest edges, where d=∥B|?|W∥. The latter problem is applicable to the job assignment problem, where the number of jobs does not equal the number of persons.     

On the decoding of the (24, 12, 8) Golay code

An improved syndrome shift-register decoding algorithm, called the syndrome-weight decoding algorithm, is proposed for decoding three possible errors and detecting four errors in the (24, 12, 8) Golay code. This method can also be extended to decode two other short codes, such as the (15, 5, 7) cyclic code and the (31, 16, 7) quadratic residue (QR) code. The proposed decoding algorithm makes use of the properties of cyclic codes, the weight of syndrome, and the syndrome decoder with a reduced-size lookup table (RSLT) in order to reduce the number of syndromes and their corresponding coset leaders. This approach results in a significant reduction in the memory requirement for the lookup table, thereby yielding a faster decoding algorithm. Simulation results show that the decoding speed of the proposed algorithm is approximately 3.6 times faster than that of the algebraic decoding algorithm.     

High speed decoding of the binary (47, 24, 11) quadratic residue code

An efficient table lookup decoding algorithm (TLDA) is presented to decode up to five possible errors in a binary systematic (47, 24, 11) quadratic residue (QR) code. The main idea of the TLDA is based on the weight of syndrome, the syndrome decoder together with a reduced-size lookup table (RSLT), and the shift-search method given by Reed et al. Thus, the size of the lookup table and computational complexity in a finite field can be significantly reduced. The memory size of the proposed condensed lookup table (CLT) consists of only 36.6 Kbytes and is only about 0.24% of the full lookup table (FLT) and 3.2% of the lookup up table given by Chen et al., respectively. These facts lead to significant reduction of computational time and the decoding complexity. A simulation result shows that the decoding speed of the proposed TLDA is much faster than all existing decoding algorithms. Moreover, it can be extended to decode all QR codes, including the class of the cyclic codes when the code length is moderate. The CLT makes this new decoding algorithm suitable for hardware or firmware implementations.     

A Lookup Table Decoding of systematic (47, 24, 11) quadratic residue code

A new decoding algorithm for the binary systematic (47, 24, 11) quadratic residue (QR) code, a code that allows error-correction of up to five errors, is presented in this paper. The key idea behind this decoding technique is based on the existence of a one-to-one mapping between the syndromes “S₁” and correctable error patterns. By looking up a pre-calculated table, this algorithm determines the locations of errors directly, thus requires no multiplication operations over a finite field. Moreover, the algorithm dramatically reduces the memory required by approximately 89%. A full search confirms that when five or less errors occur, this algorithm decodes these errors perfectly. Since the implementation is written in the C-language, it is readily adaptable for use in Digital Signal Processing (DSP) applications.     

Simultaneous approximation by (0,..., R−2, R) interpolators

The present note describes a general technique to derive quantitative assertions concerning the degree of simultaneous approximation by lacunary interpolation operators of the (0, ..., R−2, R) type. The effectiveness of our technique is demonstrated by improving various classical theorems, and by showing how other significant statements can be obtained in quite a natural fashion, too. Dedicated to the late Arun Kumar VARMA     

Fast, prime factor, discrete Fourier transform algorithms over GF(2) for 8 ? m ? 10

In this paper it is shown that Winograd’s algorithm for computing convolutions and a fast, prime factor, discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2^m − 1 points over GF(2^m), for 8 ? m ? 10. These new transform techniques can be used to decode Reed-Solomon (RS) codes of block length 2^m − 1. The complexity of this new transform algorithm is reduced substantially from more conventional methods. A computer simulation verifies these new results.