961
个编辑
更改
→Matching 匹配
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job. A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job. A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.
举一个简单的例子，假设一组''P''的所有人都在一组''J''的职位中寻找工作，但并不是所有人都适合所有职位。可以将这种情况建模为一个二分图''（P，J，E）''，其中当每个求职者找到其合适的工作时产生的关系就作为连边。一个完美的匹配描述的是所有求职者同时找到所有工作的情况；'''<font color="#ff8000"> 霍尔的婚姻定理Hall's marriage theorem</font>'''阐述的就是二分图允许完美匹配的特征。美国国民住院医师匹配项目采用的就是图形匹配法来解决美国医学生求职者和医院实习工作的匹配问题。