이언배 연구노트

job assignment problem 을 생각해보자.총 n 개의 job 이 있고, set $A$ 만큼의 지원자가 있다고 하자.$A$ 중에서 $A_i$ 가 $i$ 번째 직종에 지원 가능하다고 했을 때, $A_1$ 부터 $A_n$ 까지 각각 한명씩 매칭시킨 $x_1$ 부터 $x_n$ 을 찾을 수 있다.이게 대표적인 system of distinct representatives 문제. Definition.A matching: a set of pairwise non-incident edges (independent edges): vertex가 안겹치는 edge 들의 set.matching covers the vertices: matching 에 포함되는 edge 들에 닿은 vertex 들.perfect m..