论文部分内容阅读
图Ｇ的一个匹配Ｍ是导出的，若Ｍ是图Ｇ的一个导出子图。图Ｇ是导邮匹配可扩的（简记ＩＭ－可扩的），若图Ｇ的任一导出匹配均含于图Ｇ的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言，问题“给定图Ｇ以及一个正整数ｒ，确定是否存在图Ｇ的一个导出匹配Ｍ使得Ｍ≥ｒ”是ＮＰ－完全的。⑵对直径为２的图以及直径为３的偶图，问题“确定一个给定图是否为导出匹配可扩的”是ＣＯ－ＮＰ完全的；而对完全多部图而言，问题“