期刊文献+

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

A Necessary Condition and a Summary for Minimum Feasible Graph
下载PDF
导出
摘要 设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni =1 Xi 为顶点集的图G称为一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。那么集合序列 (X1,X2 ,… ,Xn)的含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。曾得出了n =3时集合序列 (X1,X2 ,X3 )的最小可行图的一个充分必要条件。下面得出了n =4时集合序列 (X1,X2 ,X3 ,X4 )的最小可行图的一个必要条件 ,并用一个例子说明了n =3时的判定最小可行图的充分必要条件 ,不能推广至n≥ 4的情况 。 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.
出处 《抚顺石油学院学报》 2002年第4期81-83,共3页 Journal of Fushun Petroleum Institute
关键词 最小可行图 必要条件 可行图 导出子图 Feasible graph Minimum feasible graph Induced subgraph
  • 相关文献

参考文献5

二级参考文献4

  • 1唐廷载.一个最小可行图的判定条件[J].应用数学,1989,2(2):21-24. 被引量:7
  • 2杜丁柱 陈玉敏.真空系统的有效设计[J].光源,1976,4:54-62.
  • 3杜丁柱.关于图的一个优化问题[J].离散数学,1986,14(1):101-104.
  • 4Andrasfai B 郭照人(译).图论导论[M].北京,1985..

共引文献6

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部