Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

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

Лекция



Привет, сегодня поговорим про поиск максимального паросочетания, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое поиск максимального паросочетания , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Пусть дан неориентированный граф G = (V, Е). Паросочетанием (matching) называется подмножество ребер М є Е, такое что для всех вершин v е V в М содержится не более одного ребра, инцидентного v.

Максимальным паросочетанием называется паросочетание максимальной мощности, т.е. такое паросочетание М, что для любого паросочетания М': |М| >= |М'|.

Ограничимся рассмотрением задачи поиска максимальных паросочетаний в двудольных графах. Мы предполагаем, что множество вершин можно разбить на два подмножества V = L U R, где L и R не пересекаются, и все ребра из Е проходят между L и R. Далее мы предполагаем, что каждая вершина из V имеет по крайней мере одно инцидентное ребро.

С помощью метода Форда-Фалкерсона можно найти максимальное паросочетание в неориентированном двудольном графе G = (V,E) за время, полиномиально зависящее от |V| и |Е|. Определим для заданного двудольного графа G соответствующую транспортную сеть G' = (V', Е') следующим образом. Возьмем в качестве источника s и стока t новые вершины, не входящие в V, и пусть V' = V U {s, t}. Если разбиение вершин в графе G задано как V = L U R, ориентированными ребрами G будут ребра Е, направленные из L в R, а также |V| новых ребер. Чтобы завершить построение, присвоим каждому ребру Е' единичную пропускную способность.

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

Формальное описание     [вверх]

Matching(G)
1. Об этом говорит сайт https://intellect.icu  . Проверить, является ли граф двудольным.
2. Если граф двудольный, то перейти к пункт 2.1., иначе 
   вывести сообщение о том, что граф недвудольный и завершить работу.
   2.1. Разбить граф на 2 части.
   2.2. Создать 2 вершини, связать стартовую со своеми вершинами 
        из первой части графа, конечную - со всеми вершинами 
        из второй части графа.
   2.3. Модернизировать полученную сеть, изменяя пропускную способность 
        в обратну сторону графа на отрицательные значения.
   2.4. Найти максимальный поток с помощью алгоритма Форда-Фалкерсона.
   2.5. Считать ребра между двумя частями графа 
        с потоком равным 1 ребрами паросочитаний.
   2.6. Подсчитать количество ребер в паросочитании.

Оценка сложности     [вверх]

Поскольку любое паросочетание в двудольном графе имеет мощность не более min(L, R) = О (V), величина максимального потока в G составляет О (V). Поэтому максимальное паросочетание в двудольном графе можно найти за время O(V*E') = O(V*E), поскольку |Е'| = o(Е).

Пример     [вверх]

Рассмотрим схему сведения двудольного графа к некоторой сети. На рисунке показан исходный двудольный граф G. 
Поиск максимального паросочетания
Построим сеть S(G) с источником s и стоком t следующим образом:
* источник s соединим дугами с вершинами из множества X;
* вершины из множества Y соединим дугами со стоком t;
* направление на ребрах исходного графа будет от вершин из X к вершинам из Y;
* пропускная способность всех дуг C[i,j] = 1.
Найдем максимальный поток из s в t для построенной сети. Он существует. Насыщенные дуги потока (они выделены «жирными» линиями на рисунке) соответствуют ребрам наибольшего паросочетания исходного графа. Найденное наибольшее паросочетание не единственное.


Поиск максимального паросочетания
Найдем в исходном графе (слева) две доли и запомним их. Таким образом мы получим двудольный граф.

Поиск максимального паросочетания
Добавим вершину-исток и вершину-сток. Соеденим исток и сток с разными долями графа.
Для всех ребер пропускная способность равна 1. Найдем максимальный поток из истока в сток.

Поиск максимального паросочетания
Ребра первоначального графа, через которые поток равен 1, будут ребрами максимального паросочетания. В данном случае максимальное паросочетание состоит из 2 ребер: (0;1) и (2;4).


Поиск максимального паросочетания
Найдем в исходном графе (слева) две доли и запомним их. Таким образом мы получим двудольный граф.

Поиск максимального паросочетания
Добавим вершину-исток и вершину-сток. Соеденим исток и сток с разными долями графа.
Для всех ребер установим пропускную способность равную 1. Найдем максимальный поток из истока в сток.

Поиск максимального паросочетания
Ребра первоначального графа, через которые поток равен 1, будут ребрами максимального паросочетания. В данном случае максимальное паросочетание состоит из 2 ребер: (0;1) и (2;4).

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

Из статьи мы узнали кратко, но содержательно про поиск максимального паросочетания
создано: 2014-10-13
обновлено: 2021-03-13
132869



Рейтиг 3 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов