完全二叉树理论的可数模型及其胞腔性

三角格及满二叉树上的σ全一问题
细胞自动机是一种离散动力系统,它包含了由细胞单元的状态构成的配制以及作用在配制上的传递规则。

其数学刻画如下:假设在一个无向图的每个顶点上安装有一个指示灯和一个按钮。

如果在该图中按下一个按钮,则它的所有相邻点上的灯将由暗到亮,反之亦然。

开始时,所有灯都是暗的,问题是:是否有可能按下一系列的按钮使得最终所有的灯都亮了?该问题被称为σ全一问题,特别地,若图的每一个点都有一个自环,则它也被称为σ⁺全一问题,起源于Sutner引入的棋盘上的全一问题,后被Peled称为点灯问题。

近年来σ⁺全一问题已经被广泛的研究,见文
Sutner[30,31],Barua和Ramakrishnan[2]以及Dodis和Winkler[13]。

用线性代数的理论,Sutner证明σ⁺全一问题的解对任何图总是存在的,并给出了n×n的格子图上解的一些计数结果。

Erikisson等给出了解存在性的图论证明。

进而,Chen和Gu给出了一个精巧的图论算法来找到一般图上的解。

与σ⁺全一问题不同,σ全一问题在很多图上都无解（例如
C₃和P₅）。

近期,Chang和Qian在文[40]中给出了四角格与六角格上的σ全一问题无解的一个充要条件。

本文分别给出了以三角形、菱形（四边形）和六边形为边界的三角格及满二叉树上的σ全一问题无解的充要条件。

二叉树模型名词解释
x
二叉树模型：
二叉树模型是一种树形结构，它的每个节点最多有两个子节点，并且每个节点都有一个根节点。

每个节点可以包含数据和指向其子节点的指针。

它是一种一般性的数据结构，可以用来表示复杂的数据结构，如文件系统、网络系统等等。

根节点：
根节点是二叉树模型的最上层节点，也称为根节点。

根节点没有父节点，但可以有一个或多个子节点。

子节点：
子节点是指每个节点的子节点，也称为孩子节点。

每个节点都可以有一个或多个子节点，但每个节点最多只有两个子节点，一个是左子节点，一个是右子节点。

叶节点：
叶节点是指没有子节点的节点，也称为终端节点。

叶节点是二叉树模型的最底层节点。

路径：
路径是指从根节点到叶节点的一系列节点。

每个节点都是路径的一个分支，这些分支组成了一条完整的路径。

每一条路径都是由多个节点组成的，它们在树模型中构成一条连续的序列。

