论文部分内容阅读
图中的最大团问题与最大独立集问题均属于图论中经典的NP-完全问题，该类问题所具有的固有困难，已使其普遍有效算法的寻求变得希望渺茫。但由于该类问题深刻而广泛的理论及应用背景，寻求其尽可能有效的精确算法和近似算法，近年来仍是计算数学工作者们十分关注的课题。 本文首先介绍了最大团及最大加权独立集问题的数学含义及其关系。对该类问题在国内外研究现状的介绍，重点放在各种精确算法和启发式算法的思想以及基本算法流程方面。 本文进一步重点阐述了Q0-1规划模型 main f（X）=CTX+1/2XTQX，X∈{0,1}n(其中Q=（qη）n×n是一个n×n阶的有理矩阵，C是一个n维有理向量)的背景及其一般形式，并具体介绍了求解该类模型使用的分支定界算法。上述模型和算法是本文模型和算法的基础。 在第三、第四、第五章中，作者基于上述Q0-1规划模型提出了形式更为简洁的Q0-1规划模型，此种模型与原有模型相比，与图的基本不变量具有更直接对应关系，这一改进对建模过程的简化特别有效。在此模型基础上，本文首先针对非加权最大团问题给出其分支定界法的理论基础及算法步骤直至算法实例，其次，又针对最大加权独立集问题进一步