检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

图和有向图的测地数

中国科学（A辑） 2007年第5期37卷 579-586页

作者：吕长虹华东师范大学数学系华东师范大学计算机理论研究所上海200062

图G内的任意两点y和v,u-v测地线是指u和v之间的最短路．I(u,v)表示位于u-v测地线上所有点的集合,对于子集S (?) V(G),I(S)表示所有I(u,v)的并,这里u,v∈S．图G的测地数g(G)是使得I(S)=V(G)的点集S的最小基数．对于有向图D,类似地可定义g... 详细信息

图G内的任意两点y和v,u-v测地线是指u和v之间的最短路．I(u,v)表示位于u-v测地线上所有点的集合,对于子集S (?) V(G),I(S)表示所有I(u,v)的并,这里u,v∈S．图G的测地数g(G)是使得I(S)=V(G)的点集S的最小基数．对于有向图D,类似地可定义g(D)．图G的测地谱是G的所有定向图的测地数的集合,记为S(G)．G的下测地数g-(G)=minS(G),上测地数g+(G)=maxS(G)．文中主要研究了连通图G的g(G), g-(G)和g+(G)之间的关系．同时,还给出g(G)和g(G×K2)相等的充分必要条件,从而推广了Chartrand,Harary和Zhang的相关结论．

关键词：凸集有向图距离测地线测地数

在线全文

学校读者我要写书评

暂无评论

三维管网泄漏物流向的有向图分析

测绘科学 2022年第2期47卷 166-172,206页

作者：金恒旭罗安李晓燕徐胜华辽宁工程技术大学测绘与地理科学学院辽宁阜新123000 中国测绘科学研究院北京100036

针对城市应急安全管理中面临的水、燃气泄漏问题,为对泄漏管线进行直观精准监控,该文提出了一种利用有向图进行三维管网流向分析的算法。采用正向的广度优先遍历算法构建基于有向图的管网拓扑几何模型后,对管网流向正确性进行核查,并在... 详细信息

针对城市应急安全管理中面临的水、燃气泄漏问题,为对泄漏管线进行直观精准监控,该文提出了一种利用有向图进行三维管网流向分析的算法。采用正向的广度优先遍历算法构建基于有向图的管网拓扑几何模型后,对管网流向正确性进行核查,并在步进搜索中采用嵌套循环的递归方式对管网数据遍历访问,再利用二维网络模型映射三维管网,最后将三维箭头适量间断性标记在三维管网中,实现在步进搜索过程中自动获取泄漏物所流经的三维管线。实验分析表明,该文算法与SQL数据库查询、传统网络模型分析方法相比,在海量数据下获取管网泄漏物流径的效率显著提高。

关键词：有向图流向分析广度优先遍历算法三维管网海量数据

基于有向图故障树自动建树方法的规范化描述及其应用研究

在线全文

学校读者我要写书评

暂无评论

自动化学报 2003年第5期29卷 767-772页

作者：钱彦岭邱静温熙森国防科技大学机电工程研究所长沙410073

基于有向图的建树方法是目前故障树自动建树研究中最常用的方法之一 ,但其有效性多年来一直存在争议 ,其主要原因在于采用传统的专家定义的算子进行建树推理时 ,算子定义不规范 ,导致对系统复杂的控制结构适应能力不强 .该文利用人工智... 详细信息

基于有向图的建树方法是目前故障树自动建树研究中最常用的方法之一 ,但其有效性多年来一直存在争议 ,其主要原因在于采用传统的专家定义的算子进行建树推理时 ,算子定义不规范 ,导致对系统复杂的控制结构适应能力不强 .该文利用人工智能的原理 ,对定性推理逻辑进行了必要的扩展 ,提出了建树过程的形式化描述 ,在此基础上将故障树的建树问题转化为一个约束满足问题 (CSP) ,从而可利用比较成熟的算法来解决上述问题 .针对实际问题的例证说明了这一过程 .研究表明 ,文中所提出的方法更便于计算机自动处理 ,减少建树过程中的人为失误 ,可有效地提高故障分析效率 .

关键词：约束满足问题有向图故障树自动建树方法规范化描述人工智能

无回路有向图的深度第一支撑树的快速并行算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 1990年第11期13卷 808-814页

