基于图论的雷达优化部署方法

通过离散化等处理将雷达组网部署问题转化为图论问题,利用图论相关知识研究这一多目标优化问题,根据约束条件的不同建立了对应的模型,并通过状态压缩等技巧设计了对应算法.相比于传统的相关算法,该算法复杂度低,并且适用于复杂区域和复杂约束的部署问题,对于不同约束均能快速给出最优部署方案.本文还讨论了重点区域覆盖和冗余覆盖等因素,最后给出模拟仿真.仿真结果表明,本算法给出的部署方案一方面保证了对整个区域全覆盖,另一方面让冗余度尽可能小,避免了资源浪费.      

最小顶点覆盖问题的一个近似算法

最小顶点覆盖是图论中的一个重要概念，它是一个NP难的问题．给出了一个求解最小顶点覆盖的近似算法，与现有算法相比具有更优的性能比。     

求欧拉图所有初级圈覆盖的一个算法

本文利用深探法设计了一个求欧拉图一切无公共边的初级图覆盖(简称覆盖)的算法它由两个子算法组成:算法(Ⅰ):求欧拉图中过一边 e 的所有初级级图.算法 (Ⅱ):求欧拉图的一切无公共边的初级图覆盖.文中定理和算法对有向欧拉图也完全适用。     

完全图的Hamilton圈分解

在文[3]中,Hoffman等证明了完全图Kn中最多边不交的Hamilton圈个数为「n-1/2」.然而根据文[3]中的证明方法,要具体表示出这「n-1/2」个边不相交Hamilton圈是非常困难的.文章给出了完全图的Harailton圈分解的一种简便方法.     

基于图的覆盖决策信息系统属性约简新算法

属性约简是粗糙集理论的重要研究内容之一,主要是用于去除高维数据的冗余信息.利用图论求约简是覆盖决策信息系统属性约简的一个新方法,其将覆盖决策系统的约简等价于超图的极小顶点覆盖.本研究提出一种新的覆盖决策信息系统的属性约简算法,该算法采用三步策略:首先确定覆盖决策信息系统的辨识集,然后得到超图的关联矩阵,最后用贪心法求出...     

一种基于最短长度m2圈算法的故障监测方案

针对光突发交换网络中“逐跳检验”监测模式成本较高等问题,提出了一种新的基于最短长度m2圈算法的光突发交换网络故障监测机制.该机制根据最短长度m2圈算法寻找光突发交换网络中的圈覆盖放置故障探测模块,从而形成基于圈覆盖的光突发交换网络故障监测模式.同时,在最短长度m2圈算法的基础上提出一种相应的故障定位算法,利用异或关系衡量告警编码与链路相关编码是否吻合,从而进行快速故障定位.计算结果表明,基于最短长度m2圈算法的故障监测机制具备网络开销小、故障定位率高和故障定位快速等特点.     

简单图中哈密尔顿圈的个数

给出了计算简单图中哈密尔顿圈个数的几个公式,并对简单图中哈密尔顿圈个数的上下界进行了讨论。     

求极大元的一个图论算法

给出了一个求优超关系下极大元的多项式算法，该算法能产生可图序列，直接在图上实现。文中给出算法实例。     

一种基于图论的LDPC码构造算法的研究

在对低密度奇偶校验(LDPC)码进行分析的基础上,提出了一种基于图论的构造算法.该算法从对LDPC码的校验矩阵进行图论分析入手,分析了组成校验矩阵中的圈的校验点之间的关系,得出了由这些校验点对应的结构图是彼此同构的欧拉图的定理,利用这个定理以及根据定理得到的性质,可以通过构造一个辅助的校验点结构图的邻接矩阵,渐进地生成LDPC码的校验矩阵,在生成的过程中避免短长度圈的出现.仿真实验表明提出的算法对中短码长的LDPC码构造具有良好的性能.     

几类乘积图的圈覆盖

