Методические указания к выполнению расчетных работ по теории графов и сетей, страница 11

Таким образом, мы можем удалить произвольное уравнение из системы (8.2) и такой переход будет равносильным. Остается выяснить,будет ли оставшаяся система линейно независимой. Об этом утвердительно говорит~Теорема 8.1. Пусть G  (V , X ) – связный граф и D  (V , X ) – орграф, полученныйиз G введением ориентации на ребрах (т.е. каждое ребро {v, w} X превращаем либо вдугу (v, w), либо в дугу (w, v) ). Тогда ранг матрицы B(D) равен n(G)  1.Замечание 8.2. Утверждение теоремы 8.1 остается справедливым и в случае, когдаG – связный мультиграф.Из этой теоремы следует, что после вычеркивания любой строки из B(D) получаемматрицу, ранг которой совпадает с числом строк. Но тогда после удаления из системы(8.2) любого уравнения оставшаяся система уравнений оказывается линейно независимой.Подсчитаем общее число линейно независимых уравнений Кирхгофа для токов инапряжений для некоторой электрической цепи с m элементами (двухполюсными) и содержащей n узлов.

Этой цепи соответствует некоторый граф G , ассоциированный с ней,содержащий n вершин и m ребер. Будем считать, что электрическая цепь является неделимой, т.е. граф G является связным. Тогда этой цепи можно поставить в соответствие (G)  m  n  1 линейно независимых уравнений Кирхгофа для напряжений и n  1 линейно независимых уравнений Кирхгофа для токов, т.е систему из  (G)  n  1 49 m  n  1  n  1  m линейно независимых уравнений относительно 2m неизвестных(для каждого из m элементов неизвестны величина тока по этому элементу и напряжениемежду концами этого элемента).

Недостающими m уравнениями являются уравнениясвязи между величиной тока и напряжением для каждого элемента цепи. Простейшим изуравнений связи является закон Ома: u  ir для случая, когда элементом цепи являетсясопротивление величины r.Разбор типового варианта. Пусть каждому ребру неориентированного графа G ,изображенного на рис. 8.7, соответствует некоторый элемент электрической цепи. Составить линейно независимые системы уравнений Кирхгофа для токов и напряжений. Пустьпервому и пятому ребру соответствуют источники тока с ЭДС E1 и E2 (полярность выбирается произвольно), а остальные элементы являются сопротивлениями. Используя законОма и предполагая внутренние сопротивления источников тока равными нулю, получитьобщую систему уравнений для токов.Рис. 8.7Решение.

Выделим произвольным образом остовное дерево графа G (например,используя алгоритм 4.1). Для графа G , изображенного на рис. 8.7, одним из возможныхостовных деревьев является дерево, изображенное на рис. 8.8 (пунктирными линиямиизображены удаленные из G ребра).Рис. 8.8Добавляя любое из ребер, не вошедших в остовное дерево графа G (изображенныхна рис. 8.2 пунктирными линиями), мы получим граф с некоторым простым циклом (см.тему 4, свойство (5) деревьев). Всего в остовное дерево не вошли  (G)  m(G)  n(G)  1ребер (для графа, изображенного на рис. 8.7,  (G)  9  6  1  4 ), а поэтому можем получить таким образом  (G)  4 простых циклов.

Эти циклы различны в том смысле что каждый из них проходит через ребро (то самое, которое мы добавляли для выделения данного цикла), через которое не проходит ни один другой цикл. Они образуют цикловой базисграфа G.50Для графа G , изображенного на рис.

8.7, в цикловой базис войдут циклы:1  1 ( x2 )  x1 x2 x6 x8 , 2  2 ( x3 )  x3 x4 x9 x6 , 3  3 ( x5 )  x5 x6 x8 4  4 ( x7 )  x6 x7 x9 .Введем произвольным образом ориентацию на ребрах графа G (т.е. каждое ребро{v, w} превращаем либо в дугу (v, w), либо в ( w, v) ). В результате каждое ребро x j превра~тится в дугу ~x j и соответственно множество ребер X в множество дуг X , а сам граф~G  (V , X ) в орграф D  (V , X ). Для графа G , изображенного на рис.

