关于图的分数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-因子。     

图的最短路径和传递闭包的并行算法

1.图的最短路径 给定一赋权有向图G=(V,E),假设G中没有带负权圈的顶点,Floyd给出了一个计算G的所有顶点对v_i,v_j之间最短路径算法。在该算法中,用带权邻接矩阵cosT表示图,并规定cosT(i,j)=∞若(i,j)不属于E和cosT(i,j)=0,i,j=0,…,n-1,该算法的设计思想是按下面的递推规则依次产生矩阵序列A~0,…,A~(n-1),其中A~(n-1)即是G的所有顶点对之间最短路径的长度。     

基于局部比值法的强弦图带权控制集问题的线性时间算法

一个无向图G＝(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V－D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。     

传输子网选择:度数有界最大支撑子图逼近

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。     

强竞赛图的强连通性

D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向图T中任意两个顶点之间恰有一条弧,则称T为竞赛图。一个强连通的竞赛图T称为强竞赛图。论文研究顶点个数大于的强竞赛图T的性质,并利用该性质给出了Moon定理的另外一种证明。     

网络拓扑的超能整循环图构造

循环图是一类重要的网络拓扑结构图,在并行计算和分布计算中发挥重要作用。图[G]的能量[E(G)]定义为图的特征值的绝对值之和。具有[n]个顶点的图[G]称为超能图如果图[G]的能量[E(G)>2n-2]。一个图称为循环图,若它是循环群上的Cayley图,即它的邻接矩阵是一个循环矩阵;整循环图是指循环图的特征值全为整数。借助Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性。利用Cartesian积图给出了一个构造超能整循环图的方法。     

欧式平面上瓶颈Steiner树问题的一个近似算法

近些年来，Steiner树问题在理论和应用上都引起了极大的关注，尤其在日渐成熟的近似算法设计理论方面，该问题占有一定的中心地位。给定赋权连通图G=(V，E，W)及顶点子集S包含V(S中顶点称为terminals)，传统的Steiner树问题要求寻找一棵最小的树联接5中的所有顶点，该树可能包含V-S中的顶点(称为Steiner点)。即使图中每条边的权值仅限制为1或2时，传统的Steiner树问题仍然是MAX—SNP Hard。     

(0,mf-m+1)图的正交(0,f)因子分解

设G是一个图,f是定义在V(G)上的整数值函数,且对坌x∈V(G),有2k≤f(x),设H1,H2,…,Hk是G的k个顶点不相交的子图,且|E(Hi)|=m,1≤i≤k,证明了每个(0,mf-m+1)图有一个(0,f)因子分解正交于Hi(i=1,2,…,k)。     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

两个多色顶点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。     

链图的概念格表示

概念格是基于对象集和属性集之间的二元关系建立的一种层次结构。它与极大二部团存在着一定的联系。将概念格属性约简理论应用于链图,首先给出了链图的概念格表示,其次证明了二部图G=(V1,V2,E)是链图,当且仅当G′=(V1,V2,E)是链图,这里(V1,V2,E)是(V1,V2,E)的约简形式背景。     

图上STEINER树问题及其近似算法

1.图上STEINER树问题是NP-完全的 著名的网络上Steiner问题是:对给定图G=(V,E),其中V=PUS,在边集E(G)上定义权函数f:E(G)→Z~ ,构成网络N(G,f)。要求在网络N(G,f)上寻找一棵子树T=(Y,u),使得P(?)Y,且     

内部节点受限的最小生成树问题算法研究

研究内部节点受限的最小生成树问题：给定一个赋权无向完全图[G=V,E],假定[w:E→R+]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。     

边故障[k]元[n]立方体的超级哈密顿交织性

[k]元[n]立方体（记为[Qkn]）是优于超立方体的可进行高效信息传输的互连网络之一。[Qkn]是一个二部图当且仅当[k]为偶数。令[G[V0,V1]]是一个二部图,若（1）任意一对分别在不同部的顶点之间存在一条哈密顿路,且（2）对于任意一点[v∈Vi],其中[i∈{0,1}],[V1-i]中任意一对顶点可以被[G[V0,V1]-v]中的一条哈密顿路相连,则图[G[V0,V1]]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的,所以研究网络的容错性就尤为重要。针对含有边故障的[Qkn],其中[k4]是偶数且[n2],证明了当其故障边数至多为[2n-3]时,该故障[Qkn]是超级哈密顿交织图,且故障边数目的上界[2n-3]是最优的。     

有向无环图最小度生成树问题的一种近似算法

计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.     

无向圆盘图中最大r跳独立邻居数的估计

本文考虑无向圆盘图中的最大r-跳独立邻居数(r≥2)。给定一个圆盘图G=(V,E),对任意v?V,用N'(V)表示所有距节点v跳数最多为r的节点集合,则对G中任何一个r-跳独立集I,其在N'(V)内最多有β个节点,■这里K是圆盘图的最大圆盘半径与最小圆盘半径的比值.     

关于Bubblesort-star网络的距离控制数

对于任意的正整数l,连通图G的顶点子集D被称为距离l-控制集,是指对于任意顶点v(∈)D,D中至少含有一个顶点u,使得u和v在G中的距离不超过l.图G的距离l-控制数是指G中所有距离l-控制集的最小基数,1-控制数常常称为控制数.给出了Bubblesort-star网络的控制数、距离2-控制数和距离3-控制数的界,而且针对某些低维Bubblesort-star网络的这几类控制数给出了更好的界.     

一个求图的连通分支的并行算法

已知一个无向图G(V,E),|V|=n,|E|=m,本文基于SIMD共享存贮模型,运用数据在图中快速传播原理,建议了一个新的求图的连通分支算法,具体来讲,在SIMD—CREW共享存贮模型上,求图的连通分支需O(log²n)时间、O(n²/logn)处理器;而在SIMD—CRCW共享存贮模型上需O(logn)时间、O(n²)处理器,建议的算法同著名的Hirschberg算法相比,其主要差别表现在:1)采用的求解方法不同;2)建议的算法简单易懂     

无向图中连通支配集问题的精确算法

图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。     

带权混合支配问题的近似算法研究

图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为w_v,所有边的权重均为w_e,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。