Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

Определение паросочетания на графе дано в § 1.1. В обычной жизни паросочетание — это множество различных пар людей, объектов, предметов и т.д. Члены пары связаны между собой общим для них качеством, свойством; иначе говоря, находятся между собой в каком-либо отношении (супружеская пара, пара услуга—клиент и др.).

Приведем примеры задач образования таких пар в сервисе.

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

Данную задачу можно описать двудольным графом. Обозначим множеством вершин х € Vx — покупатели, а множество у е У2 — квартиры. Дуги (х, у) соединяют вершины из Vx и V2 (покупателей с квартирами, которые хотели бы приобрести покупатели). Данная задача задана на отношении потребитель—потребность.

  • 2. Задача о танцах. В танцевальной группе имеется равное число девушек и юношей. Каждый юноша знаком с несколькими девушками, и каждая девушка знакома с несколькими юношами. При каких условиях можно образовать пару из знакомых? Данная задача задана на отношении между потребителями.
  • 3. Администратор гостиницы размещает туристскую группу. Необходимо распределить гостей в возможно меньшем числе номеров так, чтобы в одном номере не находились лица противоположного пола, не связанные родственными узами. Если номера двухместные, то надо составить родственные пары, т.е. необходимо найти паросочетания максимальной мощности. Данная задача также задана на отношении между потребителями.
  • 4. Пусть из множества людей, предметов необходимо выбрать минимальное число, удовлетворяющее сразу двум требованиям. Человека или предмет, удовлетворяющий двум требованиям, на графе можно представить ребром с двумя вершинами, причем ребер много больше, чем вершин. Требуется выбрать минимальное число таких людей или предметов, чтобы были учтены все требования. Например, требуется составить группу разработчиков сложного продукта, каждый из которых обладает определенными знаниями и опытом, необходимым для разработки данного продукта.

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

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

Теорема 3.1. Граф G—(V, Е) является двудольным тогда и только тогда, когда все простые циклы в нем имеют четную длину.

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

Пусть А — конечное подмножество вершин в множестве Vx двудольного графа G= (V, Е), V= Vx u V2. Обозначим v(A) — число вершин в множестве А. На рис. 3.21 показан двудольный граф, в котором V = {а, b, с, d, е}, V2 = {к, т, п, г). Пусть А = {а, b, d}, тогда v(A) = 3.

Двудольный граф

Рис. 3.21. Двудольный граф

Для каждого подмножества А множества Vx можно указать соединенное с ним подмножество У2(Л) множества V2, состоящее из всех тех вершин из V2, которые соединены ребром хотя бы с одной вершиной из А. В нашем примере V2(A) = {к, п}, v( V2(A)) = 2.

Теорема 3.2 [27]. В двудольном графе G=(VX, V2, Е) существует полное паросочетание F, с У2 тогда и только тогда, когда для любого подмножества/! с Vx справедливо неравенство v(A)2(A)).

Применительно к задаче о танцах (см. задачу 2 на с. 137) необходимо и достаточно, чтобы любое подмножество из к юношей, 1 < к< т, где т — общее число юношей, имело вместе не менее к подруг.

Для любого конечного подмножества/! множества F, разность

называется дефицитом подмножества А.

В нашем примере (рис. 3.21) дефицит

т.е. кому-то из группы не хватит пары.

Дефицит графа G определяется так:

Для дефицитов двух множеств Aw В справедливо соотношение [24]

