Паросочетание: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Tosha (обсуждение | вклад) |
Tosha (обсуждение | вклад) |
||
Строка 125:
=== Максимальные паросочетания ===
Максимальное паросочетание можно найти простым [[Жадный алгоритм|жадным алгоритмом]].
Наибольшее паросочетание является также максимальным, и, поэтому, имеется возможность найти ''самое большое'' максимальное паросочетание за полиномиальное время. Однако неизвестно никакого полиномиального по времени алгоритма для нахождения '''наименьшего максимального паросочетания''', то есть максимального паросочетания, содержащего ''наименьшее возможное'' число рёбер. Заметим, что наибольшее паросочетание из ''k'' рёбер является [[Доминирующее множество рёбер|рёберным доминирующим множеством]] с ''k'' рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с ''k'' рёбрами, мы можем построить наибольшее паросочетание с ''k'' рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества<ref>{{статья
| |||