10. Паросочетания.

Многие комбинаторные приложения теории графов естественно приводят к понятиям паросочетания и трансверсали. Цель контрольной работы -

изучить постановки важных комбинаторных задач и основные методы их решения с помощью теории графов. Рекомендуется следующий план работы:

1) Изучить такие основополагающие понятия теории графов, как граф, двудольный граф и паросочетание (/1/, с. 9-43, 144-146; /3/, с. 154-159).

2) Рассмотреть известную задачу о свадьбах и доказать теорему Холла (/1/, с. 144-147; /2/, с. 168-173).

3) Изучить теорию трансверсалей и ее приложение к задачам о паросочетаниях (/1/, с. 148-150). 4 Разобрать приложения теоремы Холла к латинским квадратам, реберным раскраскам графов и (0,1)-матрицам (/1/, с. 151-156).

Литература, рекомендуемая для изучения темы