최근 편집
최근 토론
게시판 메인
도구
투표
무작위 문서
스킨 설정
파일 올리기
기타 도구
216.73.216.143
IP
사용자 도구
사용자 설정
로그인
회원 가입
최근 편집
최근 토론
돌아가기
삭제
이동
파일 올리기
The Dinitz Problem
(편집) (7)
(편집 필터 규칙)
4117,4842
=== 보조정리 2 === 임의의 이분그래프 [math(G=(U \cup V, E))]의 stable matching이 존재한다. '''Proof''' Gale-Shapley Algorithm의 타당성을 증명하면 된다. 짝을 찾지 못한 [math(R)]의 원소들은 매 턴마다 고백하는 [math(V)]의 원소의 우선순위가 낮아지므로 언젠가 자신의 마지막 우선순위에 있는 원소에게 고백을 하게 되고, 결국 짝을 찾지 못했다면 [math(R)]에서 나가게 된다. 즉 [math(|R|)]은 언젠가 0이 되며, 이 알고리즘은 종료된다. 알고리즘이 종료됬을 때 어떤 [math((u-v) \in E \setminus M)]을 보자. 만약 [math(u)]가 [math(v)]에게 고백을 해보지 않았다면 [math(u)]는 우선순위가 높은 원소에게 먼저 고백을 하므로 [math(v)]보다 우선순위가 높은 짝을 가지고 있다는 것이 되고, 즉 [math((u-v’) \in M,\ N(u,v)<N(u,v’))]인 [math(v’)]가 존재한다. 그리고 [math(u)]가 [math(v)]에게 고백을 해보았다면 [math(v)]가 [math(u)]를 찬 것이므로 [math(u)]보다 우선순위가 높은 짝을 가지고 있다는 것이 되고, 즉 [math((u’-v) \in M,\ N(v,u)<N(v,u’))]인 [math(u’)]가 존재한다. 그러므로 알고리즘의 결과물은 stable matching이다.
(임시 저장)
(임시 저장 불러오기)
기본값
모나코 에디터
normal
namumark
namumark_beta
macromark
markdown
custom
raw
(↪️)
(💎)
(🛠️)
(추가)
=== 보조정리 2 === 임의의 이분그래프 [math(G=(U \cup V, E))]의 stable matching이 존재한다. '''Proof''' Gale-Shapley Algorithm의 타당성을 증명하면 된다. 짝을 찾지 못한 [math(R)]의 원소들은 매 턴마다 고백하는 [math(V)]의 원소의 우선순위가 낮아지므로 언젠가 자신의 마지막 우선순위에 있는 원소에게 고백을 하게 되고, 결국 짝을 찾지 못했다면 [math(R)]에서 나가게 된다. 즉 [math(|R|)]은 언젠가 0이 되며, 이 알고리즘은 종료된다. 알고리즘이 종료됬을 때 어떤 [math((u-v) \in E \setminus M)]을 보자. 만약 [math(u)]가 [math(v)]에게 고백을 해보지 않았다면 [math(u)]는 우선순위가 높은 원소에게 먼저 고백을 하므로 [math(v)]보다 우선순위가 높은 짝을 가지고 있다는 것이 되고, 즉 [math((u-v’) \in M,\ N(u,v)<N(u,v’))]인 [math(v’)]가 존재한다. 그리고 [math(u)]가 [math(v)]에게 고백을 해보았다면 [math(v)]가 [math(u)]를 찬 것이므로 [math(u)]보다 우선순위가 높은 짝을 가지고 있다는 것이 되고, 즉 [math((u’-v) \in M,\ N(v,u)<N(v,u’))]인 [math(u’)]가 존재한다. 그러므로 알고리즘의 결과물은 stable matching이다.
비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.
편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이
CC BY 4.0
에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.
전송
미리보기
