两个单形的k级混合顶点角

本文证明了关于两个单形的k级混合顶点角与每个单形的k级顶点角之间的一些新的重要的几何不等式。

几类笛卡尔乘积图的k路顶点覆盖数问题

对于任意图G和正整数k,如果图G中所有长度为k的路都至少含有其顶点子集S中的点,那么我们称顶点子集S为k路顶点覆盖集。我们定义最小的集合S的基数为φk(G),并且称它为图G的k路顶点覆盖数.本文我们主要研究了笛卡尔乘积图的k路顶点覆盖数问题,并给出了φk(Cm□PN2)的估计值。

基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法

强连通分量挖掘是图论中的经典问题之一,如何设计更高效率的串行强连通分量挖掘算法具有现实需求。GRSCC算法利用k步上近似和k步R相关集这两个粗糙集算子所构成的SUB-RSCC函数,可实现简单有向图中的强连通分量挖掘,而SUB-RSCC函数的调用次数决定了挖掘效率。根据挖掘强连通分量时顶点间存在的相关性,GRSCC算法引入了粒化策略,减少了SUB-RSCC函数的调用次数,提高了挖掘效率。在GRSCC算法的基础上,分析发现了顶点间的另外两种强连通分量相关性,由此设计了一种新的顶点粒化策略,进而提出了一种顶点粒k步搜索方法,可更大程度地减少SUB-RSCC函数的调用次数。最后,提出了一种基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法KGRSCC。实验结果表明,相比RSCC算法、GRSCC算法和Tarjan算法,KGRSCC算法具有更好的性能。

顶点着色的若干结果

色数理论研究是图论研究的一个重要方面.在引入了最优顶点着色概念的基础上,获得了图的色数的系列上界,刻画了图的色数与图的特征根之间的关系,即用图的特征根来估计图的色数的上下界.

关于n维单形k维顶角的正弦定理

利用度量几何的理论和方法研究了n维单形的正弦定理,提出了n维欧氏空间En中n维单形k维顶角的概念,建立了n维单形k维顶角的正弦定理,该定理不同于已有的单形正弦定理,与三角形正弦定理在内容和形式上是完全统一的.n维单形k维顶角的正弦定理应用很广泛,也很方便,应用它获得单形k维顶角的一类几何不等式,作为其特例得到了已有的一些结果.

基于遗传算法的区段站到发线运用优化安排

从模拟铁路区段站调度员思维角度出发,分析区段站车列占用到发线时区集合的特点,应用划分时间片算法建立合适的到发线安排的图论模型,将到发线安排问题转化为顶点具有加权的图的k 着色问题。依据设计混合遗传算法基本原则,将基于顺序的贪婪着色算法和遗传算法混合起来运用于该问题,设计有序的字符串编码方法,构造基于罚函数的适应度函数,采用交叉和变异等技术,给出混合遗传算法的基本求解步骤。

基于模拟退火算法和图着色的调车机车安排研究

铁路车站作业计划编制过程中,如何编制调机运用计划是调度指挥的关键问题。通过分析运用调机时区集合特点,构造调机运用安排图论模型,再将调机运用问题转化为图的着色问题。应用模拟退火算法通过解图的k 顶点着色问题来安排调车机计划,最后给出算法实例。