Дискретно-непрерывная математика (стр. 77 )

В более сложных графах необходимо находить и по­следовательно удалять несколько венгерских деревьев Т1, Т2, ..., и, следовательно, рассматривать несколько оставшихся подграфов G1, G2, ..., прежде чем будет получен граф, в котором мы обнаружим либо совершен­ное паросочетание, либо венгерское дерево, содержащее все оставшиеся верщины. Восстанавливая последователь­но венгерские деревья в обратном порядке и находя максимальное паросочетание для каждого вновь добав­ленного дерева, получаем максимальное паросочетание для всего графа.

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

Рис. 5.33.

По отноше­нию к растущему дереву и ребрам паросочетания, пока­занным на рис. 5.32, а, цикл С, Р, Q, Т, N является со­цветием. После его стягивания получим рис. 5.33, b. По отношению к новому растущему дереву (рис. 5.33, b) оставшийся граф является соцветием, которое можно стянуть в одну псевдо-псевдовершину, показанную на рис. 5.33, с. Растягивая соцветия в обратном порядке и восстанавливая паросочетания, удаленные при стягива­нии, получим максимальное паросочетание, показанное на рис. 5.33, d. Предположим, что вершина С в нашем исходном примере фактически была вышеупомянутой псевдо-псевдовершиной (т. е. что процедурам, показан­ным на рис. 5.32, предшествовало двойное стягивание). Тогда максимальное паросочетание для всего графа бу­дет иметь вид рис. 5.34.

Рис. 5.34.

Упражнение 21. Найти максимальное паросочетание для гра­фов, показанных на рис. 5.15 и 5.17.

Итак, в предыдущих разделах мы ввели терминоло­гию и предварительные сведения, необходимые для опи­сания алгоритма, и проиллюстрировали его работу на небольшом частном при­мере. Опишем теперь ал­горитм в общем виде.

Описание алго­ритма. Пусть G= (V,E) обозначает граф, для ко­торого требуется найти максимальное паросоче­тание, М — исходное па­росочетание в G (возмож­но, пустое множество), a S — множество ребер, первоначально пустое, ко­торое будет последовательно расширяться добавлением определенных ребер. Если некоторые вершины G не по­крыты относительно М, то выберем одну из них в каче­стве начала растущего дерева Т. Рассмотрим в любом порядке ребра, которые не входят в Т, но инцидентны внешним вершинам Т. Если Т — цветущее дерево относи­тельно некоторого ребра, то стянем соответствующее со­цветие в одну псевдовершину, зафиксируем стянутое со­цветие и будем считать псевдовершину внешней верши­ной Т. Если Т может быть увеличено присоединением двух ребер и вершин, как описывалось ранее, то увели­чим его. Если Т является расширяющимся по отношению к некоторому ребру, то увеличим М, используя соответ­ствующее чередующееся расширение. (В этом случае Т не является более растущим деревом. Образуем новое растущее дерево, выбирая, если она существует, непо­крытую вершину относительно М.) Если текущий ва­риант растущего дерева Т оказывается венгерским и если не все вершины графа принадлежат Т, то временно удалим все вершины Т и все ребра, которые инцидентны этим вершинам. Оставшийся граф обозначим G1 и по­вторим описанный процесс для этого графа.

В конечном счете, после удаления конечного числа венгерских деревьев Т1, Т2, …, Тп и рассмотрения со­ответствующих оставшихся графов G1, G2, ..., Gn ока­зывается, что либо (1) Gn и есть пустой граф, либо (2) М содержит совершенное паросочетание для Gn. После

этого восстанавливаем поочередно Тп , Тп-1,.....,Т1 и их

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

Пусть G=(V, E) — граф, каждой из вершин v кото­рого поставлено в соответствие неотрицательное целое число d(v). Подграфом с ограниченными степенями графа G считается подграф G'=(V, F) такой, что сте­пень каждой его вершины v не больше d(v). Максималь­ным подграфом, с ограниченными степенями считается подграф, имеющий наибольшее число ребер.

Легко видеть, что задача о максимальном паросочетании соответствует частному случаю, когда d(v) = 1 для каждой вершины v.

