tailieunhanh - Thuật toán Algorithms (Phần 46)

Tham khảo tài liệu 'thuật toán algorithms (phần 46)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 34. Matching A problem which often arises is to pair up objects according to prefer ence relationships which are likely to conflict. For example a quite complicated system has been set up in the U. S. to place graduating medical students into hospital residence positions. Each student lists several hospitals in order of preference and each hospital lists several students in order of preference. The problem is to assign students to positions in a fair way respecting all the stated preferences. A sophisticated algorithm is required because the best students are likely to be preferred by several hospitals and the best hospital positions are likely to be preferred by several students. It s not even clear that each hospital position can be filled by a student that the hospital has listed and each student can be assigned to a position that the student has listed let alone respect the order in the preference lists. Actually this frequently occurs after the algorithm has done the best that it can there is a last minute scramble among unmatched hospitals and students to complete the process. This example is a special case of a difficult fundamental problem on graphs that has been widely studied. Given a graph a matching is a subset of the edges in which no vertex appears more than once. That is each vertex touched by one of the edges in the matching is paired with the other vertex of that edge but some vertices may be left unmatched. Even if we insist that there should be no edges connecting unmatched vertices different ways of choosing the edges could lead to different numbers of leftover unmatched vertices. Of particular interest is a mazimum matching which contains as many edges as possible or equivalently which minimizes the number of unmatched vertices. The best that we could hope to do would be to have a set of edges in which each vertex appears exactly once such a matching in a graph with 2V vertices would have V edges but it is not always possible to achieve this. .