对缺失n-可扩图的研究

书籍简介:

n可扩图（n-extendable graph）是匹配可扩理论中的重要图类。它是包含n条独立边并且任意一个边数为n的匹配都可以扩展成为该图的完美匹配的连通图。是由著名图论学家Plummer[1]在 上世纪80年代初提出。n可扩偶图是资源可扩分配问题的抽象模型。随之图的匹配可扩性成为匹配理论研究的一个重要内容。近年来，各国数学家和计算机科学家对此进行了大量的研究工作。由n可扩图的定义可知，n可扩图是在偶数个顶点上具有匹配可扩性的图，考虑到在所有图中，有一半图的顶点数为奇数以及奇顶点数图的匹配可扩性与偶顶点数图的匹配可扩性的差异，本书作者提出的一个新的概念：缺失n可扩图（defect n-extendable graph）。如果一个连通图包含n条独立边并且任意一个边数为n的匹配都可以扩展为该图的一个几乎完美匹配，则称其为缺失n可扩图。基于下面三方面原因，缺失n可扩图是值得研究的。

书籍规格:

书籍信息归属:

对缺失n-可扩图的研究是经济科学出版社于2015.12出版的中图分类号为 O157.5 的主题关于 图论算法 的书籍。