检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向图的条件弧连通度

有向图的条件弧连通度

作者：周婵婵山西大学

学位级别：硕士

在设计大型网络时,人们要考虑的一个基本问题是网络的可靠性(容错性),它可由图的边连通度来度量.为更精确地度量,人们推广边连通度,提出限制边连通度的概念.限制边连通度一经提出就得到了很多的关注.作为限制边连通度在有向图中的推广,... 详细信息

在设计大型网络时,人们要考虑的一个基本问题是网络的可靠性(容错性),它可由图的边连通度来度量.为更精确地度量,人们推广边连通度,提出限制边连通度的概念.限制边连通度一经提出就得到了很多的关注.作为限制边连通度在有向图中的推广,圈弧连通度λc(D)、强限制弧连通度λ2(D)、限制弧连通度λ’(D)分别被提出.本文提出限制边连通度的又一个推广—条件弧连通度.设D是一个强连通有向图.D的一个弧子集S是D的一个条件弧割,若D-S不是强连通的且它的最小度δ(D-S)≥1.称D是λ(1)-连通的,若它包含一个条件弧割.D的条件弧连通度,记为λ(1)(D),是D的一个最小条件弧割所含的弧数.Kautz图是有竞争力的大型网络-Kautz网络的拓扑结构.本文分为四章,将给出条件弧连通度的一些性质并确定有向Kautz图的条件弧连通度.第一章首先介绍将用到的一些图论基本概念和记号,然后给出本文的研究背景、主要概念和主要结果.第二章首先说明条件弧连通度是限制边连通度的一个推广,讨论条件弧连通度和强限制弧连通度A2(D),圈弧连通度λc(D),限制弧连通度λ’(D)之间的关系,证明对于存在一个强限制弧割的有向图D,λ2(D)≥ λ(1)(D)≥ λc(D)≥λ’(D),并用例子说明限制边连通度的这四个推广各不相同.Volkmann给出了有向图D的限制弧连通度λ’(D)的一个上界ζ(D).第三章证明了当一个有向图D的最小度大于它的围长时有λ(1)(D)≤ζ(D),并用例子说明了这个结果是最优的.作为应用,我们确定了有向Kautz图的条件弧连通度.超级弧连通性是与网络可靠性密切相关的一个图性质.第四章提出有向图关于超级弧连通性的弧容错度Sλ(D)的概念,用条件弧连通度给出超级弧连通性的一个特征刻画并用之研究Sλ(D)的界.作为应用,我们确定有向Kautz图关于超级弧连通性的弧容错度.

关键词：网络有向图 Kautz图限制边连通度最小度

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向图并行计算中的多目标剖分算法

有向图并行计算中的多目标剖分算法

作者：金光浩中国工程物理研究院

学位级别：硕士

在以离散网格为基础的科学计算数值模拟中,在某些情形下,网格间的计算顺序是单方向数据依赖的,这种依赖关系可以抽象为有向图。于是,这类科学数值模拟的并行计算可以抽象成为有向图的并行计算问题。如何剖分这些有向图成多个子图,将各... 详细信息

在以离散网格为基础的科学计算数值模拟中,在某些情形下,网格间的计算顺序是单方向数据依赖的,这种依赖关系可以抽象为有向图。于是,这类科学数值模拟的并行计算可以抽象成为有向图的并行计算问题。如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟有向图并行计算的基础。有向图并行计算可分解为三个部分,有向图剖分算法、结点的优先级算法和基于有向图剖分算法和结点优先级算法的扫描并行算法。有向图剖分算法中,我们需要综合考虑连通性、并行度、负载平衡、通信开销四个目标。本文在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法。应用于二维非结构网格上的柱对称中子输运并行计算中,基于该剖分算法的通量扫描并行算法的并行效率比基于非结构网格无向图剖分区域分解的相应并行算法的并行效率有明显的提高。具体分为六章。第一章简单分析离散网格为基础的科学数值模拟中有向图剖分的应用,指出了开展多目标剖分区域分解算法研究的必要性,总结了有向图剖分算法的发展状况和以往有向图剖分算法的不足。最后,简述了本文的主要工作。第二章介绍有向图并行计算的基本概念、有向图并行计算的评判准则和基于区域分解的扫描并行算法。第三章介绍有向图的结点优先级算法。第四章介绍多目标剖分区域分解算法,即如何根据图中结点的单方向数据依赖关系,将图剖分成P个子图,分配给P台不同的处理机,使得基于图剖分的扫描并行算法获得最高的并行效率。我们将相邻结点引入多目标剖分区域分解算法之后,相应地引入三个新概念,从而改进多目标剖分区域分解算法。第五章利用扫描并行算法对Iterative Kernigham-Lin(IKL)方法和改进前后多目标剖分区域分解算法给出的剖分进行比较,并对结果进行具体分析。实验结果表明我们的多目标剖分区域分解算法达到了预期的目标,并且某些性质方面比IKL方法有更好的效果,而改进后的算法比改进前的多目标剖分区域分解算法有更好的效果。第六章为结束语,总结了全文工作,展望了将来的研究重点。