文献［１］提出猜想：每个２─连通ｎ阶简单图都有一个圈覆盖Ｃ，使得｜ｃ｜≤（２ｎ－１）／３。此猜想至今尚未完全证实。本文对路、圈、完全图的若干笛卡尔乘积图和张量乘积图证实了猜想是正确的。     

基于Meanshift和图割的极化特征图像分类

图割法对极化SAR图像能达到很好的分类效果,但由于极化SAR数据比较庞大,直接用图割法进行分类,计算量太大,所以本文提出一种改进图割模型的分类方法．首先利用自适应的Meanshift算法结合多个极化特征把图像分成若干个同质区域,以这些同质区域的加权平均值作为超像素构建图模型,最后用图割法修正Meanshift过分割来得到最终的分类．实验证明该算法不仅在分类精度上有所提高,而且在速度上更能达到实时性的要求．     

矩阵环的欧拉恒等式与标准多项式恒等式

Szigeti-Tuza和Revesz使用Swan图论定理构造了n×n矩阵环Mn（C）的欧拉恒等式[1].本文中证明这些恒等式可由标准多项式生成,即：若欧拉图Γp,q从某顶点t到u（t,u可为同一点）至少有n条边,则该欧拉图对应的欧拉多项式fΓp,q（X）可由标准多项式Sn（X）生成.该结果不仅推广了Chang[2]和Giambruno-Sehal[3]的结果,而且找到由欧拉恒等式生成的T-理想的一个有限生成集.     

混合Euler图的特征性质

本文对任意混合图M建立相伴运输网络N_M的概念,并以此给出M是混合Euler图的充要条件。这结果与文献中同类结果相比,具有更大的实用性。     

L(G)图的若干性质

从线图L(G)的定义出发,全面研究了L(G)图的性质 重点对L(G)图的连通性,E(L(G) )的计算,L(G)与G的同构,L(G)的点连通度,L(G)何时构成欧拉图、可折叠图等问题进行了研究,并给出了证明 .     

混合Euler图的特征性质

本文对任意混合图 M 建立相伴运输网络 N_M 的概念,并以此给出 M 是混合 Euler 图的充要条件。这结果与文献中同类结果相比,具有更大的实用性。     

求最大权伪对集的一个算法

图的可以含有环的对集称为图的伪对集。William 和 Anderson 给出了求图的最大基数伪对集的一个算法。本文给出了求图的最大权伪对集的一个算法,它是 Edmonds 算法的一个推广。     

基于边被收缩图的有向有环图有向割集求解算法

为了提高有向有环图有向割集生成算法的效率,通过收缩有向有环图环路中的边将有向有环图转换成带收缩顶点的有向无环图,并使得生成有向无环图有向割集的算法可以生成有向有环图的有向割集.在理论上分析了本文提出的算法的时间复杂度和空间复杂度,并进行了实验测试.理论分析和实验测试的结果表明本文提出的算法是很高效的.     

基于核的有向强连通图计算机随机生成算法

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。     

图挖掘在DNA混合样本拆分中的应用

以图论为基础提出了基于图结构的DNA混合样本拆分算法——MDG算法,对混合STR图谱中每个基因座构造不同的等位基因图,形成等位基因图集,把DNA混合样本的拆分转化为在图集中的挖掘问题。MDG算法的提出进一步扩大了图论的应用范围,也为混合样本拆分提供了新的解决思路。     

面向高分辨率卫星图像的几种图像分割算法稳定性对比分析

将基于均值漂移和图模型的图像分割算法及这两种算法的混合算法应用到高分辨率卫星光学图像,并对比了它们在分割遥感图像时的稳定性。均值漂移算法是一种基于核密度梯度估计的特征空间分析算法,其实质是一种统计优化过程。基于图模型的算法将一幅图像抽象为一个无向图,通过不断合并图结点,将这个图分割为多个连通分量,进而实现一幅图像分割。混合算法首先利用均值漂移技术对图像进行滤波,然后再使用图分割算法对图像进行分割。实验结果显示,均值漂移算法分割结果对其参数变化较为敏感,而基于图模型的算法和混合算法则较为稳定。