8.7, в результате~введения ориентации на его ребрах получаем, например, орграф D  (V , X ), изображенный на рис. 8.9.Рис. 8.9Для графа G , изображенного на рис. 8.7, с выделенным ранее цикловым базисом{1 , 2 , 3 , 4 } и выбранной ориентацией ребер, соответствующей орграфу D, изобра-женному на рис. 8.9, цикломатическая матрица имеет видC (G) x1x2x3x4x51-112030x6x7x8x900010-100110-100-1000-110-10. 4 0 0 0 0 0 -1 1 0 -1При построении циклового базиса графа G мы поочередно добавляли к остовномудереву графа G ребра x2 , x3 , x5 , x7 . Выделим соответствующие этим ребрам столбцы вматрице С (G) (они помечены символом  ).

Из выделенных столбцов составим матрицу.Ее определитель равен  1  0, а следовательно, ранг матрицы С (G) равен числу строк,т.е.  (G).Пусть теперь граф G , изображенный на рис. 8.7, соответствует электрической цепи, изображенной на рис. 8.10 (см. замечание 8.1).Рис. 8.1051Выберем произвольным образом направления токов в элементах цепи (условныенаправления; после решения соответствующей системы уравнений знаки при величинахтоков покажут истинные направления токов).

Пусть эти направления соответствуют выбранной ранее ориентации ребер графа G (см. рис. 8.9). Выпишем систему уравненийКирхгофа для напряжений в соответствии с (8.1):1 :  u1  u2  u6  u8  0, 2 : u3  u4  u6  u9  0, 2 :  u5  u6  u8  0, 2 :  u6  u7  u9  0,или, с учетом закона Ома, а также того, что u1  E1 , u5  E2 , имеем: E1  i2 r1  i6 r4  i8 r6  0, i r  i r  i r  i r  0, 32 43 64 97  E5  i6 r4  i8 r6  0,  i6 r4  i7 r5  i9 r7  0.Система уравнений Кирхгофа для токов имеет вид (8.2), где~x1 ~x3 ~x5 ~x6 ~x7 ~x8 ~x9x2 ~x4 ~B(D) v1-1-10000000v201-10-1-1-100v3001-100000v41000100-10v500000101-1v6000100101(8.3).При этом для достижения линейной независимости системы уравнений Кирхгофадля токов необходимо исключить из системы (8.2) любое уравнение, например, второе.В результате система линейно независимых уравнений Кирхгофа для токов имеет вид: i1  i2  0,i  i  0, 3 4(8.4)i1  i5  i8  0,i  i  i  0,6 8 9i4  i7  i9  0.Таким образом, общей системой уравнений для токов является объединение систем(8.3), (8.4).

Заметим, что полученная объединенная система уравнений состоит из девятиуравнений относительно девяти неизвестных: i1 , i2 ,..., i9 , после нахождения которых нетрудно определить u1 , u2 ,..., u9 .Тема 9. Транспортные сети. Поток в транспортной сети. Максимальный потокПод транспортной сетью будем понимать орграф D  (V , X ), где V  {v1 ,..., vn }, свыделенными вершинами v1 , vn , для которого выполняются условия:52(Т1) существует одна и только одна вершина v1 , называемая источником, такая,1что D (v1 )   (т.е. ни одна дуга не заходит в вершину v1 );(Т2) существует одна и только одна вершина vn , называемая стоком, такая, чтоD(vn )   (т.е. ни одна дуга не исходит из вершины vn );(Т3) каждой дуге x  X поставлено в соответствие целое число c( x)  0, называемое пропускной способностью этой дуги.Вершины в транспортной сети, отличные от источника и стока, называются промежуточными.Функция  (x), определенная на множестве X дуг транспортной сети D и принимающая неотрицательные целочисленные значения называется потоком в транспортнойсети D, если:(П1) для любой дуги x  X величина  (x), называемая потоком по дуге x , удовлетворяет условию 0   ( x)  c( x) ;(П2) для любой промежуточной вершины v сумма потоков по дугам, заходящим вv, равна сумме потоков по дугам, исходящим из v.Величиной потока  в транспортной сети D будем называть число  , равноесумме потоков по дугам, исходящим из источника v1 (или, что то же самое, равное суммепотоков по дугам, заходящим в сток v n ).Пример 9.1.

На рис. 9.1 приведен пример транспортной сети D  (V , X ) (см. (а)), атакже пример потока  в этой сети (см. (б)); в этом примере   8  10  10  3  5  18. Нарис. 9.1 (а) пропускные способности дуг взяты в скобки. На рис. 9.1 (б) около каждой дугиx  X указан поток по этой дуге  (x). Проверьте выполнение условия (П2) для потока в транспортной сети D.(а)(б)Рис. 9.1Пусть  – поток в транспортной сети D  (V , X ). Дуга x  X называется насыщенной, если поток по ней равен ее пропускной способности, т.е., если  ( x)  c( x). Поток называется полным, если любой путь из источника в сток содержит по крайней мере однунасыщенную дугу.

Поток  с максимальной величиной  называется максимальным.Очевидно, что максимальный поток обязательно является полным. Обратное, вообще говоря, не верно (не всякий полный поток является максимальным). Тем не менее полныйпоток можно рассматривать как некоторое приближение к максимальному. В связи с этимопишем алгоритм построения полного потока в транспортной сети D.53Алгоритм 9.1 (построения полного потока в транспортной сети D )Шаг 1.

Полагаем x  X  ( x)  0 (т.е. начинаем с нулевого потока). Полагаем D  D( D – вспомогательный орграф).Шаг 2. Удаляем из D  дуги, являющиеся насыщенными при потоке  в транспортной сети D.Шаг3. Ищем в D  простую цепь  из v1 в vn . Если такой цепи нет, то  – искомый полный поток. В противном случае переходим к шагу 4.Шаг 4. Увеличиваем поток  (x) по каждой дуге x из  на одинаковую величину a  0такую, что по крайней мере одна дуга из  оказывается насыщенной, а потоки по остальным дугам из  не превосходят их пропускных способностей. Переходим к шагу 2.Разбор типового варианта. (а) Используя алгоритм 9.1, построить полный поток втранспортной сети из примера 9.1.Решение. Начинаем с нулевого потока  0 . Каждой новой цепи из v1 в vn  v5 будемставить в соответствие ее очередной номер, т.е.

будем обозначать эти цепи через 1 , 2 ит.д. Соответственно после нахождения цепи 1 поток  0 изменится на поток 1 (см. шаг4 алгоритма 9.1). После нахождения цепи  2 поток 1 изменится на  2 и т.д. Числа, накоторые увеличиваем потоки по дугам из  i , обозначаем через ai . Насыщенные дуги приизображении транспортной сети D с очередным потоком  i помечаем символом  . Нарис. 9.2 приведены изображения орграфа D с потоком  0 , а также вспомогательного орграфа D, который на этом этапе совпадает с D.D0Рис. 9.2Выделяем в D  простую цепь 1  v1v2v4v5 из v1 в v5 . Увеличиваем поток  (x) покаждой дуге x из 1 на одинаковую величину a1  9 до насыщения дуг ( v1 , v2 ), (v2 , v4 ),при этом поток по дуге (v4 , v5 ) не превышает ее пропускной способности. В результатепоток  0 меняется на поток 1 , а из орграфа D  удаляются дуги (v1 , v2 ), (v2 , v4 ). На рис.9.3 приведены изображения орграфа D с потоком 1 , а также соответствующего этомупотоку вспомогательного орграфа D.54D1Рис.