Home

1

std::pair first - узел ИЗ которого идет ребро second - узел В который идет ребро

2

Конструктор класса Трансверсали является функцией поиска трансверсали для заданных множеств из элементов T. Этапы выполнения задачи:

1. Инициализация:
   1. Объединение множеств.
   2. Построение графа
      1. Построение внутренних ребер - принадлежность элемента к одному из подмножеств
      2. Построение псевдоребер от начального узла прохода и конечного узла (на самом деле они не очень-то и нужны - можно начинать сразу с левого узла)
2. Проход по графу в соответствии с алгоритмом КИО и удаление/смена направлений ребер
   1. Будут подпункты
3. Преобразование оставшихся в графе ребер ориентированных справо налево в выходные данные.

3

---

Задание: Построение трансверсали максимальной мощности для произвольного набора частично пересекающихся подмножеств.

---

4

Двудольный граф реализуем как множество направленных ребер.

---

Множества реализуем как список.

5

Объединение всех подмножеств является множеством Е. Левой долей графа являются элементы множества Е. Правой долей - подмножества S1, S2 и тд, то есть исходные множества. Ребрами ориентированного графа являются элементы подмножеств. Причем элементы подмножества Ж а, б, в - ребра от элементов всего множества к узлу Ж.

6

При решении задачи нам понадобятся алгоритм КИО-Школы "Максимальных паросочетаний" http://kioschool.eltech.ru/manipulators/user_show?id=5&tab=description

7

Что такое Транверсаль? https://ru.wikipedia.org/wiki/Трансверсаль Для проверки можно ли вообще построить Трансверсаль может понадобиться это: https://ru.wikipedia.org/wiki/Теорема_Холла