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

• 作者: 贾治中 魏丽侠
• 来源期刊: 抚顺石油学院学报
• 学科: 工学
• 关键词: 可行图 最小可行图 导出子图
• 年，卷（期）: 2002,（4）
• 所属期刊栏目: 其它科学
• 页码范围: 81-83
• 页数: 3页
• 分类号: O29|TB2
• 字数: 1979字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-6952.2002.04.023

摘要

设有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的情况,对最小可行图问题做了总结.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	魏丽侠	辽宁石油化工大学信息工程学院	1	0	0.0	0.0
2	贾治中	辽宁石油化工大学理学院	1	0	0.0	0.0