Двудольные графы и паросочетания

Рассмотрим задачу о назначении на должности. Пусть в некотором учреждении имеется 6 вакантных должностей y₁,y₂,…,y₆ и 6 работников x₁,x₂,…,x₆. Граф D, изображенный на рис.5, иллюстрирует, какие должности y может в силу своей квалификации занимать работник x. Пусть выполнено условие: каждый работник может занимать только одну должность, и каждая работа выполняется только одним работником. Тогда решение этой задачи сводится к построению наибольшего паросочетания в данном двудольном графе.

x₁ x₂ x₃ x₄ x₅ x₆

y₁ y₂ y₃ y₄ y₅ y₆

Рис. 5.