Для конечных подмножеств множества Е, существует верхняя граница дефицитов и, следовательно, некоторый максимальный дефицит а0 = а((7). Множества максимального дефицита, для которых о(А) = о0, называют критическими множествами. Если А и В — критические множества, то их сумма и их пересечение — также критические множества.

Пусть Aw В— такие подмножества К,, что Т огда

Если множество вершин К, конечно и состоит из п вершин, а максимальный дефицит равен а0, то максимальное число вершин, которые могут быть сопоставлены при паросочетании в К2, равно

Таким образом, для того чтобы два множества вершин Е, и V2 двудольного графа G=(V{, V2, Е) можно было сопоставить при паросочетании, необходимо и достаточно, чтобы оба максимальных дефицита (а для Е, и а02 для V2) были равны нулю:

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

Использование максимального потока. Задачу о паросочетании максимальной мощности можно свести к задаче о максимальном потоке [21]. Для этого необходимо:

О ориентировать все ребра в направлении от V{ к Е2;

О ввести вершину источник s и соединить ее дугами с множеством вершин х е Ej;

О ввести вершину сток t и соединить множество вершин у е V2 дугами со стоком;

О пропускную способность каждой из дуг исходного графа принять равной 1 (рис. 3.22).

Преобразование двудольного графа (а) в сеть (б)

Рис. 3.22. Преобразование двудольного графа (а) в сеть (б)

Так как поток в сети целочисленный и дискретный и может увеличиваться или уменьшаться на 1, а по связи не может проходить поток больше пропускной способности, поэтому решение задачи о максимальном потоке будет таким, что в каждой дуге образованной сети будет протекать поток, равный либо 0, либо 1. Следовательно, в каждый узел может входить и выходить только одна связь.

Паросочетанию соответствуют дуги, исходящие из вершин подмножества V1 к вершинам подмножества V2 в исходном графе, по которым протекает единичный поток в сети. Паросочетание в исходном графе, соответствующее максимальному потоку в образованной на его основе сети, должно быть максимальной мощности. В связи с этим максимальное паросочетание можно находить с использованием метода Форда—Фалкерсона. При этом справедлива теорема о целочисленности [17].

Теорема 3.3. Если функция пропускной способности принимает только целые значения, то максимальный поток/, полученный методом Форда—Фалкерсона, обладает тем свойством, что значение потока является целочисленным.

Следствие. Мощность максимального паросочетания Мв двудольном графе С равна величине максимального потока/в соответствующей транспортной сети N.

Согласно теореме 3.3, в рассматриваемом двудольном графе (рис. 3.22) не существует полного паросочетания, так как v( С|) > v( V2). Дефицит графа a( V}) = v( V}) — v( V2) = 5 — 4 = 1, максимальная мощность паросочетания a](G)=4.

Чередующиеся цепи. Существуют более быстрые алгоритмы поиска паросочетаний максимальной мощности, основанные на понятии чередующихся цепей.

Пусть задано паросочетание М в двудольном графе G=(VX, V2, Е). Чередующейся (альтернирующей) цепью называют простую цепь, в которой из любых двух смежных ребер одно принадлежит паросо- четанию М, а другое не принадлежит ему.

Чередующаяся цепь в двудольном (а) и изоморфном плоском (б) графах

Рис. 3.23. Чередующаяся цепь в двудольном (а) и изоморфном плоском (б) графах

