奇网络及包络图

Nonbipartite Network and Envelope Graphs in It

本文提出了奇网络内存在包络图的理论，揭示了包络图与网络流以及独立集等之间的重要关系，并成功地对奇网络进行了分解，给出了一般奇网络内求最大独立集的新算法。

Envelope Graph introduced in this paper is a natural structure in a network. Both bipartite and nonbi-partite networks can be decomposed ,into a series of negative and reversal negative envelope graphs alternatively distributed without exception. The closed characteristics of envelope graphs make it possible to detect and search in subnetworks instead of in an integrated large scale network without losing global optimal solution. Especially, we found that negative envelope graphs are closely related to many important issues in graph theory. For instance,by use of negative envelope graph, a polynomial algorithm of Maximum Indepen- . dent Set in general nonbipartite network is presented in this paper.