Паросочетание: различия между версиями

Некоторые авторы используют термин '''''«максимальное паросочетание»''''' для наибольшего паросочетания<ref>{{Книга|автор=Фуад Алескеров, Элла Хабина, Дмитрий Шварц|заглавие=Бинарные отношения, графы и коллективные решения|ссылка=https://books.google.com/books?id=5QR4CwAAQBAJ&pg=PA22|издательство=Litres|год=2016-01-28|страницы=22|страниц=343|isbn=9785457966925}}</ref><ref>{{Книга|автор=Рубчинский А. А|заглавие=Дискретные математические модели. Начальные понятия и стандартные задачи|ссылка=https://books.google.com/books?id=QdtSBAAAQBAJ&pg=PA136|издательство=Directmedia|год=2014-08-06|страницы=136|страниц=269|isbn=9785445838029}}</ref><ref>{{Книга|автор=Леонид Гладков, Владимир Курейчик, Виктор Курейчик|заглавие=Генетические алгоритмы|ссылка=https://books.google.com/books?id=sf93CwAAQBAJ&pg=PA276|издательство=Litres|год=2016-01-28|страницы=276|страниц=367|isbn=9785457965997}}</ref><ref>{{Книга|автор=Леонид Гладков, Владимир Курейчик, Виктор Курейчик, Павел Сороколетов|заглавие=Биоинспирированные методы в оптимизации|ссылка=https://books.google.com/books?id=Ywp4CwAAQBAJ&pg=PA330|издательство=Litres|год=2016-01-28|страницы=330|страниц=381|isbn=9785457967472}}</ref>.

 

 

'''Почти совершенным паросочетанием''' называется паросочетание, в котором не участвует ровно одна вершина. Это может произойти, если граф имеет нечётное число вершин. На рисунке выше паросочетание в графе (c) является почти совершенным. Если для любой вершины в графе существует почти совершенное паросочетание, не содержащее именно эту вершину, граф называется [[Фактор-критический граф|факторно-критическим]].