关键词：有向图并行计算多目标剖分区域分解

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向图的圈可扩和点不交圈问题

有向图的圈可扩和点不交圈问题

作者：王志兰山东大学

学位级别：硕士

给定整数c ≥ 2,定义c-部扩展竞赛图D是c-部完全图的定向,并且满足:如果（x,y）∈A（D）,这里x∈Vi,y ∈Vj,那么Vi的每个点指向Vj的每个点.其中V1,…,Vc为D的部集.一个圈C是弱可扩的,如果存在圈C’,满足V（C）（?） V（C’）且|V（C’）... 详细信息

给定整数c ≥ 2,定义c-部扩展竞赛图D是c-部完全图的定向,并且满足:如果（x,y）∈A（D）,这里x∈Vi,y ∈Vj,那么Vi的每个点指向Vj的每个点.其中V1,…,Vc为D的部集.一个圈C是弱可扩的,如果存在圈C’,满足V（C）（?） V（C’）且|V（C’）|≤|V（C）|+2.若D含有圈且D的每一个非哈密顿圈C都是弱可扩的,则称D是弱圈可扩的.进一步,如果D是弱圈可扩的且对D中的每个点v,都有一个长度为3的圈包含v,那么称D是完全弱圈可扩的.本文证明了下列结果.结果1.令D是一个c-部扩展竞赛图,其中c ≥ 4.则D是弱圈可扩的当且仅当D有哈密顿圈.一个有向图D称为zigzag有向图,若V（D）=V1∪…∪Vc,其中|V（D）|≥5且c≥4,并且满足下列条件:A（V2,V1）=A（V,V2）=A（V1,Vi）=Φ,这里i∈{3,4,…,c}且 |V1|=|V2|=|V3|+…+|Vc|.结果2.令D是一个c-部扩展竞赛图,这里c ≥ 4.如果D有哈密顿圈且它既不是zigzag竞赛图也不是点数至少为5的4-部竞赛图,那么D是完全弱圈可扩的.对于有向图D中的点v,分别用dD+（v）和dD-（v）表示点v在D中的出度和入度.对于V（D）中的两个点u和v,用uv定义从点u到点v的弧.有向图D的1-因子F是图的一个支撑子图且满足:对每一个点v ∈ V（D）,均有dF+（v）=dF-（v）=1.换而言之,有向图D的1-因子是一个支撑子图并且该支撑子图的每一个分支都是一个圈.本文证明了下列结果.结果3.令k是一个正整数并且D是一个点数为n的有向图,这里n≥9k-1.如果对于D中每一对满足uv（?）A（D）的点u和v,均有dD+（u）+dD-（v）≥ n,那么D包含恰有k个圈的1-因子.

关键词：有向图扩展竞赛图弱圈可扩性点不交圈度条件

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

利用有向图求解数据表外键相互约束问题

计算机应用 2007年第B06期27卷 40-41,45页

作者：杨玉民夏清国西北工业大学软件与微电子学院陕西西安710072

针对大数据容量数据库移植过程中,由于数据表之间相互存在外键约束而导致数据无法写入的问题,提出了采用有向图理论分析求解的方案。该方案主要思想是,首先建立数据表外键相互约束关系有向图数学模型,然后通过进行矩阵运算和改进后的迪... 详细信息

