关于索引图的一些结论

文献［１］给出了索引图的概念：设Ｇ＝（Ｖ,Ｅ）为简单图,如果存在标号ｆ,将图Ｇ的顶点分别标以０,１,… ,连续的整数,使得图Ｇ边的相邻两点标号之和是彼此不同的,则称ｆ为Ｇ的索引标号。若图Ｇ有索引标号,则称Ｇ为索引图。本文讨论了索引图的一些性质,证明了如果Ｅ２Ｖ－３,则Ｇ不是索引图;证明了Ｋｍｎ为索引图．当且仅当Ｋｍｎ为星或为Ｋ２ｎ;证明了任意个索引图非连通的并图是索引图。     

3-cactus上的连通p-median问题

设G=(V,E)是一个无向连通图,每一条边e和每个顶点v都有一个非负的权重l(e)和w(v);传统的p-median是指在顶点集合中选出p个顶点,使得其它顶点到这p个顶点的赋权距离和最小。该文考虑带有某些约束的这类问题,要求所选出的p个顶点是连通的,也即由这p个顶点所导出的子图是连通的,称为连通p-median问题。该文给出了3-cactus图上的连通p-median问题的一个O(pn)的算法。     

树的顶点扩张图的最小直径定向

文献[1]将3阶以上的连通无向图的顶点扩张图按照其最小定向直径分为三类,并给出了如下猜想:直径至少为3的连通无向图的顶点扩张图不属于第三类图.本文运用顶点标号法,证明了猜想对树是成立的,即树的顶点扩张图的最小定向直径与原树相比最多增加1.     

k—覆盖图的一个充分条件

论证了整数ｎ（ｎ≥３）和ｋ（ｋ≥２），若ｋ为奇数，则令ｋ≥ｎ－１，Ｇ是一个不含Ｋ１，ｎ的２－边连通图，ｋ│Ｖ（Ｇ）│≡ｏ（ｍｏｄ２），设Ｇ的顶点最小度α（Ｇ）至少为（ｎ＾２／４（ｎ－１）ｋ＋（３ｎ－６）／２＋（ｎ－１）／４ｋ，则Ｇ是ｋ－覆盖图，并且说明了定理条件“２－边连通”不能减弱为“连通”。     

k色图的连通性

研究和讨论了图的顶点着色问题中k色图的连通性,利用归纳与迭代的方法证明了对于任何k色连通图G,存在顶点V(G)的一个着色X1,X2,…,Xk,使得对该着色类中任意顶点集Xi所诱导出的Gk的子图Gk(Xi)都是连通的.从而证明了Chen,Schelp和Shreve关于k色图的连通性的一个推测.最后将所得的结论作了进一步推广.     

几类非色唯一的连通顶点可迁图

给出了几类非色唯一的连通顶点可迁图，即kKq⊙kKq（k≥2,q≥2）、kCn⊙kCn（k≥2，n≥3）和kRn⊙kRn（k≥2，n∈{3，4，6，12}），其中畅是具有q个顶点的完全图，Cn是具有n个顶点的回路，Rn是具有n个顶点的最大正则平面图，⊙是两个不相交图的Zykov乘积运算。     

一类单圈图的度基尔霍夫指数

设G是简单连通图,顶点集为V（G）.图G的度基尔霍夫指数定义为图G中所有顶点对的度与顶点之间的电阻距离乘积的和.棒棒糖图Ln,k是路Pn-k的一个端点连接到圈Ck的一个顶点得到的一类特殊的单圈图.给出首先给出Ln,k的度基尔霍夫指数计算公式,然后刻画了相应的极图.     

通信系统抗破坏能力研究

用顶点和边都加权的赋权图来表示通信网络，其中顶点表示网络反通信站，边表示网络的通信线路，顶点或边上的权指的是破坏其所对应的通信站或通信线路需要付出的代价，提出了赋权连通度，赋权边连通度和赋权混合连通度的概念，这些参数是图的连通度，边连通度和边嗵 度对的概念的推广，它们比连通度和边连通度等图的参数能更精确地反映通信系统的抗破坏能力，利用求网络最大流和最小割的Ford-Fulkerson标号法，给出了求赋权连通度，赋权边连通度和赋权混合连通度的有效算法。     

几类非色唯一的连通顶点可迁图

给出了几类非色唯一的连通顶点可迁图,即kKq kKq(k≥2,q≥2)、kCn kCn(k≥2,n≥3)和kRn kRn(k≥2,n∈{3,4,6,12}),其中Kq是具有q个顶点的完全图,Cn是具有n个顶点的回路,Rn是具有n个顶点的最大正则平面图,是两个不相交图的Zykov乘积运算。     

邻集交,邻集并与图的哈密尔顿性

本文把不相信两点的领集交与邻集并两个概念揉合在一起，以之刻划了比较广泛的一类哈密尔顿图、可迹图及哈密尔顿连通图，文中证明了：若ｓ，ｔ是两个整常数，ｔ≥２，图Ｇ是阶为Ｐ的２连通图，对任何不相邻的顶点ｘ与ｙ，若它们邻集交以ｓ为下界，邻集并以（ｓｐ－ｓ）／（ｔ＋１）为下界，则Ｇ是哈密尔顿图，当把连通度和领集并的下界稍微减少或增大时，图Ｇ减弱为可迹图或加强为哈密尔顿连通图。     

