超图理论及其应用

综述了超图理论及其应用方面的主要研究成果，提出了一些新的概念和研究途径，探讨了超图理论及其应用方面的四个课题，讨论了超图理论及其应用的发展前景，提出了一些尚待研究的问题。     

基于有向超图的工作流资源分配均衡优化方法

为了拓展工作流资源分配均衡优化的深度和广度,提出了一种考虑过程支持资源变化与过程结构变化相互影响的优化方法.通过对过程进行扩展超图建模,利用超图的性质以及活动能力需求集与支持资源能力集之间的耦合,给出了过程结构随支持资源变化而变化的形式化处理规则;给出了由不同结构过程构成的、用于工作流资源分配均衡优化超图模型(DHM-WRAB)的建模规则,使工作流资源分配均衡优化转化为具有权因子的超图最短路径求解问题,并给出求解过程;最后,通过举例证明该方法可行、有效.     

应用超图理论实现有向基本割集矩阵

本文应用超图理论提出了从有向基本割集矩阵Qf的树路子阵Qfp逐层判断其可实现性和综合出其对应有向图(G)的算法RFCMHGT。它的原理直观,计算复杂度为O(nl2),n和l为Qfp的行和列数。例2表明,Tutte条件不是Qf可实现的充分条件。     

基于层次式有向超图模型的胚胎硬件功能描述转换方法

当前胚胎硬件的实际工程应用受到限制,原因在于其应用设计自动化程度低,功能分化主要由人工完成,导致大规模电路功能分化难以实现.基于大规模电路功能分化的需要,针对典型多层胚胎硬件结构,提出了胚胎硬件功能的层次式有向超图描述及其存储方式,开发了基于正则匹配的硬件语言描述到层次式有向超图的转换算法,从而有效地将胚胎硬件功能分化问题转换为不同粒度的超图划分问题.为了建立分粒度层次式有向超图模型,进而设计并实现了胚胎硬件的硬件语言描述到有向超图的转换系统（Hypergraph For Embryonics, HGFE）.实验及分析表明,该系统适用于几十门至几万门的测试电路,为胚胎硬件功能分化提供了良好的图论模型,并和有向无环图对比,建模时间减少了至少28.7%,存储空间减少了至少30.1%,验证了该方法的优越性.     

超边分解集的递推公式

本文引入了超边的无向分解和有向分解的概念,导出了m点超边的无向分解集SD(m)和有向分解集SPD(m)的递推公式,进而得到它们的基数|SD(m)|和|SPD(m)|的递推公式。     

计算大型有向网络可靠度的一种新方法

本文提出了计算大型有向网络可靠度的一种新方法,它是以网络流理论为基础的分解算法。把大型网络按照本文给出的规则划分为若干子网络,再利用本文提出的收缩顶点概念和分解算法,可求出大型有向网络可靠度。     

生成有向图的有向通路和有向回路的一个新算法

本文首先定义了顶点的边,度关系矩阵,由此形成通路矩阵。证明了通路矩阵生成有向通路和有向回路的条件,提出了一个系统地,无重复地生成有向的全部有向通路和向回路的新算法。     

有向矩阵的广义讯号流图

本文把讯号流图推广到有向矩阵系统，提出一种广义的讯号流图定义及其拓扑法则，并给出了复杂网络系统的若干应用实例。     

一个计算无圈有向网络可靠度的新算法

本文对无圈有向网络的可靠度计算进行了研究。提出了加权有序根树的概念，给出了路径集合的一种特殊排序方法，导出一个计算无圈有向网络可靠度的拓扑公式。在该公式的基础上提出了一个新的计算无圈有向网络可靠度的不交积和算法，算法可以生成简洁的可靠度表达式，从而可以有效地计算无圈有向网络的可靠度。同时验证了算法的有效性。     

有向传感器网络覆盖控制策略

针对当前的有向传感器网络覆盖控制算法中主要存在的节点方向调节受限、优化程度有限、算法适用性单一等问题,提出了一种有向传感器网络覆盖控制策略(CCS,coverage control strategy),该策略经过严格的数学推导,形成一个分布式算法,能够广泛适用于不同网络下的不同节点感知模型。仿真实验表明,传感器节点运行CCS能够有效增强网络覆盖,并相比于现有的几种同类算法,具有一定的优越性。     

一般k阶余因式的k超连接表达式和分解定理

本文应用有向超图理论提出了线性系统不定参数矩阵Y的一般k阶余因式Y(ii)的两个k超连接表达式,并根据它导出了Y(ii)的一个分解定理。应用该定理容易对任意线性大系统进行多层撕裂和分析。这是一种新的多层拓扑分析方法,它可以扩大一台计算机所能拓扑分析的系统规模。     

子网络抽取定理和多端反馈网络的拓扑公式

本文提出了混合图关于二点对和超边分解的变形图的概念,应用它们和有向超图理论导出了参数抽取定理和子网络抽取定理的拓扑公式,进而导出了多端反馈有源网络的拓扑公式。公式中反馈子网络与基本子网络的参数是分开的,便于看出反馈参数的影响;而且由于把一个网络分解成二个较小的子网络,可以降低计算的时间复杂度和空间复杂度。     

基于有向感知模型的传感器网络密度控制算法

密度控制是一种常用的延长大规模传感器网络工作寿命的方法,现有的密度控制算法大多基于全向感知模型,而满足有向感知模型的传感器网络也颇具实际应用价值.文中提出一种基于有向感知模型的传感器网络密度控制算法,在保证一定网络覆盖能力的前提下,有效地休眠冗余有向感知节点,降低网络总能耗,延长网络工作寿命.     

基于效用最大化的无线可充电传感器网络有向充电调度方案

针对当前无线可充电传感器网络(WRSNs)一对一移动充电方式存在充电效率低、定向充电模型缺乏问题,该文提出了一种基于充电效用最大化(MUC)的一对多有向充电调度方案.方案首先筛选网络中充电增益最大的有向覆盖子集;然后根据有向覆盖子集确定充电锚点,并进而规划充电器的移动路径;最后在满足移动充电器能量和充电周期约束条件下优化移动充电器的充电时间.实验结果表明,该方案与平均能量充电(AEC)、固定能量充电(FEC)相比,充电效率分别提高了13.7%和32.7%;与最多节点覆盖(MNC)、最大平均增益覆盖(MAGC)子集筛选方案相比,充电效率分别提高了4.4%和35.9%;同时在网络饿死节点数目上与MNC, MAGC方案相比也显著降低.     

基于效用最大化的无线可充电传感器网络有向充电调度方案

针对当前无线可充电传感器网络(WRSNs)一对一移动充电方式存在充电效率低、定向充电模型缺乏问题,该文提出了一种基于充电效用最大化(MUC)的一对多有向充电调度方案。方案首先筛选网络中充电增益最大的有向覆盖子集;然后根据有向覆盖子集确定充电锚点,并进而规划充电器的移动路径;最后在满足移动充电器能量和充电周期约束条件下优...