n-正则(n-2)-边可删的导出匹配可扩图

设图G是有2n个顶点的简单图,如果对于E(G)的任一满足|F|=k的子集F,G-F均为导出匹配可扩的,则称图G是k-边可删的导出匹配可扩图.证明了n-正则(n-2)-边可删的导出匹配可扩图只有Kn,n,其中n≠4k,k≥3.     

一类1-边可删的导出匹配可扩图的刻画

设图G是有2n个顶点的简单图,如果删去G的任意k条边后得到的图是导出匹配可扩的,则称G是k-边可删的导出匹配可扩图.给出了4-正则、不包含K1,4作为导出子图、1-边可删的导出匹配可扩图的完全刻画.     

拟轮图的导出匹配可扩性

从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.     

导出匹配可扩图的度和条件

称一个简单图Ｇ是导出匹配可扩的,缩写为ＩＭ－可扩的,如果Ｇ的每一个导出匹配都包含在一个完善匹配中,研究导出匹配可扩图的度和条件,主要结果如下：（１）若图Ｇ有２ｎ个顶点,且对于Ｇ中每一对不相邻的顶点ｕ和ｖ,ｄ（ｕ）＋ｄ（ｖ）≥２「４ｎ／３」－１,则Ｇ是出匹配可扩的;（２）若Ｇ是一有个有２ｎ个顶点的无爪图,且对于Ｇ中每一对不相邻的顶点ｕ和ｖ,ｄ（ｕ）＋ｄ（ｖ）≥２ｎ＋３,则Ｇ是导出匹配可扩的。同时,说     

循环图中部分图类的导出匹配可扩性

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G,)则称其为步长为1和k的循环图,记为C2n(1,k.)通过详细讨论循环图的导出匹配可扩性,具体给出了循环图中的部分图类的导出匹配可扩性。     

结合图的导出匹配可扩性

简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.     

导出匹配可扩图的度和条件(英文)

称一个简单图G是导出匹配可扩的,缩写为IM-可扩的,如果G的每一个导出匹配都包含在一个完美匹配中.研究导出匹配可扩图的度和条件,主要结果如下     

直径为2的无爪图的导出匹配可扩性

如果简单图G的每一个导出匹配都包含在它的一个完美匹配中，称图G是导出匹配可扩的，简称为IM-可扩的。研究了直径为2的无爪图的导出匹配性，证明了一个直径为2的无爪图G是IM-可扩的充分必要条件是：对任意满足|M|≤3的导出匹配M，G—V(M)没有奇分支。因而，直径为2的无爪图的IM-可扩性问题是多项式可解的。     

一个匹配是导出匹配的条件

称图G的一个匹配M是导出的，如果M是由M所覆盖的顶点导出的子图的边集，分别给出二部图的一个匹配是导匹配的条件及存在一个最大匹配是导出匹配的条件。     

步长为1和n/2循环图的导出匹配可扩性研究

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±n2(mod2n)的i和j,均有xixj∈E(G),则称其为步长为1和n2的循环图,记为C2n(1,2n).本文的主要结论为:C2n(1,2n),n#4,是导出匹配可扩的.     

Motif Finding问题的分布式参数算法

基于从DNA序列形成k分图的图理论算法和查找k-clique的理论算法,设计与实现了对Motif Finding问题求解的分布式参数算法。该算法的主要特点是:采用新的1-3树分枝算法并实现分布式计算机制,即任务可以随着计算过程的展开在每一阶段不断地分解并分布到不确定数量的申请参与计算的客户机上,服务器端负责任务均衡与结果整合。实验结果表明:分布式参数算法充分利用多台机器协同计算,能够正确、高效地得到计算结果,为求解生物计算中难解的Motif Finding问题提供了有效的解决手段。     

关于匹配数为1的极大2-均衡3-部3-图的结构

描述具有给定匹配数的极大k-一致超图的结构是一个尚未解决的问题.本研究充分利用完全2-均衡3-部3-图中所有互不相交的完美匹配,得到极图的边数,进而确定所有极图的结构.     

状态离散的确定性多阶段群体满意决策最优的算法

为了解决状态离散的确定性多阶段群体决策问题,将群体满意决策问题的多阶段与图的点集、边集对应起来,应用图论知识建立了多阶段群体决策问题的模型．将多阶段群体满意决策问题转换成一个在多部赋权图中找一条最长路径的问题．依据一条最长路径上的任意两个不相邻的顶点之间是不可以被由不在这一条路径上的两个顶点组成的更长的路所替代这一事实,提出了一种多部赋权图中最长路径的算法．最后给出计算实例．     

基于最优ROC曲线的k-部排序本体算法分析

本体相似度计算和本体映射被广泛应用于查询扩展和图像检索中,已成为信息科学研究的热点内容,其核心为计算本体图中顶点间的相似度.本文从理论的角度分析最优ROC曲线标准下k-部排序本体算法的性质,给出算法模型的单调性、广义误差、可微性等若干统计特征.     

基于k-部排序学习方法的本体映射算法

本体映射作为实现多本体间相互操作的重要手段,已广泛应用于诸多领域。利于k-部排序学习算法得到最优排序函数,从而将多本体结构图中每个顶点映射成一个实数,通过比较来自不同本体顶点对应实数间的差值判断概念间的相似程度。实验表明：该方法对于在不同本体间建立映射是有效的。     

扩展AUC模型下最优k-部排序函数的计算

本体作为一种结构化数据存储和表示模型已成为信息科学的核心研究内容之一.在扩展AUC模型的k-部排序本体算法的框架上,提出一种计算最优k-部排序函数的迭代算法.最后,将算法分别作用于GO本体和大学本体.实验表明：新算法对特定的应用领域具有较高的效率.     

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S⊆V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψ_k(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψ_k(G)相关的精确值和上下界。     

张量积图的边联结数

本文研究了张量积图的边职结数，由于确定任意图的束积的边职结数很难，故限于讨论下列类型图的张量积：路（Ｌｎ），图（Ｃｎ）。完全图（Ｋｎ）和完全偶困（Ｋ＿（ｍ．ｎ）），已求得路与圈、圈与圈、路与完全图、圈与完全图、路与完全偶图、圈与完全偶图、完全图与完全图、完全图与完全偶图、完全偶图与完全偶图的张亡积图的边联结数。     

强笛积图的边联结数

本文研究了强笛卡尔积图的边联结数，求得了路与路、路与圈、圈与圈、路与完备图、圈与完备图、路与完备偶图、圈与完备偶图、完备图与完备图、完备图与完备偶图、完备偶图与完备偶图的强笛卡尔积的边联结数。