4度循环图的宽直径

研究了涉及图中两点间k条内部不交路的图的宽距离和宽直径。根据循环图的传递性和对称性,得到了n阶4度连通循环图的宽直径的上下限。所得结果可用来度量以循环图作为模型的一类具有高度对称性的网络的通信传输的延迟性能和容错性能。     

设备故障基于图论的层次诊断模型研究

提出了一种基于图论方法的设备故障诊断模型，可以克服通常产生式系统知识获取的困难以及一般基于模型系统过分依赖于定性描述的不足。文中详细讨论了基于图论的设备建模方法和层次分解技术，借助于矩阵分析技术，提出了具体的诊断算法．     

继电接触器控制系统的链式图分析法

介绍继电接触器控制系统功能分析链式图法及故障分析图法     

图的(g,f)—因子分解

设Ｇ是一个图，ｇ和ｆ是定义在图Ｇ的顶点集上的两个整数值函数，且ｇ≤ｆ．图Ｇ的一个（ｇ，ｆ）—因子是Ｇ的一个支撑子图Ｈ，使对任意ｘ∈Ｖ（Ｈ）有ｇ（ｘ）≤ｄＨ（ｘ）≤ｆ（ｘ）．若图Ｇ的边集能划分为若干个边不相交的（ｇ，ｆ）—因子，则称Ｇ是（ｇ，ｆ）—可因子化的．给出了一个图是（ｇ，ｆ）—可因子化的一个充分条件，改进了有关结果．     

并发性诊断问题求解的图论方法

研究设备故障的图论方法。地部件抽象化为节点，部件间的故障传播关系抽象化为连接两节点的边，从而引入图论的方法来解决设备的故障诊断总是讨论了完全信息情况下的并发性诊断问题的求解方法－通路极值化方法。     

基于因果拓扑图的工业过程故障诊断

基于因果拓扑图的工业过程故障诊断方法,将过程知识与数据驱动故障诊断方法结合,有效解决了故障定位和故障传播路径辨识问题。 在因果拓扑图的基础上,基于偏相关系数提出一种相关性指标(correlation index, CI)定量衡量因果拓扑中变量间的相关性,实现变量间因果性和相关性的良好结合。为得到准确的故障检测结果,采用概率主元分析(PPCA)对CI指标进行监测。在检测出故障后,应用重构贡献图(reconstruction-based contribution, RBC)和因果拓扑图,并引入加权平均值的概念辨识出最可能的故障传播路径。将提出的方法用于带钢热连轧过程,结果表明,基于因果拓扑图的故障诊断方法能够准确地定位故障源,辨识故障传播路径。     

某型号航天产品漏电故障诊断方法

针对某型号航天产品发射系统漏电故障诊断的特殊性,利用专家知识建立案例知识库,应用图论知识建立某型号航天产品漏电故障诊断图论模型,在此基础上生成树,并根据信息熵理论,提出"二分法"诊断思想,进行故障部件的定位,最后把成功诊断实例添加到案例知识库中;同时设计案例推理模块,通过人机交互模块达到案例推理和图论模型诊断方法的融合,使故障的定位更快速、精确.     

计算机K维栅格图象距离图的研究

本文着重讨论了多维栅格图象距离图的定义和计算．提出了Ｋ维栅格空间和Ｋ维栅格图象以及有关Ｋ维栅格图象的一组概念，如毗邻类型、Ｎ－序列等．然后．用路径长度定义了一个函数Ｄｑ，再用Ｄｑ定义了Ｋ维栅格图象的距离概念和相应的距离图概念，并给出一个有关距离的一个定理．对于距离图的计算，文章中给出了一个ＧＤＴ变换，即广义距离变换和相应的一个定理，该定理表明了经过ＧＤＴ变换所得的结果就是由Ｎ－序列ｑ所决定的距离图．     

冠状系统R-旋转图的连通性

1981年Ohkami等提出了R-旋转变换的概念，并由此变换建立了cata型六角系统的完美匹配集上的一种层次组织结构，它可用一个有向根树来表示。称它为该六角系统的R-旋转图。1985年陈桎柏证明了一般有完美匹配的六角系统的R-旋转图也为一棵有向根树，同时也证明了冠状系统的R-旋转图为有向森林，在对以上知识研究的基础上证明了正常冠状系统的R-旋转图至少包含两棵有向根树。     

基于表象式语义网络的图匹配算法

提出了一种在表象式语义网络中的查找方法,表象式语义网络问题的求解一般都是通过图匹配实现的,首先根据待求解的问题的要求构造一个带变量节点的语义网络,然后与计算机视觉系统中己存储的语义网络进行图匹配。当语义网络中的询问部分与系统中的语义网络图匹配后,则与询问部分匹配的事实就是问题的解。图匹配问题可以通过构造一个图的附属数据结构来完成,这个附属数据结构也称为相连图(association graph),对于两个图G=(V,A)以及G′=(V′,A′),构造相联图G″=(V″,A″),也就是说,V″是所有可能节点匹配对的集合,A″是所有相容节点匹配的集合。这相当于在相联图中寻求一个最大的基团(clique),其中基团定义为G″的完全连通的一个子图。最大基团满足其节点集合不是任何其他基团节点集的适当子集。