Паросочетание: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Tosha (обсуждение | вклад) |
|||
Строка 125:
=== Максимальные паросочетания ===
Максимальное паросочетание можно найти простым жадным алгоритмом. Наибольшее паросочетание является также максимальным, и, поэтому, имеется возможность найти ''самое большое'' максимальное паросочетание за полиномиальное время. Однако неизвестно никакого полиномиального по времени алгоритма для нахождения '''
Заметим, что наибольшее паросочетание из ''k'' рёбер является {{не переведено 5|Рёберное доминирующее множество|рёберным доминирующим множеством||edge dominating set}} с ''k'' рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с ''k'' рёбрами, мы можем построить наибольшее паросочетание с ''k'' рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества<ref>{{статья
Строка 136:
| doi=10.1137/0138030
| выпуск=3
}}</ref>. Обе эти задачи оптимизации известны как [[Класс NP|NP-трудные]],
{{книга
| автор=Michael R. Garey, David S. Johnson
| |||