交通网络k-短路径与最小支撑树问题

为了给交通管理部门提供多个路径诱导信息,基于经典的最短路径算法——Dijkstra算法,研究了赋权交通网络的k-短路径问题。k-短路径问题是在网络G中求出给定起讫点对之间的k条路径P1,P2,…,Pk,满足W(P1)≤W(P2)≤…≤W(Pk),其中W(*)表示路径*的权值。在网络G的基础上,通过对G的点、边重新划分以及对边上的权值重新赋值,构造出了1个新的网络G′并讨论了它的几个性质。从而将G的k-短路径问题转换为求解G′的最小支撑树问题,进一步,最小支撑树问题又等价于求G′中一条边的权值。研究结果表明:由于最小支撑树问题具有多项式算法,得到关于k-短路径问题的多项式算法,其时间复杂性为O(k(m+nlg(n))),m和n为G的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。     

基于蚁群算法的多属性路径选择模型

针对交通网络中多属性条件下的路径选择问题,本文基于蚁群算法讨论了给定起讫点对之间综合最优路径的实现步骤.首先将蚁群按照所给的属性集合分为若干个子蚁群,每个子蚁群给定不同的属性目标.然后在每一次循环的过程中,子蚁群按照既定的属性进行路径选择,在所有的子蚁群完成一次循环后,全局更新信息素.可知,各个子蚁群既按照自己的目标搜索最优解,同时各个子蚁群之间又互相影响,使得所得的结果不仅对于每个属性目标较优,而且综合效果也很好.最后进行了仿真实验并分析了结果.     

二部图的因子覆盖与因子消去

一个图G称为(g,f)-因子覆盖的,如果G的任何边都属于G的某个(g,f)-因子.G称为(g,f)-因子消去的,若对图G的任何边e,G-e含有(g,f)-因子.特别地,对任何x∈V(G),有f(x)≡g(x)时,G相应地称为f-因子覆盖图和f-因子消去图.通过利用二部图(g,f)-因子和f-因子的存在性定理,作者分别讨论了二部图是(g,f)-因子覆盖、(g,f)-因子消去、f-因子覆盖和f-因子消去的充分必要条件.     

二部图的f-2-覆盖与f-2-消去

利用二部图f-因子的存在性定理,给出了二部图是f-2-消去和f-2-覆盖的充分必要条件.     

广义区间值Pythagorean三角模糊集成算子及其决策应用

针对连续集合上决策变量的隶属度和非隶属度之和超过1的决策问题,提出区间值Pythagorean三角模糊数,并且分析其广义集成算子的决策应用。首先,引入区间值Pythagorean三角模糊数的概念,得到其运算法则。其次,推导区间值Pythagorean三角模糊数的加权平均算子、加权几何算子、有序加权平均算子、有序加权几何算子、广义有序加权平均算子以及广义有序加权几何算子,介绍它们的相关性质。最后,构建出基于广义区间值Pythagorean三角模糊集成算子的多属性决策模型,并且根据实例对广义有序加权平均算子和广义有序加权几何算子进行稳定性分析,运用图像直观地证明在处理决策问题时前者优于后者,说明决策模型的有效性和可行性。     

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

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