图的极大Tutte集的几个有效算法

• 作者: 李德明 简芳洪
• 来源期刊: 数学的实践与认识
• 学科: 数学
• 关键词: Tutte集 extreme集 def(G) D-图 最大匹配 最小覆盖
• 年，卷（期）: 2012,（4）
• 所属期刊栏目: 研究
• 页码范围: 195-199
• 分类号: O157.5
• 字数: 2749字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-0984.2012.04.026

摘要

图G=(V,E)的Tutte集定义为X(∈)V(G)满足ωo(G-X)-｜X｜=def(G).若不存在Tutte集Y(∩)X,则称X为图G的极大Tutte集.通过找极大extreme 集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X(∈)V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	简芳洪	九江学院理学院	10	8	2.0	2.0
2	李德明	首都师范大学数学科学学院	21	59	5.0	7.0