Различные постановки задач о паросочетаниях

1.Задача о свадьбах. Пусть имеется конечное множество юношей, каждый из которых знаком с некоторым подмножеством конечного множества девушек. В каком случае всех юношей можно женить так, чтобы каждый женился на знакомой девушке?

2. Трансверсаль или система различных представителей (СРП). Пусть S = { S_i,..., S_m} — семейство подмножеств конечного множества Е. Подмножества S_k не обязательно различны и могут пересекаться. Системой различных представителей в семействе S (или трансверсалъю в семействе S) называется любое подмножество С = { c_i,..., c_m } из т элементов множества Е, таких, что . В каком случае существует трансверсаль?

Все элементы множества С различны, откуда и происходит название «система различных представителе».

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

а) от каждого комитета имеется в точности один представитель в КК;

б) никто в КК не может быть представителем более одного комитета.

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

3. Совершенное паросочетание Паросочетанием (или независимым множеством рёбер) называется множество рёбер, в котором никакие два ребра не смежны.

Пусть G (V ₁, V ₂, Е)— двудольный граф. Совершенным паросочетанием из V₁ в V₂ называется паросочетание, покрывающее вершины V₁. В каком случае существует совершенное паросочетание из V₁ в V₂?