多部图的导出匹配可扩性

k-部图G指图的顶点集V(G)被剖分成k个子集,使每一条边所关联的两个顶点不在同一个子集之中.主要研究了完全多部图的导出匹配可扩性,给出了完全多部图是导出匹配可扩图的充要条件.     

图的顶点赋权邻域粘连度

将邻域抗毁性该参数推广到顶点赋权图中,提出图的顶点赋权邻域粘连度概念。通过构造组合星图,建立数学规划模型,研究了几类图的顶点赋权邻域粘连度的极值问题。     

群体多目标决策的联合有效解类及其最优性条件

群体多目标决策是群体决策的一个新的研究方向．一些学者曾借助群体效用函数引进群体多目标决策问题有关效用解的概念，并且给出若干求解的方法．本文撇开效用函数的介入，直接依据由各多目标决策问题的Ｐａｒｅｔｏ有效解表示的供选方案的有效数，引进了决策群体在供选方案集上的偏爱关系．由此，定义了群体多目标决策问题一类联合有效解的概念．同时，建立了这些联合有效解类要满足的Ｋｕｈｎ－Ｔｕｃｋｅｒ型最优性条件．     

旅行商问题的一种启发式算法

用一个有向图表示旅行商避开某一城市到1个顶点的所有最短路径,并在每条弧上定义一个线性表,用以记录所有包含该弧的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作,进而讨论了图上的弧都在某一最短路径上的充要条件,以及如何顺序产生第1列到第n列的顶点上的图,如何从这些图上搜索出近似最优解的方法.     

点赋权图上固定顶点的树划分问题

考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1k近似算法.     

舱室噪声传递路径分析的SEA赋权图法

针对传统传递路径分析求解中高频问题的不足,采用SEA赋权图法分析舱室噪声的传递路径.以统计能量分析(SEA)为基础,将SEA系统与图论中路径网络进行类比得到SEA赋权图,从功率流平衡方程中提取SEA参数表示赋权图连接边的权重系数.将噪声传递路径问题转化为求解赋权图的最大权重路径问题,传递权重最大的K条路径(KDP)即为能量的主要传递路径.选取某舱室模型为分析对象,从SEA赋权图中得到2000条KDP,并通过识别路径的结点得到能量传递路径中的关键结点.各种噪声控制方案的对比结果验证了SEA赋权图法在减振降噪分析中的有效性,为降噪措施具体实施方案提供了明确的参考.     

不完全信息下基于证据推理的多属性决策方法研究

针对不完全信息下多属性群体决策中存在的问题,提出一种基于证据推理的多属性群体决策方法。该方法首先应用灰色白化权函数将定量属性定性化,然后针对不同专家知识背景的不同,构建基于属性的专家赋权方法,用证据推理方法将不完全信息下的多个专家的意见进行集结,并应用效用理论对方案进行排序择优。最后通过一个算例验证该方法的有效性和可行性。     

加法幂等半环和坡代数在网络路径优化问题中的应用

对加法幂等半环上矩阵幂收敛的条件,以及加法幂等半环和坡代数赋权图路径优化问题与伴随矩阵幂的关系进行了研究,优化问题是在加法诱导的偏序≤下考虑的.特别,证明了对于选择的加法幂等半环E上的n阶赋权图G,如果其伴随矩阵A满足aij=e,且对G的任一基本回路p,权w(p)≤e,e是E的乘法幺元,则An-1的(i,j)分量表示从顶点i到j的所有路径的权在偏序≤下的最大元,且最大元一定在某一基本路径上取得.坡代数赋权图的结果作为特例得到.最后给出了几个应用的实例.说明加法幂等半环赋权图的这类广义路径优化问题仍可用矩阵幂的方法来解.     

赋权无三角形图中过给定顶点的重圈

这篇文事中,在Fujisawa的一篇文章的启发下,给出了以下结果：设G是一个2-连通无三角形（triangle-free）赋权图,d是一个非负实数．并且对G中任意顶点v,有d^w（V）≥d．则对G中任意两个顶点y1和y2,G包含一个权至少为2d的（y1,Y2）-圈．这推广了Bondy和Fan,Grotschel,及Fujisawa的一些图中圈的存在性的结果．     

有向网络最长距离的矩阵算法

