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

摘要：

设有n个集合X1,X2,…,Xn,一个以X=∪ni=1Xi为顶点集的图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的情况,对最小可行图问题做了总结.

关键词：可行图、最小可行图、导出子图

所属期刊栏目：22

分类号：O29;TB2(应用数学)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：81-83