Эдмондс непосредственно обобщил приведенный выше алгоритм на решение общей задачи нахождения макси­мального подграфа с ограниченными степенями для произвольных неотрицательных d(v). Он также рассмот­рел еще одно важное обобщение задачи о максимальном паросочетании, когда требуется найти паросочетание с максимальным общим весом при условии, что каждому ребру графа поставлено в соответствие число, называе­мое «весом» (исходная задача о паросочетании соответ­ствует случаю, когда все веса равны единице). Алгоритм решения этой задачи можно объединить с алгорит­мом нахождения кратчайших путей и решить на их основе «задачу китайского почтальона», впервые предложенную Кваном. Эта задача сводится к на­хождению замкнутой цепи, в которую каждое ребро связного графа входит по крайней мере один раз и ко­торая имеет минимальный общий вес. (Другими слова­ми, задача состоит в том, чтобы получить уникурсальный граф за счет дублирования ребер при минимальном дополнительном весе.)

ТЕХНИЧЕСКИЕ ПРИЛОЖЕНИЯ

5.15. Анализ технических систем

Покажем, как можно использовать соответственным образом построенные ориентированные графы для по­лучения существенной информации о поведении реаль­ных технических систем на основе информации, харак­теризующей их составные части при заданном способе связи этих частей. Излагаемый ниже метод, разработан­ный в числе прочих Трентом, наиболее широко ис­пользуется для анализа электрических цепей. Однако его можно также применять и к любым другим систе­мам, в которых происходит преобразование энергии, на­пример к механическим, устройствам с поступательными или вращательными движениями, или к гидравлическим системам. Кроме «чистых» систем (т. е. использующих только один вид энергии) этот метод может быть распространен на «смешанные» системы, в которых различ­ные элементы работают с различными видами энергии и связаны между собой через соответствующие устройства согласования.

Рассмотрим набор из т двухполюсников, которые образуют элементы системы Е1, ..., Ет. Пусть клеммы двухполюсников соединены некоторым образом в п узлах Р1, ..., Рп. Примером такой системы может служить набор сопротивлений, конденсаторов, индуктивностей и источников напряжения (в простейшем случае — бата­реи, в более сложных случаях — источники переменного напряжения). Предположим, что каждый отдельный элемент системы можно адекватно охарактеризовать из­вестным уравнением, связывающим две основные пере­менные: ток xi и напряжение уi элемента Ei. Считается, что xi и уi измеряются в определенном направлении. Выбор переменных и использование терминов «ток» и «напряжение» будут скоро понятны.

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

где t обозначает время. Активный элемент, или источ­ник, характеризуется уравнением, выражающим одну из основных переменных как функцию времени (это может быть и константа). Например, уi=f(t) характеризует источник напряжения.

Допустим теперь, что каждому элементу Е соответ­ствует дуга аi, а каждому узлу Рj — вершина vj. Если конечные точки дуг взяты в качестве соответствующих» узлов, то полученный ориентированный граф дает удоб­ную характеристику структуры соответствующей реаль­ной технической системы. Важное для нашего рассмотрения свойство токов состоит в том, что в каждой вер­шине их поведение подчинено так называемому правилу вершин. Оно состоит в следующем.

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

Под алгебраической суммой понимается следующее: каждый ток добавляется или вычитается в зависимости от того, является ли соответствующая дуга положитель­но или отрицательно инцидентной рассматриваемой вершиной. На рис. 5.35 правило выполняется, например, в v1, так как (4)—(7)— (-3)=0.

Pис. 5.35

Нетрудно видеть, что оно выполняется также и в других вершинах. В тео­рии электрических цепей это правило называется зако­ном Кирхгофа для токов.

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

Напряжения также удовлетворяют следующему ос­новному так называемому циклическому правилу.

Циклическое правило. Алгебраическая сумма напряжений, соответствующих дугам любого элементар­ного цикла, равна нулю.

В этом случае предполагается, что циклу задается некоторая ориентация (в любом из направлений) и каж­дое напряжение добавляется или вычитается в зависи­мости от того, совпадает или не совпадает направление соответствующей дуги с выбранной ориентацией цикла. На рис. 5.36 это правило выполняется, например, для ориентированного элементарного цикла С, так как