[1]连广昌,朱顺荣.Gale-Shapley 匹配的推广[J].南京理工大学学报(自然科学版),1997,(06):93-97.
 LianGuangchang ZhuShunrong.The Extensions on Gale Shapley Matching[J].Journal of Nanjing University of Science and Technology,1997,(06):93-97.
点击复制

Gale-Shapley 匹配的推广()
分享到:

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

卷:
期数:
1997年06期
页码:
93-97
栏目:
出版日期:
1997-12-30

文章信息/Info

Title:
The Extensions on Gale Shapley Matching
作者:
连广昌朱顺荣1
金陵职业大学, 南京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
摘要:
该文推广了Gale-Shapley匹配的男孩-最优算法。证明了当男孩挑选时,允许某些男孩可以不挑选,则G-S匹配的最大步数为n2-n+1。给出了一般情形下的Gale-Shapley匹配,即有m个男孩,n个女孩(m≠n)时,男孩-最优算法的最大步数是m(m-1)+1(m≤n时),或n(m-1)+1(m>n时);女孩-最优算法的最大步数是n(n-1)+1(n≤m时),或m(n-1)+1(n>m时)。
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) .

参考文献/References:

1 Gale D, Shapley L S. Colley e admissions a nd the st ability o f ma rr iag e. Amer M ath Monthly,1962, 69: 9~14
2 Eug ene L, Low ler . Combinato rial optimiza tio n. Netw or ks and Mat ro ids, Ho lt , Rinehart and Winston, San Fr ancisco , 1976 211~213

备注/Memo

备注/Memo:
连广昌 男 57岁 副教授
更新日期/Last Update: 2013-03-29