轮图的边不交生成树类的数目

借助图的删除点、增加点、删除边和增加边等基本运算,刻画图的最小度顶点在生成树中是2度顶点的生成树结构性质.进一步地,运用递推方法,给出轮图的边不交生成树类的数目计算公式.

统计数据分析的若干挑战与进展

大数据时代,数据的特征相较以往已经发生了巨大的变化,从而对传统的统计数据分析提出了新的挑战.本文将从若干角度介绍大数据分析的机遇与挑战,并回顾近年来在相关领域的研究进展.

LDPC码的树图法构造

LDPC码译码采用的是BP算法,但由于回路的存在,使译码重复迭代,特别是短长度的回路使LDPC码的性能下降。为此,用树图法分析了LDPC码的回路及其特性,给出了求解回路长度和所经过节点的方法,非常适合于计算机进行求解。同时也用树图的方法来构造LDPC码,可以在树生成的过程中了解其中的回路数目及长度。

模糊图论在山西植被区划中的应用

本文用模糊图论的最大树方法对山西植被区划进行了数量分类研究,将山西植被分为2个植被地带,6个植被地区,17个植被小区。与在植物群落学中应用的模糊聚类分析和其它方法相比,模糊图论的最大树方法直接依模糊相似系数矩阵得到树状图,从而避免了相似系数矩阵复杂的合成运算,而分类结果不仅更具直观性,而且也是令人满意的。我们认为模糊图论应用于植被区划是合适的。

基于最小生成树的图像分割

基于最小生成树思想,给出了一种利用改进的最小生成树进行图像分割的方案,减少了最小生成树的构建过程,对初分割的结果利用NNG算法进行合并。该方案节约了分割时间,并且对分割后的图像进行了有效的合并,达到了较好的分割效果。

基于图论分析法的舰艇作战系统损伤评估研究

舰艇作战系统损伤评估是舰艇损伤评估的重要组成部分。舰艇作战系统损伤评估可以采用损伤树分析法,但是损伤树分析法难以精细的评估舰艇作战系统的损伤,现采用图论分析法对其进行损伤评估。图论分析法评估的步骤如下:首先,建立舰艇作战系统的作战运行模型;其次,将舰艇作战系统的作战运行模型转化为损伤评估的图论模型;再次,对图论模型进行求解。为了对比分析,最后分别运用图论分析法和损伤树分析法进行舰艇反潜模型的损伤评估。从评估结果可以得出:图论分析法的分析结果更全面、精确,更适合评估舰艇作战系统的损伤。

基于图的脑组织磁共振图像分割方法

提出一种基于图的层次聚类算法实现脑组织磁共振图像的自动分割。首先,采用基于图的分割方法对脑组织MR图像进行初始分割。由于脑组织MR图像各类组织结构分布复杂,尤其是脑脊液和灰质区域细节信息丰富、结构变化多样,分割结果中存在过分割现象。因此,利用对偶树复小波变换高频子带信息构造基于图的分割方法中参数k的自适应取值函数,避免图像平滑区域分割后产生大量小区域。然后,以层次聚类算法合并分割得到的小区域,解决基于图的方法分割脑组织MR图像中存在的过分割问题。最后,通过大量真实脑组织MR图像实验证明该方法在脑组织MR图像分割中的准确性和稳定性。

最小树求解的表上作业法

最小树的求解一般采用破圈法求解,称此法为图上作业法。本文对此进行了改进,采取用赋权值构造的表格来求解图G的最小树--------最小树的表上作业法。

全符号网络函数的割裂分析法

本文提出了一种形成一般线性网络的全符号网络函数的新的树值算法—割裂分析法.此方法基于图分块的思想,具有现有的全符号网络函数树值法的主要优点,完全不存在冗余项问题,正、负符号的判断也较为简洁,另外也为较大型网络的分析提供了依据.

关于完全树权的符号判断

引入了完全树的伴随(a+1)一树和伴随主子图的概念,提出了确定完全树权符号的新算法.这种符号计算方法比Mayeda的完全树法简单得多.

时态图最短路径查询方法

最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径查询在城市交通路径规划、社交网络分析、通信网络挖掘等领域有着广泛的应用.由于最短时态路径的子路径不能保证是最优子结构,传统的普通图最短路径计算方法不再适用于时态图.因此提出了基于压缩转化图树(CTG-tree)索引的查询方法,该方法包含预处理和在线查询2个阶段.预处理阶段将时态图转化为普通图,提出了一种无损压缩方法将转化图压缩以减小图规模,采用层次划分技术将压缩有向图分解为若干个子图,并基于子图建立CTG-tree索引.CTG-tree中的节点保存相应子图内部分顶点之间的最短路径、孩子节点对应子图的边界点之间的最短路径、孩子节点对应子图的边界点与当前节点相应子图的边界点之间的最短路径信息.在线查询阶段基于构建的CTG-tree索引,提出了一种高效的最短路径查询方法.基于4个真实的时态图数据集实验结果表明,与现有方法相比,提出的方法具有更优的查询性能.

