Презентации лекций / Презентация лекции 15 ДМ 20

				1
	Матрицавесов		Матрицаразмера × ,вкоторой	2
				3
			элемент, стоящийнапересечении -ойстрокии -огостолбца,
	полного двудольного
			равенвесуребра,соединяющего -уювершинупервойдолис -ой	4
	графа
			вершинойвторойдоли

Свойствозадачионазначениях:

Множество оптимальных решений не изменится,				Множество оптимальных решений не изменится,
если веса всех ребер, инцидентных какой-либо				если все элементы строки или столбца матрицы
вершине, увеличить (уменьшить) на одно и то же				весов, соответствующих какой-либо вершине,
число.				увеличить (уменьшить)наодноитожечисло.

Пусть ( , ) –вес ребра .

(1)Будем считать, что ( , ) ≥ 0 для каждого ребра графа (из свойства следует, что случай, когда имеются ребраотрицательноговеса,можносвестикэтому).

(2)Решение задачи о назначениях начинаем с перехода к взвешенному графу, у которого каждой вершине инцидентно ребро нулевого веса и веса всех ребер неотрицательны. Для этого изменим матрицу весов графа следующим образом: сначала вычтем из всех элементов каждой строки минимальный элемент этой строки, а затем тожесамоепроделываемсостолбцами(изсвойстваследует,чтоэтапроцедуранеменяетоптимальногорешения).

21

1

2

3

4

Будемсчитать,чток графу применяетсяоперация

( , , ),если:

(1)сначалаиз весакаждогоребра,инцидентного вершинеиз множества ,вычитается ,

(2)затемквесукаждогоребра,инцидентного вершинеиз множества ,прибавляется .

Изменениематрицывесовприоперация , , :

(1) сначала из всех элементов строк, соответствующих вершинаммножества ,вычитаем ,

(2)затем ко всем элементам столбцов, соответствующихвершинамиз , прибавляем .

Пусть , - двудольный граф с долями , и - паросочетание в нем.

Будем обозначать через - вспомогательный ориентированный двудольный граф, полученный из графа путем ориентаций «от к » всех ребрам паросочетания и «от к » всем остальным ребрам этого графа.

22

1.Построитьграф , ,вкотором = , = { : ,

= }.

2.Найтивграфе максимальноепаросочетание.Пусть и множестваненасыщенныхпаросочетанием вершин,входящих соответственно,вдоли и.

3.Если = = ,токонец( -оптимальноерешениезадачи).Иначепостроитьграф.

4.Применитькграфу поисквширинуизмножества .Еслинайденаориентированнаяцепь из в , , ,то перейтикп.5.Иначеперейтикп.7.

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

6.Если = = ,токонец(множествовсехтакихребер ,что , и( ,) -дугаграфа,составляетсовершенное паросочетаниеминимальноговесависходномграфе).Иначеперейтикп.4.

7.Пусть′ и′ - подмножествавершинграфа ,получившихпометкиврезультатепоискавширину(вп.4).Средиребер графа ,имеющихвид ,что , \ ′ найтиреброминимальноговеса.Пусть –весэтогоребра.

8.Модифицироватьвесареберграфа,применивкнемуоперацию( , ,).

9.Модифицироватьграф,добавивкнемувсетакиедуги( ,),что , \ ,	,	= ,иудаливвсетакиедуги( ,), что
\ , .Перейтикп.4.

1

2

3

4

23

1.Построитьграф , ,вкотором = , = { : ,

= }.

2.Найтивграфе максимальноепаросочетание.Пусть и множества ненасыщенныхпаросочетанием вершин,входящихсоответственно,вдоли и.

3.Если = = ,токонец( -оптимальноерешениезадачи).Иначепостроитьграф.

4.Применитькграфу поисквширинуизмножества .Еслинайденаориентированная цепь из в , , ,топерейтикп.5.Иначеперейтикп.7.

5.Преобразоватьграф ,замениввнемкаждуюдугуцепи наобратную.Темсамым

получитьновоепаросочетание вграфе имножества и –подмножествавершини графа,ненасыщенныхновымпаросочетанием.

6.Если = = ,токонец(множествовсехтакихребер ,что , и( ,) -

дугаграфа,составляетсовершенноепаросочетаниеминимальноговесависходномграфе ).Иначеперейтикп.4.

7.Пусть′ и′ - подмножествавершинграфа ,получившихпометкив результатепоискавширину(вп.4).Средиреберграфа ,имеющихвид ,что , \ ′ найтиреброминимальноговеса.Пусть –весэтогоребра.

8.Модифицироватьвесареберграфа,применивкнемуоперацию( , ,).

9.Модифицироватьграф,добавивкнемувсетакиедуги( ,),что , \ ,

,	= ,иудаливвсетакиедуги( ,), что \ , . Перейтикп.4.

	1
	2
	3
Пример:	4

Двудольный граф задан матрицей весов.

2	6	4	6
6	3	4	4
8	3	2	4
3	5	8	7

Найти паросочетание минимальноговеса.

24