На рис. 3.23 простая цепь показана утолщенными сплошными и штриховыми линиями на двудольном графе и изоморфном ему плоском графе. Как видно, одна вершина ребра находится в множестве Vx = {a, b, е}, а другая в множестве V2 = {т, п,р, г}. Если М= {(а, т),

(Ь, р)}, то М = {(т, Ь,), (р, Щ- Входящие в паросочетание М ребра изображены сплошными линиями, а не входящие — штриховыми.

Вершина называется открытой, если она не инцидентна ни одному из ребер, входящих в это паросочетание. Вершина называется вершиной паросочетания, если она инцидентна некоторому входящему в паросочетание ребру. Так, на рис. 3.23 вершины а, Ь, т, р являются вершинами паросочетания, а вершины с, d, е,п,г— открытыми.

Чередующаяся цепь Р называется увеличивающей (аугменталь- ной), если ее первая и последняя вершины являются открытыми. На рис. 3.24 увеличивающая цепь показана штриховыми и сплошными утолщенными линиями. Первое и последнее ребро увеличивающей цепи не принадлежат паросочетанию, т.е. вершины d, г — открытые. Если вместо ребер, принадлежащих исходному паросочетанию (сплошные линии), выбрать в качестве паросочетания ребра увеличивающей цепи, отмеченные штриховыми линиями, то новое паросочетание будет иметь на одно ребро больше, т.е. новое паросочетание представляет собой дизъюнктивную сумму (симметрическую разность) М® Рмножеств ребер Ми Р.

Увеличивающая цепь в двудольном (а) и изоморфном плоском (б) графах

Рис. 3.24. Увеличивающая цепь в двудольном (а) и изоморфном плоском (б) графах

Как видно на рис. 3.24, Р= {(г, а), (а, т), (т, b), (b,p), , d)}, исходное паросочетание содержит 2 ребра М0 = {(а, т), (b, р)}, а новое 3 ребра М{ = М © Р= {(г, а), (т, b), (/?, ?/)}, |Л/)| = |М© = М + 1.

Вершины а, /?, d, т, р, г являются вершинами паросочетания Мь а вершины с,е,п — открытые вершины. Однако данное паросочетание не является максимальным согласно теореме [21, 24].

Паросочетание максимальной мощности

Рис. 3.25. Паросочетание максимальной мощности: а — максимальное паросочетание в двудольном графе; б — максимальная чередующаяся цепь в изоморфном плоском графе

Теорема 3.4. Паросочетание М максимально тогда и только тогда, когда для него не может быть найдена увеличивающая цепь.

Данная теорема служит основой для алгоритма поиска паросочетания максимальной мощности. Алгоритм должен осуществлять поиск увеличивающих по отношению к данному паросочета- нию цепей. Подробное описание алгоритма дано в [21].

На рис. 3.25 найдено максимальное паросочетание мощности а.]((/)=4

Вершина d открытая.

Задача с несколькими отношениями (/г-дольный граф)

Пусть в организацию сервиса обратилось несколько клиентов. Каждый из них выдвигает определенные требования к средству удовлетворения потребности (товару). Например, клиент имеет свои требования к квартире, которую хочет купить. Она, скажем, должна быть

3-комнатной, с большой кухней, лоджией, находиться в определенном районе и др. На основании этих требований можно составить двудольный граф.

Трехдольный граф на отношениях клиент—свойства—товар

Рис. 3.26. Трехдольный граф на отношениях клиент—свойства—товар

Организация сервиса располагает средствами удовлетворения потребностей (товар), которые обладают рядом свойств. Например, риелторская фирма имеет несколько двухкомнатных, трехкомнатных квартир, имеющих различные удобства и расположенных в разных районах города. Эти данные также позволяют составить двудольный граф. Объединив соответствующие свойства средств удовлетворения потребностей с требованиями клиента, можно получить результирующий граф (рис. 3.26).

Данную задачу невозможно решить методом поиска максимального потока на графе. Однако на основании полученного графа можно сформировать двудольный граф, первое множество которого составляют клиенты, а второе — товары. Для установления связи между элементами множества клиентов и множеств товаров используются следующие правила:

  • 1) связь устанавливается тогда, когда имеется хотя бы один путь от элемента множества клиентов к элементу множества товаров. В этом случае клиент будет доволен при выполнении любого из требований к товару;
  • 2) для элементов множества товаров необходимо существование всех путей, т.е. выполнение требований со стороны элементов множества товаров. Тогда связь устанавливается от элемента множества клиентов к множеству товаров при наличии путей, проходящих через все связи с элементом множества товаров, т.е. товар имеет неделимый набор свойств, а клиента удовлетворяют все из них;
  • 3) для элементов множества клиентов необходимо существование всех путей, т.е. выполнение требований со стороны элементов множества клиентов. Тогда связь устанавливается от элемента множества клиентов к множеству товаров при наличии путей, проходящих через все связи с элементом множества клиентов. Например, обязательное выполнение требований клиента к товару.
Двудольный граф, образованный из трехдольного

Рис. 3.27. Двудольный граф, образованный из трехдольного

На рис. 3.27 показан двудольный граф, образованный из трехдольного в соответствии с правилом 2. Для задачи приобретения квартиры это означает, что квартира имеет свойства, которые нельзя разделить, а клиента может устроить частичное выполнение своих требований.

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

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

Присвоим каждой дуге графа вес р(х, у) > 0, равный стоимости квартиры. Для максимизации стоимости сделки необходимо найти паросочетания с максимальным весом:

Паросочетания с минимальным весом. Задача. Служба знакомств организует для каждого клиента встречу с одним из подходящих ему претендентов для знакомства. С организацией каждой встречи связаны определенные затраты. Служба знакомств должна выполнить обязательства перед клиентом, и при этом она заинтересована в минимизации затрат.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>