Задача о свадьбах

Материал из WikiGrapp
Перейти к:навигация, поиск

Задача о свадьбах (Marriage problem) — Известно некоторое множество X юношей, каждый из которых знаком с несколькими девушками. При каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой ему девушке? Математическая постановка задачи состоит в нахождении в двудольном графе (X,Y,E) паросочетания, покрывающего X.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.