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

【Abstract】 In this paper we have analyzed the structure and characteristics of a connected network, and discovered a special kind of sub-network, which can optimize the iteration processes, and then deduced the sufficient and necessary conditions for obtaining the maximum independent set. Afterwards, we have detected that the neighborhood of this sub-network possesses the similar characters to it, but both can never be allowed incorporated together. Particularly, we have detected and identified that as you divide the network into two parts by a certain style, then transform both of them into a pair set network, where you can find that the special sub-networks and their neighborhoods appear themselves alternately distributed one by another throughout the entire pair set network. By use of this characteristic you can get the network decomposed enough without losing any solutions. All of these above have made well ready for developing a new algorithm, which will be able to search for maximum independent set in an odd network with polynomial time bound of O(|V|5).更多还原