构造二叉树的一个算法

给出一个算法，该算法输入一棵二叉树的前序遍历和中序遍历的结点序列，构造出该二叉树，该算法具有Ｏ（ｎ）时间复杂度，是解决该问题的最优算法，其中ｎ为二叉树的结点数     

Hamilton偶图的局部度数条件

设Ｇ是具有二分类（Ｘ，Ｙ）的２连通等部偶图。如果对Ｇ中每一个顶点ｖ，Ｈ是Ｇ中与ｖ距离为２和３的所有顶点导出的子图，并且对于ｇ中每一个与ｖ距离为３的顶点ｕ，ｕ在Ｈ中的度数ｄ＿Ｈ（ｕ）不小于距离ｖ为２的顶点的数目减去（ｄＧ（ｖ）－２），则Ｇ是Ｈａｍｉｌｔｏｎ图。其中ｄ＿Ｈ（ｕ）的下界不能改进。     

1-可扩偶图的刻划(英文)

设G是一个具有二分类(X,Y)的偶图且M是G的一个完美对集。文章证明:G是1＿可扩图当且仅当G有如下耳朵分解G=e+P1+P2+…+Pr使得e∈M并且每个Pi是起始和终止边都在E(G)\M中的M＿交错路。文章还给出一个有效算法判定一个偶图是否1＿可扩图并找出该图的耳朵分解。     

大围长图中控制圈的一个局部条件

设Ｇ是围长大于或等于５的连通图．本文证明了；如果对Ｇ中每个顶点ｖ，距离ｖ为２和３的顶点导出的子图的独立数不大于最小度的两倍减３，那么Ｇ中有控制圈．     

工作流系统中的PRBAC访问控制模型研究

工作流管理系统（workflow management systems，WFMS）已被企业和政府广泛用于组织的业务流程管理，系统的任务分派一般采用基于角色的访问控制（role-based accesscontrol，RBAC）模型来解决授权控制问题，这为员工的角色或部门变更提供了良好的适应性.然而，随着竞争的加剧和改革的常态化，组织的结构和角色变化日益频繁.另外，一套流程系统实施到不同的组织，也要面对不同的组织结构和角色.RBAC模型导致业务流程定义中的任务授权严重依赖于组织，后者的频繁变化不但会引起授权体系的频繁变化，甚至因影响流程定义而引起执行期的异常.为此，提出了一种基于职位-角色的访问控制（position-role basedaccess control，PRBAC）模型，将角色的粒度细化为组织职位，同时引入业务角色的概念，授权仅针对后者，并通过一个映射层来建立两者的对应关系.证明了PRBAC与RBAC在表达能力上的等价性，并对授权粒度和复杂度进行了分析.通过案例分析，演示了PRBAC模型可以有效提高WFMS应对组织变化的适应性和柔性，实现了组织模型与业务模型的解耦.     

n-可扩图的局部邻域条件娄定俊

设G是阶为v的图且具有完美对集。设n是正整数,满足n≤(v-2)/2.G称为n-可扩的,是说:G中任意n条独立边包含在G的一个完美对集中。 设G是一个图且v∈V(G)。定义N_k(v)={u|u∈V(G)且d(u,v)=k}。设u,v∈V(G)满足d(u,v)=2.记I(u,v)=|N(u)∩N(v)|。定义散度α~*(u,v)如下: n_(u+v)(W)=max{|S||w∈N(u)∩N(v),S是G[{w}∪N_G(w)]中包含u和v的独立集},     

K方体的递归构造

本文给出了k方体递归的构造性定义,并使用构造方法解决了V.V.Firsov(1965)提出的表征k方体中可嵌入图的问题(见[1]).     

1-可扩偶图的刻划

设G是一个具有二分类(X，Y)的偶图且M是G的一个完美对集。文章证明：G是1—可扩图当且仅当G有如下耳朵分解G=e P1 P2 … Pr使得e∈M并且每个只是起始和终止边都在E(G)＼M中的M-交错路。文章还给出一个有效算法判定一个偶图是否1—可扩图并找出该图的耳朵分解。     

2—可扩平面图

证明了所有具有偶顶点数的5—连通平面图是2-可扩的,并给出了非2-可扩的4-连通平面图。