求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G))|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G)|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

K-通道流的改进算法

设G=(N,A,u)是一个顶点集为N,弧集为A,始点为s∈A,终点为t∈N,有限容量向量u={u_(ij):(i,j)∈A}及正整数K的网络。一个基本K-通道流是从始点到终点t∈N的发送K个单位流,使得在每个弧上的流是0或1。一个K-通道流是一个从s到t的流,使得这个流可以表示成基本K-通道流的非负线性组合的流。因此,K-通道流问题是求解从s到t不仅要满足顶点平衡(s和t除外)和弧的容量限制下通常的最大流问题,而且这个流必需满足沿着K条弧不交的s-t路发送。给出了另一个解决K-通道流问题组合算法,分析了这个改进算法的时间复杂性。     

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分割多项式算法.     

诊断组合逻辑网络的SDT算法

本文提出诊断组合逻辑网络的一种新算法。其特点是根据组合逻辑网络的结构,将产生测试码与时序测试过程统一起来进行。使算法的复杂性大大降低。这种算法称为S D T(sequential fiagnostic tree)算法。     

饱和二部图

没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X(∈)V(G),T(X)表示V(G)中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=(U,W)是饱和的当且仅当(a)存在唯一X(∈)U,使得|X|＞Γ(X)|,|X|-1＞|Γ(X)|且G的导出子图G[X∪Γ (X)]是完全二部图;(6)G的导出子图G[(U-X)∪(W-Γ(X))]是完全二部图,且满足|U-X|+1=|W-Γ(X)|;(c)U-X中每个顶点与W中的每个顶点都相邻,且X∪(W-Γ(X))是图G的一个独立集.     

产生组合数字电路测试的九值*算法

本文为组合数字电路测试码的生成提出了一种新算法。它把四值*算法推广到电路的九值模型上,证明了四值*算法中的所有高次*项组合,均包括在本算法的单*项中,从而得到了单故障测试码生成的线性化结果。即使遇到需同时敏化多个通路才能求得测试码的情况,也只要计算单*项即可。因此有m个通路的单故障,最坏情况时,不必计算2~m-1种组合,只计算m个单*项。     

圆有向图中的泛弧

设D=(V,A)是一个有向图,uv是D上的一条弧。如果对于任意顶点w∈V(D),都有弧uv和顶点w包含在某个公共圈中,则称弧uv是D的一条泛弧。证明了圆有向图R的每条弧都是泛弧当且仅当R是一个圈或者R是2-强连通的且R不属于一类特殊的圆有向图。并由此给出了判断圆有向图的每条弧是否都是泛弧的多项式算法。     

一类二部图的奇优美性

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足:1)L为G的顶点集V到{0,1,…,2|E|-1}的一个单射;2)由L'(e)=|L(u)-L(v)|(其中e=uv)决定的边标号L'是从G的边集E到{1,3,…,2|E|-1}的一个双射.根据奇优美图的定义,研究了一类二部图G*的奇优美标号.     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

多通道流的几种算法

G=(N,A,u)是一个有始点s和终点t的有向网络,每条弧的容量限制为uij.多通道流问题是求解从始点s到终点t不仅要满足顶点平衡(始点和终点除外)和弧的容量限制下通常的最大流问题,而且这个流必需满足沿着K条弧不交的s-t路发送.它对通信领域、网络领域、军事领域和科学领域有许多重要意义,是计算机科学和运筹学领域的研究内容.经20多年来的研究和发展,多通道流问题已经形成几种不同的算法,本文主要对这几种算法进行总结和归纳.     

K条路的两个问题

关于寻找有向连通图G=(V,E)的最小最大的k条弧不交路的问题是NP-完备的.研究这个问题的推广———有容量限制的k条路问题:①寻找k条路,使得k条路的费用之和尽可能小;②寻找k条路,使得k条路中最长的路的费用尽可能小.给出了问题①的一个最优算法,其复杂度为O(k|V|2),同时证明了该算法对于问题是k-近似的.     

