偏序集最小顶点割算法与最小费用赶工问题

在网络计划问题中,一项大的工程由许多工序合成。工序与工序之间存在着一定的前后关系,每个工序有着自己的正常加工时间和通过赶工所能达到的最短加工时间以及每赶工一天的赶工费用。设一项工程的正常工期为T天,通过对所有可能的工序赶工,整个工程能达到的最短工期为S天。本文的问题是,对于任意给定的t(S t<T),怎样确定所要赶工的工序及其赶工天数,在满足整个工程的完工时间恰为t天的条件下,使总的赶工费用最小。本文对这一问题给出了一个方便易行的有效算法,并将以往在(双代号)网络图上对工程工期的计算改为在工程的偏序图上进行,从而省去了烦琐的工程网络图(即偏序集的箭线图)的绘制。

一种基于网络顶点割的拓扑优化算法

优化网络设计是网络管理的目标之一。介绍一种基于关键链路分析和图的顶点割来优化网络拓扑结构设计的BTop算法,它结合流量工程和图形学理论对已有的网络拓扑进行优化设计。对算法的特性进行了分析,使用Abilene流量和拓扑数据验证了算法的有效性。

图的点割集及连通度的矩阵判断

给出一种利用图的邻接矩阵判断图的点割集及连通度的矩阵方法。

基于攻击路径图的网络攻击意图识别技术研究

针对目前网络攻击分析和威胁评估都是建立在静态的网络环境和攻击行为之上的问题,设计了网络攻击意图动态识别系统。研究了基于最小顶点割的攻击意图阻止算法和基于时间自动机的攻击意图动态识别算法,搭建了网络攻击意图动态识别系统的框架并完成了该系统的设计。最后搭建了临时实验网络平台进行实验,实验结果表明,网络攻击意图动态识别系统在测试环境下是正确有效的。

一类无爪图的Hamilton圈

设ｖ是图Ｇ＝（Ｖ，Ｅ）的顶点，若存在顶点μ∈Ｖ—｛ｖ｝，使子图Ｇ［Ｎ（ｖ）Ｕ｛μ｝］中任意一对顶点的距离不超过３，则称Ｖ是Ｇ的弱局部连通顶点。设Ｇ是非平凡的连通无爪图，且它的任一顶点割均包含一个弱局部连通顶点，则Ｇ包含Ｈａｍｉｌｔｏｎ圈。

循环图的最佳连通性

本文依据连通循环图有关连通度的性质,得到连通循环图具有最佳连通性的充要条件。依据这一充要条件,可判定一个连通循环图是否具有最佳连通性。

k_(p,q)(G)≤λ_(p,p)(G)成立的一些充分条件

设G是简单有限无向连通图,p,q是两个正整数.G的一个边割(顶点割)S是一个p-q-边割(p-q-顶点割),如果G-S不连通,且G-S中有一个分支至少含有p个顶点,另一个分支至少含有q个顶点.G称为λp,q-(kp,q-)连通的,如果一个p-q-边割(p-q-)顶点割存在.用pλ,q(G)(kp,q(G))表示最小p-q-边割(p-q-顶点割)的基数.文章证明了在kp,q-连通(p≤q)和λp,p-连通图G中,使kp,q(G)≤λp,p(G)成立的一些充分条件及k1,p-连通图的一些性质.