bipartitematching (3) 썸네일형 리스트형 이분 매칭에 관한 몇 가지 반례들 매칭(matching), 특히 이분 매칭(bipartite matching)은 제 주된 연구 분야 중 하나입니다. 제 블로그에 매칭 관련된 포스트가 가장 많은 것을 보면 쉽게 유추할 수 있으시리라 생각합니다. 최근 개인적으로 이분 매칭과 관련하여 몇 가지 명제를 세워 증명해 보려고 했습니다. 만약 참으로 밝혀진다면 제가 요즘 하는 연구에 도움이 될 명제들이었습니다. 하지만 안타깝게도 모두 반례가 존재하였습니다. 어디 가서 써 먹을 곳도 없다 보니 약간은 울적한 마음에 블로그에라도 적어 보려고 합니다. 혹여 비슷한 주제를 고민하시는 분들이 계시다면 이 글이 약간의 도움이 되었으면 합니다. 차수와 간선 서로소인 최대 매칭의 개수 첫 번째 명제는 다음과 같았습니다. 어떤 이분 그래프의 최소 차수(degree).. 온라인 이분 매칭 랭킹 알고리즘 (Ranking Algorithm for Online Bipartite Matching) 지난번에 온라인 이분 매칭 문제(online bipartite matching problem)에 대해서 알아 보았습니다. 그 문제는 다음과 같이 정의되었습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 한 명도 태우지 않은 택시 가운데 한 대를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 바로 결정해야 한다. 이 결정은 번복될 수 없다. 이때 목표는 승객을 최대한 많이 태우는 것이다. 저번 글에서 공부한 내용을 요약하면 다음과 같습니다. 승객이 매번 들어올 때마다 가능한 택시 중 아무 하나에 이 승객을 태우는 방법은 1/2의 .. 온라인 이분 매칭 (Online Bipartite Matching) 어떤 그래프에서 서로 정점을 공유하지 않는 간선의 부분집합을 우리는 매칭(matching)이라고 부릅니다. 매칭의 모양을 살펴보면, 각 정점이 최대 하나의 다른 정점과 짝지어진 꼴입니다. 이를 통해 왜 이러한 간선의 부분집합에 매칭이라는 이름이 붙었는지를 쉽게 유추할 수 있죠. 어떤 그래프가 주어졌을 때, 크기가 작은 매칭을 찾는 것은 간단합니다. 정의에 따르면 아무 간선을 고르지 않는 방법도 가능한 매칭이기 때문이죠. 따라서 대개 우리는 크기가 가장 큰 매칭을 찾고자 하죠. 이 문제를 우리는 최대 매칭 문제(maximum matching problem)이라고 부릅니다. 이 문제는 실생활에서 발생할 수 있는 여러 문제들을 효과적으로 나타냅니다. 이미 제 블로그의 다른 글들을 통해 이에 대한 다양한 예시를.. 이전 1 다음
