一种双端网络简化方法

摘要

本发明涉及一种双端网络简化方法，它采用如下的方案步骤，步骤一：计算关节点集合；步骤二：计算无效顶点集合；步骤三：生成精简双端网络；它采用一种高效快速的简化方法，能够识别中双端网络中所有无效元素，并对它们进行消减，从而构造更为精简的双端网络。

主权项

一种双端网络简化方法，其特征在于：它采用如下的方案步骤：步骤一：计算关节点集合；其采用如下方法步骤：1)所谓关节点就是在双端网络中删除某个顶点及其附属的边，双端网络变为非连通的；2)根据定义可以对网络中的每个顶点采用删除并检测是否连通的方法判定该顶点是否是关节点，从而找出所有关节点；步骤二：计算无效顶点集合；其采用如下方法步骤：1)从原始双端网络中，删除步骤一所获得的所有关节点以及和从这些关节点出发的边，得到若干个非连通的子网；2)如果一个子网不包含顶点s或顶点t，则该子网的所有顶点都认定为无效顶点；步骤三：生成精简双端网络；其采如下方法步骤：1)从原始双端网络中，删除步骤二所获得的所有无效顶点；2)从这些无效顶点出发的边得到的唯一连通子网就是所要求的精简双端网络。