点接拟梯子的L(1,1)-标号

图G的一个L(2,1)-标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)|≥1;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为.那么,图G的L(1,1)-标号数λ(G)是是G的所有L(1,1)-标号下的跨度max{f(v);v∈V(G)}的最小数.完全确定了点接拟梯子的L(1,1)-标号数.     

拟梯子的L(1,1)-标号

图G的一个L(2,1)-标号就是从顶点集到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)|≥1;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为0.那么,图G的L(1,1)-标号数λ(G)是是G的所有L(1,1)-标号下的跨度max{f(v);v∈V(G)}的最小数.完全确定了拟梯子的L(1,1)-标号数.     

拟m(o)bius梯子的L(2,1)-标号

图G的一个L(2,1)标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)| ≥2;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)标号下的跨度max {f(v);v∈V(G)}的最小数.本文定义了拟m(o)bius梯子,并完全确定了拟m(o)bius梯子的L(2,1)标号数.     

拟梯子的L(2,1)-标号

图G的一个L(2,1)-标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)| ≥2;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v ∈ V(G)}的最小数.本文定义了拟梯子,并完全确定了拟梯子的L(2,1)-标号数.     

拟mbius梯子的L(2,1)-标号

图G的一个L(2,1)标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)|≥2;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)标号下的跨度max{f(v);v∈V(G)}的最小数.本文定义了拟mbius梯子,并完全确定了拟mbius梯子的L(2,1)标号数.     

一种弱相互作用结构模型

将同位旋与奇异数的概念推广到轻子,借助推广了的Gell-Mann-Ni-shijima公式,确定轻子的同位旋T与奇异数S。然后,从总奇异数的选择规则|△S|≤1出发,代替Feynman与Gell-Mann的“(总流)×(总流)”耦合形式的弱相互作用拉格朗日函数,我们得到一个由“流与流”耦合表征的弱相互作用拉格朗日函数。本模型具有以下一些主要性质:(i)能引起△S=±△Q的奇异粒子的轻子衰变;(ii)将禁戒|△S|>1的过程;(iii)奇异粒子的非轻子衰变近似地遵从|△(?)|=1/2定则;(iV)不存在中性轻子弱流;(Vi)能与传递弱相互作用的蹭矢量玻色子理论相容。     

用最小生成树解决TSP问题

旅行商问题(Traveling Salesman Problem，TSP问题)是组合优化领域中研究最多的问题之一，是一个经典的NP难题，也是目前优化领域里的研究热点。目前解决旅行商问题有诸多算法，神经网络、遗传算法、免疫算法等，在各种解决旅行商问题的算法中，还是存在很多问题。本用最小化生成树来求解旅行商问题。在对题目要求进行深入分析的基础上，对原有算法进行了多方面改进，并用C语言进行了实现。采用选取排除最长路径顶点的方法降低时间复杂度、采用比较顶点次序的方法提高算法准确性、通过自动产生顶点坐标降低输入复杂性和测试的准确性，实验结果表明该算法可以取得较好的效果。     

Irr(G|N)的一些性质

在给定了Irr(G|N)的某些条件下,讨论了导长dl(N)与|cd(G|N)|的关系,并给出了群N的一些结构,即定理1若NG且N可解,则dl(N)≤|Irr(G|N)|.定理2若NG,Irr(G|N)中所有特征标单项,则dl(N)≤|cd(G|N)|且N可解.定理3若NG,Irr(G|N)中每特征标维数不同且G可解,则下列情形之一成立(i)N有特征子群序列N=N0＞N1＞…＞Nk-1＞Nk=1使Ni+1为Ni的正规pi补;(ii)N为Abel群;(iii)N为超特殊2群;(iv)N为2可迁Frobenius群,且Frobenius补循环;(v)N为72阶2可迁Frobenius群,且Frobenius补为四元数群;在(ii)-(iv)中,N为偶阶群或N=1.