|
|||||
|
|
| Gale—Shapley匹配的推广 | |
| 引用本文： | 连广昌,朱顺荣.Gale—Shapley匹配的推广[J].南京理工大学学报(自然科学版),1997,21(6):569-573. |
| 作者姓名： | 连广昌 朱顺荣 |
| 作者单位： | 金陵职业大学(连广昌)，南京理工大学理学院(朱顺荣) |
| 摘 要： | 该文推广了Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配的男孩－最优算法。证明了当男孩挑选时，允许某些男孩可以不挑选，则Ｇ－Ｓ匹配的最大步数为ｎ＾２－ｎ＋１。给出了一般情形下的Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配，即有ｍ个男孩，ｎ个女孩时，男孩－最优算法的最大步数是ｍ（ｍ－１）＋１，或ｎ（ｍ－１）＋１；女孩－最估算法的最大步数是ｎ（ｎ－１）＋１，或ｍ（ｎ－１）＋１。 |
| 关 键 词： | 男孩－最优匹配 G－S匹配 完全两部图 |
| 本文献已被 CNKI 维普 等数据库收录！ | |