单平面有向无圈图中最小路覆盖问题的算法研究

一个铁路区段在规划时间内的时空网络是一个仅包含一对源与汇的有向无圈平面图。每个列车都可由该网络中的一条有向路表示。本文研究上述网络中的最小路覆盖问题,即至少用多少条有向路可以覆盖图中所有的边。根据单平面有向无圈图的单源单汇和平面性等结构性质,本文给出了上述问题的一个时间复杂度为O(nk)的精确算法,这里n表示图中顶点数、k表示图中最大有向割所包含边的数目。

基于平均树值的无圈图博弈有效解

本文对无圈图博弈进行了研究,考虑了大联盟收益不小于各分支收益之和的情况。通过引入剩余公平分配性质,也就是任意两个分支联盟的平均支付变化相等,给出了一个基于平均树值的无圈图博弈有效解。同时,结合有效性和分支公平性对该有效解进行了刻画。特别地,若无圈图博弈满足超可加性时,证明了该有效解一定是核中的元素,说明此时的解是稳定的。最后,通过一案例分析了该有效解的特点,即越大的分支分得的剩余越多,并且关键参与者,也就是具有较大度的参与者可获得相对多的支付。

n阶无圈图的指数集

设 T(n,d)表示丛体恰含 d(d≥0)个环点的 n 阶无圈图构成的集合.文中证明了 T(n,d)的传递指数集 t_(n,d)为:t_(n,0)={1}∪{m|2≤m≤n—1且 m 为偶数}t_(n,1)={1}∪{2,4,…,2n—2}t_(n,d){1,2,…,n—1}∪({n,n+1,…,2(n—d)}∩{2i|i—1,2,…,n—d})(d≥2)进一步还刻划了传递指数分别达到上界 n—1,n—2,2n—2,及 max{n—1,2(n—d)}的极图的特征.

给定匹配数的无圈图的Laplacian谱半径的下界

在本文中,我们研究了无圈图的Laplacian谱半径与图的匹配数之间的关系,得到了Laplacian谱半径的与匹配数有关的一个精确下界。

基于有向无圈图的敏捷卫星姿态机动策略

针对敏捷卫星一次过境时间内的同轨拼幅观测和同轨多点连续观测模式的姿态机动策略问题,提出一种基于时间序有向无圈图的敏捷卫星姿态机动策略算法.该算法首先将区域目标和点目标转化为若干条带目标,然后通过将各个条带的观测时间窗口离散成一系列带有条带信息的时刻点,构造时间序有向无圈图,将敏捷卫星对地观测姿态机动策略问题转换为图论的寻找最优路径问题.仿真算例表明,该算法能够有效解决敏捷卫星同轨拼幅观测和多点连续观测的姿态机动策略问题,获得最大化观测覆盖收益同时机动时间消耗最小的姿态机动方案.

面向光子网格任务调度的迭代列表算法

光子网格中任务和通信的联合调度是一个非确定性多项式难题.为了进一步优化调度长度,本文在扩展列表算法的基础上,提出一种迭代列表调度算法.该算法通过扩展列表算法产生一个初始调度序列,并通过迭代的方式不断估计调度过程中子任务之间的通信时间;然后重新计算子任务的权重,调整子任务的调度序列,达到改善调度长度的目的.仿真实验表明,迭代调度算法对于大部分的实例能够有效地减少任务的调度长度,并且更加适用于数据密集型的任务调度.

一种通过结构边界进行贝叶斯网络学习的算法

贝叶斯网络是智能算法领域重要的理论工具,其结构学习问题被认为是NP-hard问题。该文通过混合学习算法的方式,从分析低阶条件独立性测试提供的信息入手,给出了构造目标网络结构空间边界的方法,并给出了完整的证明。在此基础上执行打分搜索算法获得最终的网络结构。仿真结果表明该算法与同类算法相比具有更高的精度和更好的执行效率。

图依能量的排序

图 G的能量指的是它特征值绝对值的和 .叙述了图依能量排序问题研究的基本工具与历史并著重介绍了 2 0世纪 90年代以来的新结果 ,同时指出若干猜想与未解决的问题 .

一种基于图的层次多标记文本分类方法

由于一个类别在层次树上可能存在多个镜像,基于层次树来进行分类可能会导致不一致性。一种自然的解决方法是采用图结构来描述类别关系,在现实生活中人们实际的描述方式也是如此。鉴于此,提出了一种直接基于图的层次多标记分类方法,称为GraphHMLTC。该方法利用有向无圈图的拓扑排序而非树的自顶向下的层次关系来确定类别之间的分类顺序,并且该拓扑序根据分类情形进行动态维护。实验表明,采用层次图分类的GraphHMLTC方法比非层次分类方法的代表之一BoosTexter.MH在较大程度上改善了分类精度。该工作体现了基于层次图的分类方法的可行性和优越性。

