Tutte定理与Tutte-Berge公式的等价性证明

• 作者: 段侠 陈智斌
• 来源期刊: 曲阜师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 匹配理论 Tutte定理 Tutte-Berge公式 等价性 正则图
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 数学科学
• 页码范围: 51-55
• 页数: 5页
• 分类号: O157.5
• 字数: 4839字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5337.2016.2.051

摘要

Tutte定理在匹配理论中占有中心位置,刻画了一般图有完美匹配的充分必要条件.Tutte-Berge公式足任意图上关于最大匹配的一个核心结果,确定了匹配数的一个最大最小关系,且提供了任意图中匹配数的一个紧的上界.Tutte定理常常被认为是Tutte-Berge公式的一个特殊情形.提供Tutte定理与Tutte-Berge公式的一个简单而完整的等价性证明,从而说明Tutte-Berge公式也是Tutte定理的一个特殊情形.作为Tutte公式的一个应用,考察并总结了任意正则图中是否具有完美匹配的情况,结果包含了著名的Petersen定理.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	段侠	昆明理工大学理学院	2	0	0.0	0.0
2	陈智斌	昆明理工大学理学院	11	18	3.0	4.0