图论中独立支配集的最佳求解算法研究

通过对图论中独立集和支配集的深入研究，提出了独立支配集的概念，论证了独立支配集同极大独立集及极小支配集之间的内在联系，并在此基础上给出了独立支配集的最佳求解算法，从而圆满地解决了图论中独立集及支配集的求解问题，对图的着色及匹配等问题的研究均有相当重要的借鉴意义。

An Optimum Solving Algorithm of Independent-Dominating Set in Graph Theory

Through researching into the independent and dominating set in graph theory, this paper has put forward a concept of independent-dominating set and has expounded and proved the internal relationship among the following three concepts: independent-dominating set , maximal independent set and minimal dominating set. On the basis of arranging the vertices set of a given graph in a reasonable sequence, this paper has given out some optimun solving algorithms with a low complexity O(n3) , which has settled satisfactorily and efficiently the solving problem of maximum independent (-dominating) set and minimum (independent-) dominating set in graph theory. The method and the algorithms provided in this paper can certainly be used for reference in studying the problems of graph coloring, covering and matching and so on.