最小可行图问题的一个必要条件及总结

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni =1 Xi 为顶点集的图G称为一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1,2 ,… ,n) ,导出子图Gi=GXi]是连通的。那么集合序列 (X1,X2 ,… ,Xn)的含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。曾得出了n =3时集合序列 (X1,X2 ,X3 )的最小可行图的一个充分必要条件。下面得出了n =4时集合序列 (X1,X2 ,X3 ,X4 )的最小可行图的一个必要条件 ,并用一个例子说明了n =3时的判定最小可行图的充分必要条件 ,不能推广至n≥ 4的情况 ,对最小可行图问题做了总结

A Necessary Condition and a Summary for Minimum Feasible Graph

For any sets X 1,X 2,...,X n,a graph with X=∪ni=1X i as vertex is called a feasible graph,if the induced subgrap G i=G(i=1,2,...,n) is connected. A feasible graph G is called a minimum feasible graph for (X 1,X 2,...,X n),if its number of edges is the least.A necessary and sufficient condition for the minimum feasible graph of set sequence (X 1,X 2,X 3) on n=3 was gotten before. In this paper, a necessary condition for the minimum feasible graph of set sequence (X 1,X 2,X 3,X 4)about n=4 was given, and that the necessary and sufficient condition on n=3 can not be extended to the condition on n≥4 was also proved with an example, and theproblems on minimum feasible graph was summarized.