极大欧拉生成子图边数的几个定理

利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 .

基于可拓层次分析法求解最佳生成树

针对最小生树不唯一,如何选择最优的最小生成树的问题,提出了将破圈法和可拓层次分析法相结合的方法。首先,用破圈法求出一个最小生成树;其次,对连通图进行约化,得出约化图,标记固定边,求出换入边,用破圈法的思想求出全部的最小生成树;因最小生成树的结构不相同,节点之间的连接方式也不相同,最小生成树的选取就有了区别,最后,采用可拓层次分析法对全部最小生成树进行评价,从最小生成树的节点度为1的节点比例、聚类系数、平均路径长度、网络效率构造可拓判断矩阵,计算权重向量,进行层次单排序和层次总排序。以一个连通图为例,说明了该方法的步骤和可行性,得到了得分最高的最小生成树即为最佳生成树。

用概率树图法求解事件发生的概率

求事件发生的概率时,首先按事件先后发生的顺序画出概率树图,在概率树图上注明各个事件发生的概率,然后沿事件的终点重返始点,再利用概率的乘法公式和概率的可加性,即可求得事件发生的概率.

随机市场模型下支付固定比例红利和考虑交易费用的美式看涨期权定价

文章研究随机市场模型下考虑交易费用和支付固定比例红利的美式看涨期权定价,详细讨论了支付固定比例红利时刻美式看涨期权提前执行满足的不等式条件,并应用二叉树图定价和蒙特卡罗方法数值求解期权价格。

基于图论及网络等值的配电网可靠性评估方法

能源互联网的快速发展对电网形态、结构、功能提出了新的要求。针对配电网目标网架构建,提出基于图论的配电网可靠性评估方法,为配电网的规划和建设提供参考依据。提取配电网拓扑结构采用图的邻接矩阵表示,用加权邻接矩阵的边权代表配电网馈线上元件的可靠性参数,采用搜索树的方法找出复杂结构配电网的最小路,转化为最小割集矩阵得到网络的一二阶割集;运用图论的状态空间法推导出多元件系统可靠性指标等效合并计算公式,对于含分支馈线的复杂结构配电网,采用网络等值法将分支馈线对上级馈线的影响用等效元件的可靠性指标反映,通过网络等值有效降低配电网网架的空间复杂度,简化计算过程,具有良好的实际应用价值。最后在RBTS母线6系统的主馈线上验证了将图论和网络等值运用在配电网可靠性评估中的有效性。

基于UPGMA的恶意代码系统发生树构建方法

借鉴生物信息学中的物种系统发生树构建方法,提出了基于恶意代码函数调用图和非加权组平均法(UPGMA)的恶意代码系统发生树构建方法,并利用恶意代码函数调用图的相似性距离数据对本方法进行了实验。此方法能够为恶意代码的同源及演化特性分析研究与恶意代码的检测和防范提供有力的支撑和参考。

融合时空多特征表示的无监督视频分割算法

针对视频分割的难点在于分割目标的无规则运动、快速变换的背景、目标外观的任意变化与形变等,提出了一种基于时空多特征表示的无监督视频分割算法,通过融合像素级、超像素级以及显著性三类特征设计由细粒度到粗粒度的稳健特征表示。首先,采用超像素分割对视频序列进行处理以提高运算效率,并设计图割算法进行快速求解;其次,利用光流法对相邻帧信息进行匹配,并通过K-D树算法实现最近邻搜索以引入各超像素的非局部时空颜色特征,从而增强分割的鲁棒性;然后,对采用超像素计算得到的分割结果,设计混合高斯模型进行完善;最后,引入图像的显著性特征,协同超像素分割与混合高斯模型的分割结果,设计投票获得更加准确的视频分割结果。实验结果表明,所提算法是一种稳健且有效的分割算法,其结果优于当前大部分无监督视频分割算法及部分半监督视频分割算法。

用图论法确定工艺尺寸链

本文介绍了应用图论的基本知识如何确定工艺过程中的尺寸链,并通过实例总结了确定工艺尺寸链的具体方法、步骤和注意事项。为确定复杂工艺尺寸链提供了一种新的方法。

用图论理论正确掌握破圈法

用图论中有向树和赋权图的理论指出了一些书中所讲"破圈法"的错误,同时也点出了求网络图中关键路线的两种新方法.详细说明了如何正确使用破圈法.