*国家自然科学基金资助项目(19931020)收稿日期:2003-06-03完全二叉树理论的模型及性质*陈 磊 沈复兴(北京师范大学数学系,100875,北京M 第一作者26岁,女,博士生)摘要 定义了完全二叉树理论的决定公式.利用该类公式证明了此理论是原子理论,且型的个数是可数的.还给出了它的可数原子模型和饱和模型.证明了完全二叉树理论的X 1-范畴性.关键词 完全二叉树理论;原子模型;饱和模型;型;X 1-范畴分类号 O 141.41 完全二叉树理论的公理完全二叉树是图论中一个较基础的概念,在其他学科,例如计算机科学,也有着广泛的应用.一棵完全二叉树上的节点个数是多少?是否存在可数的完全二叉树?如果有,互不同构的可数完全二叉树模型有多少个?本文用模型论的方法来研究这些有趣却并不显然的问题.下面先阐述一下完全二叉树的理论.设一阶语言L ={E,R},E 是二元关系符号,R 为常量符号.完全二叉树的理论T 由下列公理组成:它表示存在长度为k 的环(即图中有k 条边首尾相连,构成一个环).为简单起见,我们定义下面一些关系:1)二元关系d (x ,y ).若有x S y ,则称x ,y 的距离为0,记作d(x ,y )=0.若有xEy ,则称x ,y 的距离为1,记作d(x ,y )=1.若公式v z 1z 2,z n-1((C i X jz i X z j )C (C n-1i=1x X z i )C (C n-1i=1y X z i )C (xEz 1)C (z 1Ez 2)C ,C (z n-1Ey )),n \22004年 4月第40卷 第2期北京师范大学学报(自然科学版)Journal of Beiji ng Normal Universi ty (Natural Science)Apr.2004Vol.40 No.2成立,则称x ,y 的距离为n,记作d (x ,y )=n (n \2).它表示节点x ,y 间有一条长度为n 的路径连接x 和y.2)一元关系h (x ).若有公式d (x ,R )=n,则称节点x 的高度为n,记作h(x )=n (n \0).它表示节点x 与根节点的距离为n.设L 的模型A =3A,E ,R 4,若A 4T ,则称A 为完全二叉树理论的一个模型.我们称A 为树中的节点集,xEy 表示节点x ,y 有边相连,R 为唯一的1个根节点.2 完全二叉树理论的型的个数刘吉强等[1]利用分布公式和有限覆盖证明了:完全二叉树的理论是可以量词消去的,进而是完备理论.并给出了它的消去集为{d(x ,y )=n,h(x )=m (n ,m =0,1,2,)}.这样该理论的任意公式都等价于消去集中的公式及恒真和恒假公式的布尔组合.在这一基础上我们计算了该理论的型的个数.先给出几个定义.定义1 形如:;m 1,m 2,,,m n C 1[i<j [n s ij(x 1,,,x n )BS (h(x 1)=m 1C h(x 2)=m 2C ,C h(x n )=m n C d (x 1,x 2)=s 12C ,C d (x i ,x j )=s i j C ,C d(x n-1,x n )=s n-1,n ),m k ,s i j I N ,1[k [n,1[i <j [n的任意n 元公式称为完全二叉树理论的决定公式,n <X .定义2 d(x ,y )=]BS (d (x ,y )X 0)C (d (x ,y )X 1)C ,C (d(x ,y )X n)C ,.该二元关系描述的是2个变元间的距离无限大.定义3 h(x )=]BS (h(x )X 0)C (h(x )X 1)C ,C (h (x )X n)C ,.该一元关系描述的是x 的高度无限.定理1 对于任意n <X ,完全二叉树的理论T 只含有可数多个n 元型.证 为了讨论该理论中型的个数,我们只要考虑由消去集中的公式组成的型.设E (x 1,x n )为一阶语言的n 元型,则E (x 1,x n )中的公式为(h(x 1)=m 1C h (x 2)=m 2C ,C h(x n )=m n )C C 1[i <j [n(d(x i ,x j )=s ij ),其中m 1,,,m n ,s ij I N 或等于],1[i <j [n.不同的2个n 元型分别对应2个不同的有限序列(m 1,,,m n ,s 12,,,s n -1,n ).因此|S n (É)|[T 0#T 0#,#T 0n +(n(n -1)/2)=T n(n +1)/20=T 0.即对于任意n <X ,完全二叉树的理论T 只有可数多个n 元型.3 完全二叉树理论的模型现假设B 0为如下模型:rr 0r 00r 000r 0000r 00000,r 00001,r 0001,r 001r 0010,r 0011,r 01,r 1r 10,r 11r 110r 1100,r 1101,r 111r 1110,r 1111r 11110,r 11111,, 178 北京师范大学学报(自然科学版)第40卷其中任一元素的高度有限.r 为B 0中的根结点R.不难看出B 0是完全二叉树理论的一个模型.由于B 0中高度为n 的节点共有2n 个,而n <X ,所以B 0中的元素是可数的.故B 0是该理论的一个可数模型.由于定义1中的任一个m 变元决定公式描述了m 个变元的高度及相互之间的距离,故完全二叉树理论的量词消去性保证了:对于L 中的任意一个公式,每个决定公式总蕴含该公式或其否定.这样,任意一个决定公式都是完备公式.故有下面的定理2.定理2 模型B 0为L 的原子模型.证 根据原子模型的定义[2-4],对于B 0中任意的n 元组r 1,,,r n ,存在m 1,m 2,,,m n ,s 1,2,,,s i ,j ,s n -1,n I N ,1[i <j [n,使得h (r 1)=m 1,h (r 2)=m 2,,,h (r n )=m n 且d (r i ,r j )=s i,j ,1[i <j [n.即B 04;m 1,m 2,,,m n C 1[i <j [n s ij (r 1,,,r n ),这样B 0中任意的n 个元素均满足一个决定公式.因此模型B 0是原子模型.根据原子模型的存在性定理[2-4],可以得到下面的定理3.定理3 完全二叉树理论T 是原子理论.由原子模型和素模型的等价性[2-4]知B 0是T 的可数素模型,能初等嵌入到完全二叉树理论的任意一个模型中.因而,它可被看作是该理论的/最小0模型.根据定理1和可数饱和模型的存在定理[2-4]可知,完全二叉树的理论有可数的饱和模型.接下来,我们要用初等模型链的方法构造它.从定理3我们知道该理论一元型的个数是可数的,其中除了2(x )={h (x )X 1,h(x )X 2,h (x )X 3,,,h(x )X n,,}外,其他的型都能在B 0中实现,因此添加r ]来满足2(x ).也正因为r ]的添加,根据完全二叉树理论公理,r ]必和3个节点相连,这3个节点的高度也是无穷.这样,从r ]起将向下发出两枝二叉树,向上与一枝二叉树相连.这3枝树上的节点的高度都是无穷,但和r ]的距离却是有限.我们把新添加的这一部分称作B 1,它的节点个数是有限的,把添加B 1后的模型记作B 0ÝB 1.容易看出,B 0ÝB 1也是完全二叉树理论的一个可数模型,并且它和B 0是不同构的.其结构如下图:rr 0r 00r 000,r 001,r 01,r 1r 10,r 11r 110,r 111, , )))r c r c 0r c 00r c 000,r c 001,r c 01,r c 1r c10,r c 11r c 110,r c 111,,其中B 1中的元素与B 0中的元素不同,h(r c )=h (r c 0)=h(r c 1)=,=].B 0ÝB 1是B 0的初等扩充,并且对于B 0中任意有限子集A <B ,与Th (B 0A )和谐的每个公式#(x )都能在B 0ÝB 1中得到实现.这样逐个添加下去,可以得到可数多个互不同构的模型.把添加可数多个B 1时得到的模型记作B X .定理4 B X 是完全二叉树理论的可数饱和模型.证 对于任意有限子集A <B X ,由上面的构造过程我们总能找到整数n,使得A <B 0ÝB 1Ý,ÝB 1n .这样,S 1(A)总能在B 0ÝB 1Ý,ÝB 1n +1中实现,进而可以在B X 中实现.从而,B X 是完全二叉树理论的可数饱和模型.根据可数齐次模型和可数万有模型的定义[2-4],B 0和B X 是可数齐次模型,B X 是可数万第2期陈 磊等:完全二叉树理论的模型及性质179180北京师范大学学报(自然科学版)第40卷有模型.从上面的构造过程我们可以看出:完全二叉树理论互不同构的可数模型至少有可数多个.因此,该理论不是X0-范畴的.下面将利用强极小理论的定义及相关引理来证明完全二叉树理论是X1-范畴的.定义4[5]设T是一理论,公式U(v1,v2,,,v n)称为在T中是代数的,若U与T和谐且对于所有M4T,U(M)={a=(a1,a2,,,a n)I M:4U(a1,a2,,,a n)}是有限的.引理1[5]若T是一个强极小理论,则T在每一不可数基数上是范畴的.定理5完全二叉树理论是X1-范畴的.证由完全二叉树理论T是可量词消去的,T的任一模型M上的一元公式等价于h(x)= n,n<X和d(x,a)=m,m<X,a I M的布尔组合.而M中分别满足这2个公式的元素均是有限的.因而,公式x=x是强极小的,即理论T是强极小理论.利用引理1,定理得证.4参考文献[1]刘吉强,廖东升,罗里波,等.完全二叉树理论的量词消去[J].数学学报,2003,46(1):95[2]Chang C C,Keisler H J.Model theory[M].Amsterdam:North-Holland Publishing Co,1977[3]沈复兴.模型论导引[M].北京:北京师范大学出版社,1995[4]王世强.模型论基础[M].北京:科学出版社,1987[5]Steven Buechler.Essential s tability[M].Berlin:Springer-Verlay,1996THE MODELS AND PROPERTIES OFTHE THEORY OF CO MPLETE BINARY TREEChen Lei Shen Fuxing(Department of Mathematics,Beiji ng Normal University,Beiji ng100875,Chi na)Abstact The determinant formulas of the theory of complete binary tree are defined and used in this paper to prove that the number of the types of this theory is countable and the theory is atomic.The countable atomic and saturated models are also built.Moreover,it is proved that the theory is cate gorical in every uncountable power but not in po wer X.Key words the theory of complete binary tree;atomic model;saturated model;type;X1-categorical。

二叉树（Binary tree）是树形结构的一个重要类型。

许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。

当集合为空时，称该二叉树为空二叉树。

在二叉树中，一个元素也称作一个节点
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树是递归定义的，其节点有左右子树之分，逻辑上二叉树有五种基本形态：
1、空二叉树
2、2、只有一个根节点的二叉树
3、只有左子树
4、只有右子树
5、完全二叉树。

名词解释1、Totipoency(细胞全能性)：指植物的每个细胞都包含着该物种的全部遗传信息，从而具备发育成完整植株的遗传能力。

在适宜条件下，任何一个细胞都可以发育成一个新个体。

植物细胞全能性是植物组织培养的理论基础。

2、Partical molar volume(水的偏摩尔体积)：在【T、P】下，往无限大的体系（此体系不一定是由水组成）中加入1mol水，体系体积的变化量。

3、Channel framsport(通道转运)：是细胞膜中由通道蛋白构成的孔道，控制物质通过细胞膜。

4、Pressure-flow theory(压力流动学说)：该学说认为从源到库的筛管通道中存在着一个单向的呈密集流动的液流，其流动动力是源库之间的压力势差。

5、MAPK signaling cascades(促分裂原活化蛋白激酶信号转导级联反应途径)：由MAPK、MAPKK和MAPKKK三个激酶组成的一系列蛋白质磷酸化反应。

6、Skotomor phogenesis(暗形态建成)：暗中生长的植物表现出各种黄化特征，茎细而长，顶端呈钩状弯曲，叶片小而呈黄白色。

7、Hardness physiology(植物抗性机理)：是指逆境对植物生命活动的影响，以及植物对逆性的抵御抗性能力。

8、Sene scence (植物的衰老)：是指细胞、器官或整个植株生理功能衰退，趋向死亡的过程。

9、Assimilatory power(同化力)：由于ATP和NADPH用于碳反应中CO2的同化，故把这两种物质合称为同化力。

10、Homeosis(同源异形)：是指分生组织系列产物中一类成员转变为该系列中形态或性质不同的另一类成员。

简答题1、有两种植物激素GA3和6-BA，有萝卜种子和大麦种子两种，设计一个实验将这两种激素区别开来。

GA3是赤霉素的一种。

它能显著地促进植物茎、叶生长，特别是对遗传型和生理型的矮生植物有明显的促进作用；能代替某些种子萌发所需要的光照和低温条件，从而促进发芽；可使长日照植物在短日照条件下开花，缩短生活周期；能诱导开花，增加瓜类的雄花数，诱导单性结实，提高坐果率，促进果实生长，延缓果实衰老。

生物信息学复习题一、名词解释生物信息学, 二级数据库, FASTA序列格式, genbank序列格式, Entrez，BLAST，查询序列（query），打分矩阵（scoring matrix），空位（gap），空位罚分，E 值, 低复杂度区域，点矩阵（dot matrix），多序列比对，分子钟，系统发育（phylogeny），进化树的二歧分叉结构，直系同源，旁系同源，外类群，有根树，除权配对算法（UPGMA），邻接法构树，最大简约法构树，最大似然法构树，一致树（consensus tree），bootstrap，开放阅读框（ORF），密码子偏性（codon bias），基因预测的从头分析法，结构域（domain），超家族，模体（motif），序列表谱（profile），PAM矩阵，BLOSUM，PSI-BLAST，RefSeq，PDB数据库，GenPept，折叠子，TrEMBL，MMDB，SCOP，PROSITE，Gene Ontology Consortium，表谱（profile）。

二、问答题1）生物信息学与计算生物学有什么区别与联系？2）试述生物信息学研究的基本方法。

3）试述生物学与生物信息学的相互关系。

4）美国国家生物技术信息中心（NCBI）的主要工作是什么？请列举3个以上NCBI维护的数据库。

5）序列的相似性与同源性有什么区别与联系？6）BLAST套件的blastn、blastp、blastx、tblastn和tblastx子工具的用途什么？7）简述BLAST搜索的算法。

8）什么是物种的标记序列？9）什么是多序列比对过程的三个步骤？10）简述构建进化树的步骤。

11）简述除权配对法（UPGMA）的算法思想。

12）简述邻接法（NJ）的算法思想。

13）简述最大简约法（MP）的算法思想。

14）简述最大似然法（ML）的算法思想。

15）UPGMA构树法不精确的原因是什么？16）在MEGA2软件中，提供了多种碱基替换距离模型，试列举其中2种，解释其含义。

习题十1. 设G 是一个(n ，m)简单图。

证明：，等号成立当且仅当G 是完全图。

证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。

根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。

（2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。

所以，G 的每个结点的点度都为n-1，G 为完全图。

G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。

■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。

证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。

与题设m = n+1，矛盾。

因此，G 中存在顶点u ，d （u ）≥3。

■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。

因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。

最后，将奇数序列对应的点两两一组，添加连线即可。

下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)v 1v 5v 3v 4v 2将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。

coalescent theory名词解释(一)Coalescent theory名词解释1. Coalescent theoryCoalescent theory是基因演化中的一个重要理论模型，其研究的是种群中个体之间的共同祖先关系。

该理论模型通过回溯推断，解释了如何从现有的物种或个体群，推断出它们的共同祖先。

2. AlleleAllele指的是一个基因座上的一个或多个变种。

在基因组的不同位置上，我们可以有不同的allele。

例如，人类眼睛颜色的基因座上可以有褐色allele和蓝色allele。

3. Gene treeGene tree是一种表示基因演化过程中不同个体之间关系的树状图。

在coalescent theory中，gene tree用于描述共同祖先与后代之间的关系。

例如，假设我们研究某个人群中的多个基因座，我们可以通过分析这些基因座的变异情况，重建出一个表示个体之间共同祖先关系的gene tree。

4. Coalescent eventCoalescent event指的是两个或多个个体的基因共同祖先的合并事件。

在coalescent theory中，coalescent event是基因演化过程中的重要事件，它代表了共同祖先关系的形成。

例如，假设我们研究了一个人群的基因演化，我们可以通过观察基因座的变异情况，确定共同祖先在不同个体之间合并的coalescent event。

5. Neutral mutationNeutral mutation是指发生在基因组中没有显著影响个体适应度的突变。

在coalescent theory中，假设大多数的突变是中性的，对个体的适应度没有显著影响。

例如，人类基因组中的一些基因座上的突变，如常见的单核苷酸多态性(SNP)，很可能是中性突变。

6. Effective population sizeEffective population size是指一个理想化的概念，用于估计一个群体中的基因演化过程。