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

Предположим, у вас есть набор X (например, соискатели рабочих мест), не пересекающийся с множеством Y (например, рабочие места), и двудольный граф G, соединяющий вершины двух наборов (пары «соискатель — рабочее место», где соискатель обладает достаточной квалификацией для выполнения работы). Паросочетание M в графе G представляет подмножество ребер в G, где никакие два ребра не совпадают (не имеют общей вершины). Наибольшее паросочетание представляет собой то, к которому нельзя добавить больше ребер в графе. Паросочетание максимальной мощности — это наибольшее паросочетание с максимально возможным числом ребер из графа. На рисунке 1 показаны примеры паросочетаний графов.

 

Примеры паросочетания в графе
Рисунок 1. Примеры паросочетания в графе

 

В нашем примере «соискатели — рабочие места» нужно найти паросочетание максимальной мощности, чтобы максимально задействовать соискателей и заполнить рабочие места.

Тестовые данные

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

Используйте программный код листинга 2, чтобы создать большой набор тестовых данных (~1000000 ребер) для тестирования производительности решения.

Если вы используете SQL Server 2016 или более новую версию, обязательно создайте пустой столбчатый индекс columnstore для оптимизации с оператором Window Aggregate пакетного режима:

CREATE NONCLUSTERED COLUMNSTORE
   INDEX idx_cs_dummy
ON dbo.G (x) WHERE x = 'yes' AND x = 'no';

Алгоритм поиска паросочетания максимальной мощности

В алгоритме поиска паросочетания максимальной мощности используется увеличивающийся путь (разновидность чередующегося пути). Напомню, что при паросочетании M в графе G чередующийся путь, или M-чередующийся путь в G, — это путь, состоящий из ребер в G, которые меняются от присутствующих в паросочетании к отсутствующим в паросочетании. Увеличивающийся путь — это чередующийся путь, который начинается и заканчивается на свободных вершинах. На рисунке 2 показаны типы путей.

 

Типы путей
Рисунок 2. Типы путей

 

Ниже приводится алгоритм поиска паросочетания максимальной мощности M в G.

  • Начните с любого паросочетания M в G (пустого или непустого).
  • Повторяйте шаги, пока верно следующее утверждение:

— задать M = M ⊕ P (симметрическая разность M и...

Это не вся статья. Полная версия доступна только подписчикам журнала. Пожалуйста, авторизуйтесь либо оформите подписку.

Поделитесь материалом с коллегами и друзьями

Купить номер с этой статьей в PDF