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

причем

Известно, что U(n) = L(n) для 1<п≤11, а также для п=20 или 21. Оптимальность процедуры в общем случае не доказана.

Упражнение 33. Пусть истинная ранжировка элементов

А,.., О имеет вид

Начав со сравнения А и В, проведите ранжирования элементов мето­дом Штейигауза. Новые элементы вводите в порядке С, D, . . ., N, О. (При наличии двух средних элементов выбирайте левый.) Найдите общее число требуемых сравнений и сравните его с М (15) и L (15).

Задачу ранжирования можно рассмотреть с точки зре­ния теории графов. Пусть элементам ранжируемого мно­жества соответствуют вершины некоторого ориентирован­ного графа. В начальный момент дуги в графе отсут­ствуют. После каждого сравнения в граф вводится дуга, идущая из вершины с более высоким рангом в вершину с меньшим рангом. (Предполагается, что благодаря транзитивности отношения упорядочения, кроме дуг, воз­никающих непосредственно в результате сравнений, в графе имеются дополнительные дуги. Последние не обязательно нужно изображать на графе.) Цель состоит в том, чтобы ввести такое количество дуг, при котором в графе возникает путь, проходящий через все вершины (т. е. гамильтонов путь). Порядок появления вершин в гамильтоновом пути дает нужную ранжировку элемен­тов. Вернемся к примеру рис. 8.75. После ранжировки sl,…, sl5, показанной горизонтальными дугами на рис. 5.77, ранг sl6 определяется добавлением дуг а, b, с и d (в на­званной последовательности).

Рис. 5.77.

Последовательность вер­шин 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 11, 12, 13, 14, 15 опре­деляет гамнльтонов путь. Хорошей процедурой ранжи­рования будет та, которая позволит найти гамильтонов путь при минимальном числе вводимых в граф дуг.

6. ПОТОКИ В СЕТЯХ

6.1. Введение

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

6.2. Основная терминология

При изучении потоков достаточно ограничиться рас­смотрением ориентированных связных графов, не имею­щих петель. Такие графы будут называться сетями. (Потоки в несвязных графах могут изучаться при отдельном рассмотрении каждой компоненты, a поток в петле не влияет на распределение потока между вершинами. Таким образом, класс графов, называемых сетями, является достаточно представительным для наших целей.) Чтобы отличить сеть от обычного ориен­тированного графа, мы будем обозначать ее через N, а не через D. Пусть задана сеть N(V, А). Потоком в сети N называется целочисленная функция φ, опре­деленная на А. Целое число φ(а) называется потоком по дуге а. Более точно, если a(v, w), то говорят, что поток направлен от v к w при φ(а)≥ 0 и от w к v при φ(а) ≤0.

Большинство идей и результатов, которые будут изложены ниже, становятся особенно очевидными, если рассмотреть геометрическую реализацию сети и интер­претировать [φ(a)] как постоянную скорость потока однородного вещества через а. Направление потока определяется знаком φ(a) с учетом приведенного выше условия.

Вершины сети N обычно классифицируются по их воздействию на поток φ (создают, поглощают или со­храняют поток). Чтобы формализовать классификацию, обозначим через v→ V множество дуг, для которых v является начальной вершиной, а через V→v—миожесто дуг, для которых v является конечной вер­шиной. Тогда целое число Q(v, φ), определяемое со­отношением

называется чистым потоком из v относительно φ. Будем далее писать просто Q(v), если наличие φ очевидно из контекста. Если φ(а)≥0 в каждой дуге, то первая сум­ма есть просто общий поток, вытекающий из вершины v, а вторая—общин поток, вытекающий в вершину v. Если в некоторых дугах потоки отрицательны, то выделен­ные суммы не имеют названной интерпретации, но их разность по-прежнему представляет собой чистый поток из вершины v. Например, на рис. 6.1 множество v→V состоит из дуг {a1a2}, множество V→v — из дуг {а3а4} и

Рис. 6.1.

Заметим, что чистый поток из вершины не изменится, если мы изменим направление дуги и знак ее потока па противоположные. Следовательно, все потоки через дуги можно сделать неотрицательными, не изменяя чи­стого потока в любой вершине. Однако здесь более полезно оставить направление дуг неизменным и допу­стить в определенных случа­ях отрицательные потоки. Сгруппируем теперь вер­шины сети N в множества V+, V- и V0 следующим об­разом:

Элементы множеств V+, V- и V0 называются источника­ми, стоками и промежуточными вершинами соответствен­но. Интуитивно можно считать, что эти вершины соответ­ственно создают, потребляют и сохраняют поток.

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

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

Рис. 6.2.

Если в сети имеется единственный источник vi и единствен­ный сток vj , то рассматривается поток из vi в vj, а ве­личина Q(vi) или —Q(vj) называется величиной потока. (Для удобства эта же терминология распространяется на случай потоков нулевой величины, для которых Q(v)=0 во всех вершинах.)

Любой поток в сети можно преобразовать в поток, который имеет только один источник и один сток, увеличив количество вершин в сети. Например, доба­вим новую вершину w1 и дуги bi (w1, vi), ведущие от w1, к каж­дому источнику сети. Этим дугам припишем поток

φ(bi)=Q(vi).

Аналогичным образом, добавим вторую вершину w2 и дуги

cj(vj, w2), которые ведут от каждого стока к вершине w2 и имеют поток

φ (cj)=-Q(vj).

В результате получим сеть с одним источником и одним стоком. Рис. 6.3 показывает расширение сети, требуемое для приведения потока в сети рис. 6.2 к стандартной форме. Результирующий поток из w1 в w2 имеет вели­чину 11.

Рис. 6.3.

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

6.3. Отношения между потоками и операции над ними

Пусть φ1 и φ2 — потоки в одной и той же сети N=(V, А), и пусть р — целое число. Тогда для каждой дуги а А потоки φ1+ φ 2, φ1— φ2 и pφ определяются с помощью следующих соотношений:

Легко видеть, что

Отсюда следует, что если φ1 и φ2 — потоки из v в w, имеющие величины k1 и k2 соответственно, то φ1 +φ2 также является потоком из v в w и имеет величину k1+k2. Аналогично, φ1 — φ 2 есть поток, имеющий вели­чину |k1—k2| и направленный от v к w, если k1≥k2, или от w к v, если k1≤k2. (Поток величины нуль можно считать направленным как от v к w, так и от w к v.) И наконец, поток pφ имеет величину |pk1| и направлен от v к w, если р≥0, и от w к v, если р≤0.