运筹学-匹配与覆盖问题(名校讲义)_图文.ppt
§1 问题的现实来源 （1）

匹配和覆盖问题是图论的一个重要分支，在介绍它的基本定义和有关算法之前，先举例说明其应用背景。[例5-18]第二次世界大战时，英国空军曾招募了许多沦陷国的飞行员。空军飞机上需配备两名在航空技能与语言技能上都相协调的飞行员（当然，一般一个飞行员可与其多个飞行员搭配）。问如何将众多飞行员进行搭配，才能使发出的飞机数目最多？
§1 问题的现实来源 （2）

[例5-19]某国家有50个州和65个民族，该国需成立参谋委员会，委员会要求每州至少一人和每个民族也至少一人，同时希望人员尽量少。现已从全国推选出170人准备参加该委员会，问如何挑选，才能满足上面要求？这两个问题就是典型的匹配和覆盖问题。