Главная Промышленная автоматика.

dfnumber[a]= 1 low[a] = 1

di питЬеф] = 2 tow [b] = 1

dfnumber[d\ = 3 low[dl= 1

dfnumberfe] = 4 low[e]= 1


dfnumberfc] = 5 /ои/И- 5

dfnumber[ = 6 tow [f = 5

dfnumber[g] = 7 tow fe] = 5

Pmc. 7. II. Числа dfnumber и low, подсчитанные для графа из рис. 7.8.а

7.5. Паросочетания графов

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


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

Описанную ситуацию можно представить в виде графа, показанного на рис. 7.12, где все вершины разбиты на два множества и V, так, что вершины из множества Fi соответствуют преподавателям, а вершины из множества - учебным курсам. Тот факт, что преподаватель и может вести курс ш, отражается посредством ребра (v, w). Траф, у которого множество вершин распадается на два непересекаюшихся подмноже-



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

Задачу паросочетания мокно сформулировать следующим образом. Есть граф G = (V, Е). Подмножество его ребер, такое что никакие два ребра из этого подмножества не инциденты какой-либо одной вершине из V, называется паросочетанием. Задача определения максимального подмножества таких ребер называется задачей нахождения максимального паросочетания. Ребра, вьщеленные толстыми линиями на рис. 7.12, составляют одно возможное максимальное паросочетание для этого графа. Полным паросочетанием называется паросочетание, в котором участвуют (в качестве концов ребер) все вершины графа. Очевидно, что любое полное паросочетание является таюке максимальным паросочетанием.

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


а. Паросочетание ,

©-©-О-®-0-©

б. Чередующаяся цепь

Рис. 7.13. Паросочетание и чередующаяся цепь

В настоящее время разработаны более эффективные алгоритмы нахождения максимальных паросочетаний. Эти алгоритмы используют в основном метод, известный как "чередующиеся цепи". Пусть М - паросочетание в графе G. Вершину v будем называть парной, если она является концом одного из ребер паросочетания М. Путь, соединяющий две непарные вершины, в котором чередуются ребра, входящие и не входящие в множество М, называется чередующейся (аугментальной) цепью относительно М. Очевидно, что чередующаяся цепь должна быть нечетной длины, начинаться и заканчиваться ребрами, не входящими в множество М. Также ясно, что,



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

Пример 7.9. На рис. 7.13,а показаны граф и паросочетание М, состоящее из ребер (на рисунке они выделены толстыми линиями) (1, 6), (3, 7) и (4, 8). На рис. 7.13,6 представлена чередующаяся цепь относительно М, состоящая из вершин 2, 6, 1, 8, 4, 9. На рис. 7.14 изображено паросочетание (1, 8), (2, 6), (3, 7), (4, 9), которое получено удалением из паросочетания М ребер, входящих в эту чередующуюся цепь, и добавлением новых ребер, также входящих в эту цепь. □


Рис. 7.14. Увеличенное паросочетание

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

Пусть М и N - паросочетания в графе G, причем \М\ < \N\ (здесь \М\ обозначает количество элементов множества М). Для того чтобы показать, что М Л N содержит чередующуюся цепь относительно М, рассмотрим граф G = (V, М Д N), где V - множество концевых вершин ребер, входящих в М JX N. Нетрудно заметить, что каждая связная компонента графа G" формирует простой путь (возможно, цикл), в котором чередуются ребра из М и N. Каждый цикл имеет равное число ребер, принадлежащих М и N, а каждый путь, не являющийся циклом, представляет собой чередующуюся цепь относительно или М, или N, в зависимости от того, ребер какого паросочетания больше в этой цепи. Поскольку \М\ < \N\, то множество М Д Содержит больше ребер из паросочетания N, чем М, и, следовательно, сушествует хотя бы одна чередующаяся цепь относительно М.

Теперь можно описать алгоритм нахождения максимального паросочетания М для графа G = (V, Е).

1. Сначала положим М = 0.

2. Далее ищем чередующуюся цепь Р относительно М, и множество М заменяется на множество М Д Р.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018