针对大数据容量数据库移植过程中,由于数据表之间相互存在外键约束而导致数据无法写入的问题,提出了采用有向图理论分析求解的方案。该方案主要思想是,首先建立数据表外键相互约束关系有向图数学模型,然后通过进行矩阵运算和改进后的迪克斯特拉运算,求出建表次序,进而完成数据库移植。实践证明,该方法运算简便,易于用计算机程序实现,尤其适合求解具有复杂外键约束关系逻辑问题。

关键词：有向图数据库外键约束

在线全文

学校读者我要写书评

暂无评论

计费网关中基于有向图的IP地址组织

计算机工程 2004年第13期30卷 82-83,177页

作者：卢明华韩毅刚南开大学信息科学学院天津300071

设计了一个基于Linux网桥的计费网关,该网关使用一个有向图来描述全部IPv4地址。讨论了网桥模块中IP地址的组织方法,并对内存分配进行了一些简单管理。

关键词：树有向图 IP地址网桥

在线全文

学校读者我要写书评

暂无评论

一个通用的有向图故障诊断算法

信息与控制 1989年第6期18卷 1-4页

作者：钱大群张钟俊上海交通大学自动控制系

在符号有向图故障诊断算法和有向图反向搜索事故定位方法的基础上,本文提出了一个通用的有向图故障诊断算法.它具有更丰富更灵活的知识表达方式和更广泛的故障诊断范围。

关键词：有向图故障诊断知识表达算法

在线全文

学校读者我要写书评

暂无评论

基于有向图分析的集群识别方法研究

科学学与科学技术管理 2007年第4期28卷 75-79页

作者：骆静华中科技大学管理学院湖北武汉430074

对基于有向图分析的集群识别方法进行了全面分析,系统地阐述了该方法的核心工具——有向图表以及创新交互矩阵,并重点对9种集群有向图进行了深入的研究分析,提出并详细剖析了基于有向图分析的集群识别方法在应用过程中存在的优点和缺陷。

关键词：集群识别有向图

在线全文

学校读者我要写书评

暂无评论

基于有向图的关联规则挖掘算法研究

云南大学学报（自然科学版） 2006年第S2期28卷 119-121,125页

作者：唐德权夏耀稳朱林立夏幼明云南师范大学计算机科学与信息技术学院云南昆明650092

为了提高关联规则挖掘效率,提出了一种基于有向图的频繁项目集挖掘算法DGBFIG(Directed graph -based frequent itemsets generation)．该算法采用位矢量技术构造有向图,表示项与项之间的频繁关系,并在有向图的基础上递归产生频繁项集,... 详细信息

为了提高关联规则挖掘效率,提出了一种基于有向图的频繁项目集挖掘算法DGBFIG(Directed graph -based frequent itemsets generation)．该算法采用位矢量技术构造有向图,表示项与项之间的频繁关系,并在有向图的基础上递归产生频繁项集,从而只需扫描数据库2次,不产生候选集,从而大大提高了关联规则挖掘算法的效率．最后从空间和时间的复杂度分析了该算法的效率．

关键词：数据挖掘有向图频繁项集位矢量

在线全文

学校读者我要写书评

暂无评论

基于有向图的对象范式生成算法

软件学报 2004年第5期15卷 730-740页

作者：刘国华汪卫张亮施伯乐复旦大学计算机与信息技术系燕山大学计算机科学与工程系河北秦皇岛066004

对Tari等人提出的面向对象数据模型规范化理论的基本思想进行了介绍,分析了他们给出的对象范式生成方法,指出了这些方法所存在的问题.为了研究新的对象范式生成方法,对有向图顶点的含义进行了扩充,使其不仅可以是一个简单的顶点,还可以... 详细信息

对Tari等人提出的面向对象数据模型规范化理论的基本思想进行了介绍,分析了他们给出的对象范式生成方法,指出了这些方法所存在的问题.为了研究新的对象范式生成方法,对有向图顶点的含义进行了扩充,使其不仅可以是一个简单的顶点,还可以是一个有向图.基于这种扩充有向图,提出了一种对象范式生成算法,并给出了算法的时间复杂度分析和正确性证明.

关键词：面向对象数据模型规范化范式有向图