Рассмотрим задачу о назначении на должности. Пусть в некотором учреждении имеется 6 вакантных должностей y1,y2,…,y6 и 6 работников x1,x2,…,x6. Граф D, изображенный на рис.5, иллюстрирует, какие должности y может в силу своей квалификации занимать работник x. Пусть выполнено условие: каждый работник может занимать только одну должность, и каждая работа выполняется только одним работником. Тогда решение этой задачи сводится к построению наибольшего паросочетания в данном двудольном графе.
x1 x2 x3 x4 x5 x6
y1 y2 y3 y4 y5 y6
Рис. 5.