由图结构确定的交换环研究

针对由图结构所确定的交换环的代数结构、性质,本文深入讨论了无圈图(独点、星图、双星图)与交换环之间的对应关系,并确定了相应的交换环的代数结构及同构分类,同时对有圈图的图结构进行了刻画。结果表明:只有唯一条件符合时,环的零因子图才能确定,从而奠定完全图带一个角对应的交换环代数结构的理论与实践基础。

最优树的生成及应用

阐述和实现了生成最优树的算法—kruskl算法 。

多处理机系统中的任务调度

本文根据图论知识提出一种新算法旨在解决多处理机系统中的任务调度.本算法可以使系统的并行性有很大改善从而缩短程序的执行时间.文中用实例详细描述了算法的步骤.

极大祖先图的马尔可夫性质研究

极大祖先图可编码为含有潜变量的有向无圈图模型的条件独立性关系。不同的极大祖先图可表示相同的条件独立集,称之为马尔可夫等价。基于有向无圈图模型,给出了构造极大祖先图的算法,研究了极大祖先图的马尔可夫性质,并给出了构造极大祖先图马尔可夫等价类的方向准则。

数学奥林匹克问题

本期问题高737已知n∈Z_(+),非负实数x_(0),x_(1),…,x_(n)满足x_(0)=0,2x_(i)>x_(i-1)(i=2,3,…,n).证明:n∑k=1(k+1)^(2)/2x_(k)-x_(k-1)≥n∑k=1k^(2)/x_(k).高738给定一个(可有重边的)有向无圈图G=(V,E),对于顶点u、v,一条u→v的路径P是边的序列〈e_(1),e_(2),・・・,e_(l)〉,满足边e_(1)的始点为u,边e_(l)的终点为v,且对于任意的1≤i≤l-1,边e_(i+1)的始点为e_(i)的终点.

贝叶斯网边际马尔科夫子图及其应用

贝叶斯网络利用有向无圈图对多元联合概率分布中条件独立性进行约束,以实现其在不确定推理中的模块化分解,降低概率推理的计算复杂度.它在概率推理、机器学习和因果推理中都有广泛的应用.在实际中,如果采用分而治之或模型压缩的方法对贝叶斯网络进行结构学习或统计推断,那么需要人们寻找边际分布的极小马尔科夫子图(或极小独立图)来建立边际模型.为此,本文基于贝叶斯网的道义图研究贝叶斯网边际模型的极小马尔科夫子图,从统计和图论的观点对其进行了细致的刻画.针对DAG模型的可压缩性,本文将基于有向导出路径的性质给出更直观的等价条件,同时又给出了若干充分条件,这为判断模型是否可压缩到局部子模型上提供了更多的理论工具.

度序列与树中的叶子数

给出了树的度序列与叶子总数之间的关系式 ,从而得到一种精确地计算树的叶子数的方法 ,并证明了结论 :度序列满足该关系式的简单连通图必是树 .对树形图中的度序列和叶子数也有类似的结果 .

具有k个最大次点树的叶子数目估计

对于任意一棵具有k个最大次点树 ,采用细分、同胚的方法 ,得到如下结论 :任意一棵具有k个最大次点树都含有至少max{k(△ - 2 ) ,0 } +2个叶子 ;如果一棵树具有k个最大次点 (其中△ ≥ 3)并且其叶子数目为k(△ - 2 ) +2 ,则这棵树在同胚意义下的次序列是 (△ ,△ ,… ,△ ,k1,1,… ,1k(△ - 2 ) + 2) ,即具有k个最大次点且叶子数目为k(△ - 2 ) +2的树在同胚意义下的次序列是唯一的 .

贝叶斯网马尔可夫性的边缘化

贝叶斯网作为概率论与图论相结合的产物,在对不确定复杂系统进行建模以及降低概率推理的计算复杂度等方面具有不可替代的应用价值.当在大规模贝叶斯网上进行概率推理和数据分析时,往往不需要关心全部的变量,而是在少数变量集上进行统计推断或概率推理,这就需要人们考虑边缘模型的结构信息(即分布中的条件独立信息),而边缘模型结构实质上是马尔可夫性的边缘化.考虑到贝叶斯网的边际化运算并不封闭,文章重点研究了贝叶斯网边缘模型的极小独立图问题.在借鉴无向图模型的变量消元方法以及有向图中t-可去点定义的基础上,文章提出了有向无圈图的变量消元方法,并证明消元后所得到的图恰好是边缘化掉变量集后所得到的边缘模型的极小独立图.

图论中的树(二)

§2.树的定义 在各种各样的图中,有一类简单而重要的图,即所谓“树”。树之所以重要,不仅在于它在许多不同领域中应用,而且也在于图论本身。在图论中,解决许多悬而未决的问题往往是从树这一类图着手。