有向图的同构

证明“图Ｇ与图Ｆ同构当且仅当它们有机合的ＶＣ算法”的结论,对于简单有向图依然成立。     

简单无向图的同构判定问题的研究

图的同构判定问题是图论学科的基本问题之一,但是要判定两个图是否同构却是一件非常不简单的事情。本文旨在研究简单无向图的同构判定问题;并提出了一种新的简单无向图同构的必要条件。     

一种对称无向图的同构判定算法

文章在电路模拟法的基础上提出了一种对称无向图的同构判定算法.电路模拟法对随机图的同构判定问题非常有效,但是对于处理对称度较高的图,判定效率明显降低甚至失效.该文提出的算法针对对称无向图的特性,在电路模拟法的基础上结合Dijkstra算法,综合得到顶点属性和最短距离序列来搜索顶点之间的映射关系,能够有效判定这类图的同构问...     

无向图的一个距离不等式

对任一无向图Ｇ（Ｘ，Ｅ），顶点集Ｘ＝｛ｘ１，ｘ２，…，ｘｎ｝，任给三点ｘｉ，ｘｊ，ｘｋ，若两两之间存在距离，则成立不等式：ｄ（ｘｉ，ｘｊ）Ｇ＋ｄ（ｘｉ，ｘｋ）Ｇ＋ｄ（ｘｊ，ｘｋ）Ｇ≤２ｎ－２。     

图的同构判定算法:关联度序列法及其应用

提出了图的同构判定新算法,即关联度序列法和黄金分割关联度序列法,后者的计算时间复杂性远远低于2N（N为图的顶点数）,已接近于多项式时间复杂性,该算法可应用于很多能用图来描述的式识别等实际问题。     

置换群的一个应用——不同构的简单无向图的数目计算

针对不同构的简单无向图的数目计算问题，本文在研究了置换群以及伯恩斯坦定理的基础上，以4个顶点的无向图为例，给出了具体的计算方法。     

同构问题的关联矩阵亚字典排序判别法

通过研究关联矩阵行列变换对两图同构性的影响情况，定义了关联矩阵的亚字典排序，探讨了关联矩阵亚字典排序的唯一性及两图同构的一个充要条件。最后给出一个通过对关联矩阵的亚字典排序，判定两图是否同构的有效算法。     

基于无向图的专家群体决策会诊调度算法

传统CAD的专家调度算法,大都集中在专家和患者一对一的会诊模式,或不同领域专家和患者多对一的会诊模式方面的研究,很少涉及对相同领域专家与患者多对一的会诊调度研究.针对这一问题,提出了群体决策思想的多专家会诊调度算法(MESDA),调度相同领域内的多位专家,为同一患者展开群体会诊.算法采用贪心策略,一方面考虑并行会诊的数量达到最大,另一方面考虑每一群诊项的专家成员数达到最大,通过滑动参数控制,从局部最优出发,逐步解决并行会诊和专家成员数的优化问题.实验结果表明:算法能够解决现实问题中相同领域专家和患者多对一的群体决策会诊的调度问题.     

关于无向图节点信息量的比较

运用图模型的基本理论,研究了离散型和连续型两种随机变量熵和信息量的相关性质,讨论了这两种情况下条件信息量的性质,再利用无向图的概念,推导了几种简单的无向图节点信息量的一般结论,即相邻节点间的信息量大于不相邻节点的信息量.     

任意无向图的R点连通扩充

为研究以最少边集扩充一个任意无向图为R点连通图这一尚未解决的优化问题，通过将无向图点连通问题转化为有向图边连通问题，采用增广扩充的方法，提出了一个复杂度为O（｜V｜^5）的算法．利用该算法可最优地将给定无向图中任意2点达到所要求的点连通度．它发展了K点连通最优扩充的研究，从而使图的点连通扩充的研究在应用于网络设计的可靠性设计方面更具有实际意义．     

无向图同构的快速算法

规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断；要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使...     

基于改进遗传算法的无向加权图的k点连通扩充

加权图的连通扩充问题已被证明是NP完全问题，作者提出一种改进遗传算法来解决无向加权图的k点连通扩充问题，通过改进遗传算法中的交叉和变异操作有效地改善了群体的效果，有助于搜索解空间中新的区域，能以较大概率搜索到全局最优，仿真结果表明，该算法在原来简单遗传算法上做了进一步改善，为解决加权图的扩充问题提供了新的方法。     

任意图同构判定及其应用

建立了任意图的伴随电路模型,使用电路分析方法求解伴随电路,通过解出的节点电压来确定原图拓扑结构的对应顶点,并由此提出了可应用于任意图的同构判定算法.     

无向简单图P─中心的求法

本文提出一种方法──把减边法与矩阵法结合起来，可较简便地寻求无向简单图Ｐ－中心。     

无向Kautz图的限制性连通度和限制性容错直径

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４。     

一类无向双环网络的最优路由算法

设n=qh r,这里1≤r≤h-1,w=「(h-1)/(q r) .对于一类较为普遍的满足条件h≥wr的无向双环网络G(n,1,h),本文给出了一种时间为常数步的最优路由算法.     

一类变换图的同构问题

利用度序列的概念,证明变换图G~(--+)与H_n~(--+)同构,当且仅当G与_n同构.以及在G连通的条件下,G~(--+)与C_n~(--+)同构,当且仅当G与_n同构.     

非固定步长的无向循环图的支撑树数

图的支撑树数是图的重要的不变量,也是网络可靠性的重要量度.循环图是一个重要的图类,可应用于局域网和分布系统的设计中.对有固定步长的循环图,其支撑树数已得到了研究.本文考虑有非固定步长的无向循环图Cpn(a1,a2-,…,ak,q1n,q2n,…,qmn),这里a1,a2,…,ak,q2,q2,…,qm,n和p都是正整数,a1≤a2≤…≤ak≤n/2,q1≤q2≤…≤qm≤p/2,且n是可变化的,因而有些步长并非固定.给出其支撑树数的一个公式,并得到其渐近性态和常数系数的线性递归关系.