«上一篇/Previous Article|本期目录/Table of Contents|下一篇/Next Article»

《南京理工大学学报》（自然科学版）[ISSN:1005-9830/CN:32-1397/N]

卷:

期数:

1997年06期

页码:

93-97

栏目:

出版日期:

1997-12-30

文章信息/Info

Title:

The Extensions on Gale Shapley Matching

作者:

连广昌; 朱顺荣¹

金陵职业大学, 南京210008)
 ¹ 南京理工大学理学院, 南京210094

Author(s):

LianGuangchang ZhuShunrong ①

Nanjing Polyt echnic College,Nanjing 210008
① School of Sciences,NUST,Nanjing 210094

关键词:

Gale-Shapley 匹配;  男孩-最优匹配;  女孩-最优匹配;  完全两部图。

Keywords:

Gale-Shapley mat ching;  man-opt imal matching;  woman-opt imal matching;  complet e bipart it e graph.

分类号:

O241

摘要:

该文推广了Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配的男孩－最优算法。证明了当男孩挑选时，允许某些男孩可以不挑选，则Ｇ－Ｓ匹配的最大步数为ｎ２－ｎ＋１。给出了一般情形下的Ｇａｌｅ－Ｓｈａｐｌｅｙ匹配，即有ｍ个男孩，ｎ个女孩（ｍ≠ｎ）时，男孩－最优算法的最大步数是ｍ（ｍ－１）＋１（ｍ≤ｎ时），或ｎ（ｍ－１）＋１（ｍ＞ｎ时）；女孩－最优算法的最大步数是ｎ（ｎ－１）＋１（ｎ≤ｍ时），或ｍ（ｎ－１）＋１（ｎ＞ｍ时）。

Abstract:

　T he man-optimal algorithm in the Gale-Shapley mat ching is ex tended in this paper. T he most st ages for the G-S matching is n 2 - n+ 1 when we admit some boys may not select at each st age. It is generalized t o general cases: when there arem boys and n girles ( m ≠n ) , the most st ages f or the man-opt imal algorithm in the G-S matching is m(m - 1) + 1 ( when m ≤ n) or n( m - 1) + 1 (w hen m > n) , and the most st ages f or the women-opt imal algorithm is n( n - 1) + 1 ( when n ≤ m) or m(n - 1) + 1 ( w hen n > m) .

备注/Memo

备注/Memo:

连广昌　男　57岁　副教授

常用功能

更新日期/Last Update: 2013-03-29