Максимальное совпадение в двудольном графе - PullRequest
Новая
       11

Максимальное совпадение в двудольном графе

4 голосов
/ 26 ноября 2010

Используйте следующий эвристический алгоритм: 

M = NULL
while E != NULL do {
if ((∃u vertex) and (gr(u) == 1)) then 
    e ← the incident edge with u
  else 
    e ← an incident edge with a vertex with the most incident edges
M ← M ∪ {e}
E ← E - (all the incident edges with e)
}
return M //return the matching

Где: М, Е - ребра; gr (u) - оценка u (количество падающих ребер с u);

Что нас спросили: 

  a) Prove that this algorithm returns the maximum matching for a tree.
  b) Prove that if there is a perfect matching M0 then the algorithm returns it, for any bipartite graph.
  c) Prove that |M| ≥ (v(G)/2), for any bipartite graph. 
  //G is the graph, v(G) is the matching number, size of the maximum matching.

Я почти уверен, что этот алгоритм похож на некоторый классический алгоритм, который мне не удается найти, или решение может быть полностью основано на теоремах и свойствах двудольных графов.

Не могли бы вы дать мне отправную точку .. Чего мне не хватает?

Я думаю, а) это просто .. Я все еще пытаюсь найти правильное доказательство, я думаю, что оно может быть полностью основано на свойствах деревьев и двудольных графов.
Для б) и в) .. Понятия не имею.

1 Ответ

2 голосов
/ 26 ноября 2010

Это очень похоже на жадный алгоритм сопоставления. См. статью в Википедии для получения дополнительной информации.

Что касается вопросов ... 

a) Show that the matching you get is maximal (there are no larger matchings containing it). What does this imply on a tree?
b) Show that if M0 is a valid matching that can be found in M ∪ E in a given step, that it can be found in M ∪ E in the next. By induction, the statement holds.
c) Consider a maximum matching M1. Why must at least one of the vertices adjacent to any given edge in M1 appear as an endpoint for some edge in the matching the algorithm outputs? What does this tell you about a lower bound for its size?
...