摘要
该文推广了Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配的男孩－最优算法。证明了当男孩挑选时，允许某些男孩可以不挑选，则Ｇ－Ｓ匹配的最大步数为ｎ２－ｎ＋１。给出了一般情形下的Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配，即有ｍ个男孩，ｎ个女孩（ｍ≠ｎ）时，男孩－最优算法的最大步数是ｍ（ｍ－１）＋１（ｍ≤ｎ时），或ｎ（ｍ－１）＋１（ｍ＞ｎ时）；女孩－最优算法的最大步数是ｎ（ｎ－１）＋１（ｎ≤ｍ时），或ｍ（ｎ－１）＋１（ｎ＞ｍ时）。
出处
《南京理工大学学报》
EI
CAS
CSCD
1997年第6期569-573,共5页
Journal of Nanjing University of Science and Technology
关键词
男孩-最优匹配
G-S匹配
完全两部图
Gale Shapley matching,man optimal matching,woman optimal matching,complete bipartite graph.
