网络分解及最大独立集算法研究(Ⅰ)

本文首先分析了一般网络的结构特征,开发出对任意网络进行变换及分解、且不丢失可行解的新方法。继而发现了网络中具有优化迭代功能的特殊子网络;对其进行了较深入的研究,提出并论证了求最大独立集的充要条件;研制出在网络中系统搜索该特殊子网络的新算法。最后,对算法的有效性及可靠性,进行了较全面的分析论证。研究表明,该算法可在时间复杂性O(|V|5)界内收敛。

网络分解及最大独立集算法研究(II)

本文首先分析了一般连通网络的结构特征,发现了网络中具有优化迭代功能的特殊子网络;并对其进行了较深入的研究,提出并论证了求最大独立集的充要条件。进一步的研究发现,此特殊子网络及其邻域,具有相依、相斥的偶对性质;若按某种方式将连通网络划分成两部分,形成网络对集,则较容易看出,此特殊子网络及其邻域,将一个接一个地交叉分布,遍及整个网络。利用这个性质,就可对网络进行充分的分解,而不丢失可行解。在上述基础上,开发出在奇网络中搜索该特殊子网络及求最大独立集的新算法,并对算法的有效性及可靠性,进行了较全面的分析。研究表明,该算法可在时间复杂性O(|V|5)界内收敛。