Презентации лекций / Презентация лекции 15 ДМ 20
.pdf
План лекции
1.Алгоритм поиска в ширину в ориентированном графе
2.Понятие паросочетания
3.Задачао наибольшем паросочетании
4.Задача о назначениях
11
1
2
3
4
12
|
1 |
Цепь графа, ребра которойпоочередновходяти не входятв |
2 |
параосочетание, называетсячередующейсяотносительно |
3 |
|
4 |
|
Цепь |
|
Ребра цепи называются темными, |
из одногоребра |
Вершины графа,инцидентные |
также |
ребрамиз , называются |
|
если они входят в , и светлыми, |
чередующаяся |
насыщенными,вседругие |
если они не входят в |
|
вершины –ненасыщенными |
Пример: |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
= { , , }- |
|
|
|
|
паросочетание |
|
|
||
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
и |
-ненасыщенные |
|
|
|
, , |
, , , -насыщенные |
|
|
|
→ |
-чередующаясяцепь,ребро |
= |
-светлое |
→ → → - чередующаясяцепь,
ребра = и = -светлые, ребро = - темное
Цепи, неявляющиеся чередующимися: |
|
|||
|
→ |
→ |
→ |
|
|
→ |
→ |
→ |
13 |
|
|
|
|
|
Если чередующаяся относительно паросочетания цепь соединяет две различные |
1 |
2 |
|
ненасыщенные вершины, то ее называют увеличивающейотносительно |
3 |
|
4 |
ПОЧЕМУ?
Если увеличивающая относительно цепьсуществует,то можнопостроить паросочетаниес большимчислом ребер,чем .
Для этогонадопоступить так:удалить из всетемныеребраувеличивающей цепи и присоединитьк всеее светлыеребра(ихна одно большетемных).
Получим новоепаросочетаниесчисломреберна единицубольшим.
Пример: |
|
|
|
|
|
|
|
= { , , |
, } |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
- новое |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
= { , , }- |
|
|
|
|
|
паросочетание |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
|
паросочетание |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
→ → → |
- |
|
|
|
|
|
|
|
|
|
|
|
|
увеличивающая |
|
|
|
|
|
|
|
|
|
|
||||
|
относительно |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
цепь |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
14
|
|
1 |
|
Паросочетание -наибольшее |
Вграфенетувеличивающих |
2 |
|
относительно цепей |
3 |
||
|
|||
|
4 |
||
|
|
Стратегияпоисканаибольшегопаросочетания
Начав с произвольного парососчетания , строить последовательность паросочетаний , , ,…, в которой |
= и получается |
|
из |
с помощью описанного изменения вдоль некоторой увеличивающей цепи. В качестве можно взятьпроизвольное ребро графа или, |
|
чтолучше, некотороемаксимальноепарососчетание. |
|
|
Какнайтиувеличивающуюцепьнаграфе?
Поставим в соответствие графу и паросочетанию вспомогательный ориентированный двудольный граф , придав ориентацию «от к » всем ребрам графа, входящим в паросочетание, и «от к » всем остальным ребрам этогографа.
Обозначим через |
и множества ненасыщенных вершин, |
входящих |
|
соответственно, в |
и . Увеличивающей цепи в графе взаимно однозначно |
||
соответствуеториентированнаяцепьсначаломиз |
иконцомиз |
вграфе . |
|
Вграфе увеличивающаяотносительнопаросочетания цепь существуеттогдаитолькотогда,когдавграфе существуеториентированная цепьсначаломввершинеиз иконцомиз
Дляпоискаориентированнойцепииспользуемпоисквширинуизмножества .
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15
1.Построитькакое-либомаксимальноепаросочетание в графе .
2.По графу и паросочетанию построитьграф .
3. Пустьв графе - множество |
|
вершин из и |
|
- множествовершин из , не насыщенныхтекущим |
паросочетанием.Еслихотя бы одноиз этих множеству пусто, то – наибольшеепаросочетание;конец.Иначе выполнитьв графе поиск в ширину из множества .
4. Если врезультатепоискав ширину ни одна из вершин множества не получила метки,то перейти к п.5. Иначе перейти к п.6.
5. Пусть = |
|
|
, |
, |
|
, |
,…, |
|
, |
|
, – множество всехдуг, выходящих из множества .Положить = |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
, |
|
|
,…, |
|
|
. – наибольшеепаросочетание.Конец. |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
6. Пусть – ориентированнаяцепьв графе такая,чтоначалоцепи - вершина из , конеццепи – вершина из
|
(найденнаяв результатепоиска в ширину вп. 4). Изменить граф , заменивв нем каждуюдугу |
, цепи |
|
на дугу , . Перейтик п. 3. |
|
|
|
|
|
|
|
1
2
3
4
16
1.Построитькакое-либомаксимальноепаросочетание в графе
.
2.По графу и паросочетанию построитьграф .
3. Пустьв графе - множество |
|
вершин из и |
|
- множество |
вершин из , не насыщенныхтекущим паросочетанием.Если хотя бы одно из этих множеству пусто, то – наибольшее
паросочетание;конец.Иначе выполнитьв графе поиск в ширину из множества .
4. Если врезультатепоиска в ширину ни однаиз вершин множестване получиламетки, то перейтик п.5. Иначе перейтик п. 6.
5. Пусть = |
|
|
, |
, |
|
, |
,…, |
|
, |
|
, – множество всехдуг, |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
выходящих из множества .Положить = |
|||||||||||||||||
|
|
|
, |
,…, |
|
|
. – наибольшеепаросочетание.Конец. |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
6. Пусть – ориентированнаяцепьвграфе такая,чтоначалоцепи |
|
|
|
- вершина из |
, конеццепи – вершина из (найденнаяв |
результатепоиска в ширину вп. 4). Изменить граф , заменивв |
|
нем каждуюдугу |
, цепи надугу , . Перейтик п. 2. |
1
2
3
Пример:найти наибольшее 4 паросочетаниевграфе:
17
План лекции
1.Алгоритм поиска в ширину в ориентированном графе
2.Понятие паросочетания
3.Задачао наибольшем паросочетании
4.Задача о назначениях
18
1
2
3
4
Совершенноепаросочетаниеминимальноговесаназовемдлякраткости оптимальнымрешением.
19
1
2
3
4
20