Изменения

Перейти к: навигация, поиск
Теорема о мощности MVC и MM
и <tex>L^-</tex> нет, то каждому ребру <tex>MM</tex> инцидентна ровно одна вершина из <tex>L^- \cup R^+</tex>.
Тогда <tex>|L^- \cup R^+| = |MM| \le \min(|L|, |R|)</tex>. Значит, минимальным вершинным покрытием является <tex>L^- \cup R^+</tex> и <tex>|MVC| = |MM|</tex>.
}}
Анонимный участник

Навигация