对于无多重弧的n阶赋权有向图，引入距离矩阵A，将此矩阵看作取大-加代数 (R∪{-∞}，max，+ )上的矩阵，证明了只要任一回路的权非正，则An-1的分量aij（n-1）”就是顶点i到j的最长距离，且此最长距离必在某条路径上取得。     

K-桥图的本原指标

K-桥图是由连接A，B两点的K条内部不交路所组成的图．计算得到本原K-桥图的本原指标等于m-1或n-1，其中m是最大奇圈的圈长，而n是A，B间最长奇路(偶路)与最短偶路(奇路)的长度之和．     

关于图的广义Mycielski图的邻点可区别关联着色

邻点可区别关联着色是使得相邻顶点的颜色集不同的关联着色。主要研究了路,圈C3m, C4m与完全图的广义Mycielski图的邻点可区别关联色数, 拓展了图着色的领域,便于更好的研究图的结构。     

路径幂图、Flower Snark图及多锥图独立数

图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多锥图的独立数问题,首先构造出了它们的独立集,得到其独立数的下界,然后证明了该值也是其独立数的上界,并给出了它们独立数的准确值.     

路和圈幂图的邻点可区别E-全染色

以一个简单图G为基础,连接G的任意最短路长为k的2个顶点就可得到基础图G的k-幂图,研究了路的k-幂图和圈的2-幂图的邻点可区别E-全染色问题,并结合该类幂图的结构性质,运用构造法、反证法和穷举分类染色技术给出了其邻点可区别E-全色数,为确定图的各类染色问题提供了有效的借鉴.     

几类和扇有关图的优美性

证明下面的结论:对任意自然数n≥2,图(K_1∨(P_n∪P_(n+1)))是(n-1)-强优美图.对任意自然数n≥3,图(K_1∨P_n~((1))∪P_n~((2))))∪G是优美图;对任意自然数n≥4,图(K _1∨(P_n~((1))∪P_n~((2))∪P_n~((3)))∪H是优美图,其中k=[n/2].P_n是n个顶点的路,G_i为含有i条边的优美图.给定优美图G_(n-1)和其优美标号f,G_(k-1)和其优美标号g,设u∈G_(n-1),v∈G_(k-1)且f(u)=g(v)=0,取不同的两边xy和x′y′,点x与u合并后得到的图记为G,点x′与v合并后得到的图记为H.     

控制圆点临界图的若干性质

对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的k-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图.     

具有最小Wiener指数的双圈图

一个图G的Wiener指数W(G)定义为G中所有点对的距离和,双圈图是一个具有n个点和n+1条边的连通图,我们根据两个圈的相对位置关系把双圈图分成三类,分别在这三类中给出了最小的Wiener指数,然后通过比较三类极值的大小得到了双圈图中具有最小Wiener指数的图。     

Immune Algorithm for Selecting Optimum Services in Web Services Composition

0 IntroductionInha rveec eenmte yregaerds a,sa t ghreo Iwnitnegrn neut mdbeverel oofps W aetb a S fearsvtic reast e( .W TSshe)Webis nowevolving into a distributed device of computationfroma collection of information resources[1]. But individualWeb services usually cannot satisfy some customers’require-ments ,so we always needtointegrate existingservices to cre-ate newvalue-added composed services .The process model underlying a composite identifies thefunctionalities required by the servic…     

S(7，n)的k-边优美的图标号Z

设图G＝(V,E),其中|V|＝p,|E|＝q.对于k∈N,如果存在一个双射f：E→{k,k＋1,…,k＋q－1},使得它的导出映射f＋：V→Zp,uMT ExtraaAp(u,v) mod p也是一个双射,则称图G是k-边优美的.对于所有的满足G为k-边优美图的非负整数k构成的集合称为图G的边优美指标集.本文根据轮图的特殊性质,讨论了S(7,n)为k-边优美图的必要条件.根据所得的必要条件,利用递归的方法构造S(7,n)的k-边优美图标号并给出详细证明,从而完全解决了当n为偶数时S(7,n)的边优美指标集问题.     

麦比乌斯梯子及其他图类的二维带宽(英文)

设G 是一个简单图。二维带宽问题是 :确定图G在平面格子上的一个嵌入 ,使得最长边尽可能短。本文给出了一些特殊图类的二维带宽