作者：张益新大连海运学院计算机系

Ghosh和Bhattacharjee在[1]中提出的无回路有向图的深度第一支撑树的并行算法是错误的。本文解决了一般无回路有向图的深度第一支撑树的快速并行算法。其时间复杂度及处理器复杂度分别为O(log^2n)及O(n^3/log n)。

关键词：有向图深度第一支撑树并行算法

在线全文

学校读者我要写书评

暂无评论

有向图和定向图的边连通性研究

有向图和定向图的边连通性研究

作者：王艳红山东师范大学

学位级别：硕士

图论是一门古老而又活跃的学科,也是一门很有实用价值的学科.它是研究工程技术,自然科学等的重要数学工具,应用极为广泛.在现代社会中,人们的日常生活,学习和工作与多处理机互联网络的关系也越来越密切.因此网络的可靠性和容错性受到人... 详细信息

图论是一门古老而又活跃的学科,也是一门很有实用价值的学科.它是研究工程技术,自然科学等的重要数学工具,应用极为广泛.在现代社会中,人们的日常生活,学习和工作与多处理机互联网络的关系也越来越密切.因此网络的可靠性和容错性受到人们的普遍关注,从而网络的可靠性和容错性的研究成为了近年来国内外研究的一大热点.在设计和分析大规模互联网的可靠性和容错性时,一个很重要的模型是将网络的拓扑结构抽象成图或有向图D=(V,E).D的顶点代表处理机,连接顶点的边表示一对处理机之间的直接通信联系(有向边则表示只能进行单向联系).研究这种模型时,假设其节点不会失效,但每条边相互独立地以相等的概率p∈(0,1)失效.则D不连通的概率为：其中m表示D的边数,λ(D)表示D的边连通度,Ci(D)表示D的边数为i的边割数目,因而可用D连通的概率R(D,p)=1—P(D,p)来衡量网络的可靠性.显然P(D,p)越小,网络的可靠性越好,但是对于一般图,确定所有的系数G是NP-困难的.对此,Colbour[2]做了进一步的阐述.当假设D的边不会失效,但其节点相互独立地以相等的概率p∈(0,1)失效时也有类似的讨论.图或有向图的边连通度是反映其连通性质的一个重要参数.而在精确刻画图或有向图的连通性方面,经典边连通度存在一些不足：首先,边连通度相同的图或有向图的可靠性可能有所不同.其次,不能区分删掉λ-割后所得图或有向图的不同类型.最后,默认图或有向图的任何子集中所有元素可能潜在地同时失效.为了克服以上缺陷,自1983年Harary[5]提出了条件边连通度的概念,经过三十多年的发展,边连通性所涉及的内容日益丰富和具体,其中包括极大边连通性、超级边连通性、极大局部边连通性和超级局部边连通性等.目前,对于这一邻域已有了广泛而深入的研究.本人在前人工作的基础上,继续研究图或有向图的边连通的相关性质.本文主要研究有向图与定向图的边连通性的一些条件.在第一章中,主要介绍本文的研究背景和一些已有的结果,以及文章中涉及的一些基本概念、术语符号.在第二章中,首先给出定向图依赖于团数的超级边连通性的度序列条件：为简洁起见,本章所讨论的定向图的阶数n为偶数时,令v=1,否则,令v=0;当所讨论的定向图的团数ω(D)≤p,最小出度,最小入读,最小度分别为δ+,δ-,δ时,令定理2.1.5 设D是n阶定向图,团数ω(D)≤p且p≥4,出度序列为d1+≥d2+≥…≥dn+(=δ+≥2),入度序列为d1-≥d2-≥…≥dn-(=δ-≥2).若则D是超级边连通的.定理2.1.6 设D是n阶定向图,团数ω(D)≤p且p≥4,度序列为d1≥d2≥…≥若则D是超级边连通的.定理2.1.7 设D是n阶定向图,团数ω(D)≤p且p≥4,n为偶数,度序列为d1≥若则D是超级边连通的.然后又讨论了有向图和定向图极大局部和超级局部边连通依赖于团数的度序列条件,得到了以下结果：定理2.2.4 设D为n阶定向图,团数ω(D)≤p,度序列为d1≥d2≥…≥dn(=δ),△’=△’(D).若n≤4[pδ/p-1]-1或若n≥4[pδ/p-1]且对某整数k,1≤k≤2δ+1,有则D是极大局部边连通的.定理2.3.4 设D为n阶有向图,团数ω(D)≤p,度序列为d1≥d2≥…≥dn(=δ),△’=△’(D).若n≤2[pδ/p-1]-1或若n≥2[pδ/p-1]且对某整数k,1≤k≤[pδ/p-1],有则D是极大局部边连通的.定理2.3.11设D为n阶有向图,团数ω(D)≤p,度序列为d1≥d2≥…≥dn(=δ≥3),△’=△’(D).若n≤2[pδ/p-1]-3或若n≥2[pδ/p-1]-2且对某整数k,1≤k≤[pδ/p-1]-1,有则D是超级局部边连通的.在第三章,首先给出了有向图极大局部边连通的度序列条件：定理3.1.3设D为n阶有向图,度序列为d1≥d2≥…≥dn(=d),△’=△’(D).若δ≥[n/2]或若δ≤[n2/]-1且对某整数k,1≤k≤δ+1,有则D是极大局部边连通的.接着又讨论了二部有向图和定向图的边连通性的度序列条件：定理3.2.3设D为n阶二部有向图,度序列为d1≥d2≥…≥dn(=δ).若δ≥[到+1或若δ≤[n/4]且对某整数k,1≤k≤δ,有则D是极大边连通的.定理3.2.5设D为n阶二部定向图,度序列为d1≥d2≥…≥dn(=δ≥2).若δ≥[n+3/8]或若δ≤[n+2/8]且对某整数k,1≤k≤4δ-1,有则D是超级边连通的.定理3.2.7(1)设D为n阶二部定向图,度序列为d1≥如≥…≥dn(=δ≥1),△’=△’(D).若δ≥[n+1/8]或若δ≤[n/8]且对某整数k,1≤k≤4δ,有则D是极大局部边连通的.(2)设D为n阶二部定向图,度序列为d1≥d2≥…≥dn(=δ≥2),△

关键词：有向图定向图极大(超级)边连通性极大(超级)局部边连通性倒数度

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于时序约束模糊有向图的电网故障诊断

控制工程 2016年第6期23卷 800-811页

作者：陈晋音何辉豪周晓杨东勇浙江工业大学信息工程学院杭州310000

对电网故障进行快速而准确的诊断对电网的安全运行至关重要。针对SCADA获取的警报信息不完备情况,提出了一种基于时序模糊有向图(Time Constraint Fuzzy Directed Graph,TCFDG)的故障诊断方法,利用时序约束有效识别警报信息的丢失、误... 详细信息

对电网故障进行快速而准确的诊断对电网的安全运行至关重要。针对SCADA获取的警报信息不完备情况,提出了一种基于时序模糊有向图(Time Constraint Fuzzy Directed Graph,TCFDG)的故障诊断方法,利用时序约束有效识别警报信息的丢失、误报、时序不一致情况,并对错误警报信息进行过滤,克服警报信息不完备缺陷,为精确定位故障源提供保障;其次提出了基于时序模糊有向图的推理方法,利用时序关联矩阵的最小运算和乘法运算确定故障源,并采用关联矩阵约简的方法,降低了矩阵的维数,提高诊断速度。最后,用典型电力系统发生的故障案例对所提出的方法进行了说明,并与已有几种典型先进方法比较,验证了所提出诊断方法的优势。

关键词：故障诊断时序属性有向图电力系统关联矩阵约简

在线全文

学校读者我要写书评

暂无评论

对称本原有向图的重上广义本原指数

应用数学学报 1998年第2期21卷 161-164页

作者：高玉斌邵燕灵华北工学院理学系太原030051

一个有向图D称为本原有向图，若存在某自然数κ，使D中任一点u到任一点υ都有长为κ之途径．若D是一个对称有向图，则D是本原的当且仅当D对应的无向图G连通且至少包含一个奇圈．本文中，我们将决定具有最小奇圈长r的n阶对称本原有向图... 详细信息

一个有向图D称为本原有向图，若存在某自然数κ，使D中任一点u到任一点υ都有长为κ之途径．若D是一个对称有向图，则D是本原的当且仅当D对应的无向图G连通且至少包含一个奇圈．本文中，我们将决定具有最小奇圈长r的n阶对称本原有向图的第κ重上广义本原指数的最大数．

关键词：有向图本原指数广义对称本原有向图

在线全文

学校读者我要写书评

暂无评论

有向图极大方向Wiener指数研究

有向图极大方向Wiener指数研究

作者：江云涛中北大学

学位级别：硕士

拓扑指数在化学图论中是一个十分重要的研究课题,它在化学分子构造中有重要的应用.其研究和发展前景非常广阔.本文我们首先介绍了Wiener指数关于无向图和有向图的定义;其次研究了有向图极大方向的Wiener指数,总结了具有最大、第二大Wie... 详细信息

拓扑指数在化学图论中是一个十分重要的研究课题,它在化学分子构造中有重要的应用.其研究和发展前景非常广阔.本文我们首先介绍了Wiener指数关于无向图和有向图的定义;其次研究了有向图极大方向的Wiener指数,总结了具有最大、第二大Wiener指数的有向图的极值和对应的极图,给出了具备第三大Wiener指数的有向图的极值和极图.在第一章中,我们介绍Wiener指数的研究历史,给出了一些基本的概念、相关的结论及本文的主要结果.在第二章中,我们首先给出了Wiener指数在有向图中的一些重要定理并总结了具有最大、第二大Wiener指数的有向图的极值以及对应的极图;接着通过分类讨论和反证等方法得出了具有第三大Wiener指数的有向图的极值和对应的极图.

关键词： Wiener指数有向图平均距离网络

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向图子图同构计算算法研究

有向图子图同构计算算法研究

作者：吴楠辽宁大学

学位级别：硕士

图作为一种通用的数据结构，被广泛地用来描述复杂的半结构化或结构化数据，例如：万维网(WWW)、生物信息学、可扩展标记语言(XML)、社会关系网络、软件和数据工程、化合物集合与基因网络等等。随着图这种数据结构不断的在各领域内的成... 详细信息

图作为一种通用的数据结构，被广泛地用来描述复杂的半结构化或结构化数据，例如：万维网(WWW)、生物信息学、可扩展标记语言(XML)、社会关系网络、软件和数据工程、化合物集合与基因网络等等。随着图这种数据结构不断的在各领域内的成功应用，迅速的累积了大量的图数据。但是，由于图数据本身的复杂性，随着图数据量急剧的增加，不但没有使本文享受获得信息的便利，反而使本文的研究工作与学习更加的难以展开。最近几年，对于累积的大量图数据（即图数据库）如何进行管理，正逐渐地受到研究者们的关注。在大量的数据图的集合中检索出本文所需要的数据图，这些数据图要包含某个给定的数据图。这个给定的数据图就叫做查询图。这种检索包含查询图的算法叫做子图同构计算算法（或者叫子图查询算法）。子图同构计算算法具有很强的现实和实际的意义，其主要包括两种类型：第一种是精确子图同构计算;第二种是相似性子图同构计算。给定一个图数据库Ｄ及一个查询图q，精确子图同构计算定义为{g∈D|g′g，其中g′与q是同构图}，相似性子图同构计算的定义为{g∈D|g′g，其中g′与q是相似图}。子图同构计算的一个典型应用就是从海量图数据中获取用户所需要的相关知识。子图同构计算与传统的查询技术相比，具有很多的特点或者说是难点。例如：图数据的种类繁多，数据结构复杂多变，对于操作和控制要求比较高;在图查询领域中子图同构的问题是不可规避的最基本操作之一。正是由于这些难点的存在，所以子图同构计算技术的研究充满了挑战。现存的子图同构计算的算法大多都是应用在无向图上的，应用在有向图中的算法很少。因此，本文的目标是开发一种有向图精确性子图同构的计算算法，本文对一个应用在无向图中的子图同构计算算法做出更改，使其可以应用在有向图中。并且在这个基础之上，开发出一种可以进行有向图相似性的子图同构计算算法。通过许多真实和人工合成数据的试验，得出了大量的实验结果，达到了算法设计的预期。

关键词：有向图子图同构精确性子图同构相似性子图同构