Паросочетание: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Vayvor (обсуждение | вклад) отмена правки 63776328 участника Ludmila 95 (обс): не путать наибольшее и максимальное паросочетание! |
Jumpow (обсуждение | вклад) м →Наибольшие паросочетания: Описка |
||
Строка 122:
=== Наибольшие паросочетания ===
Наибольшее паросочетание можно найти простым жадным алгоритмом. Максимальное паросочетание является также наибольшим, и, поэтому, имеется возможность найти ''самое
Заметим, что наибольшее паросочетание из ''k'' рёбер является {{не переведено 5|Рёберное доминирующее множество|рёберным доминирующим множеством||edge dominating set}} с ''k'' рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с ''k'' рёбрами, мы можем построить наибольшее паросочетание с ''k'' рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру наибольшего паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества<ref>{{статья
| |||