Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 4
Текст из файла (страница 4)
Кроме того, древовидность всегда имеет корень. Корень древовидности — это единственный узел сети, из которого ориентированные луги могут только исходить. Древовидность не может иметь более одного корня, Следовательно, древовндность из й узлов содержит к — ! узел, в каждый нз которых заходит только одна луга, и олин узел, из которого дуги могут только исходить. Дерево, являющееся древовтедностью, будем называть древовидным деревом„а остов, являющийся древовкдностью— древовидным остовом. о Илк, короче, остовом. — Прим. перев.
з> Называемые весами дуг.— Прим. перев. Введение Формально древовидность с корнем х,енй1 определяется следующим образом: 1. Каждый узел, отличный от хь является конечным для одной единственной дуги. О О О У ° У Корень Корень О О О 1.5.
Деревья н аревовндностн. 6' — остов сети «а»; а — дерево сети «а»; а — ориентирован- сети «г»: е — древовидный остов сети «г»; ж — дерево сети «г», а — остов сети «г». Рнс а — неориентированнан сеть; нан сеть; д — древовидиость 2. Узел х~ не является конечным ни для одной дуги. 3. Сеть не содержит контуров. Отметим, что для каждого узла, отличного от хь существует единственная цепь, соединяющая его с хь 2 — 1 Воя Глава г Рис. 1.5 иллюстрирует основные определения, приведенные для неориентнрованных и ориентированных сетей, деревьев и лревовидностей. На рис. 1.5,а — е изображены неориентнрованная сеть, остов этой сети и дерево, не являющееся остовным, соответственно.
На рис. 1.5, г — е изображены ориентврованная сеть, древовидность этой сети и ее древовидный остов соответственно. На рис. 1.5,Ж, з изображены дерево и остов ориентированной сети соответственно. Е2. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ СЕТЕЙ Очевидно, что сети, которые графически представлены различным образом, могут соответствовать одним и тем же элементам некоторой системы и выражать одни и те же отношения. Однако установить эквивалентность двух сетей большой размерности иногда бывает чрезвычайно сложно.
В теории графов две сети, между дугами и узлами которых может быть установлено взаимно однозначное соответствие, называют изоморфными. Если два графа изоморфны, то любое уравнение, справедливое для одного из них, справедливо и для другого графа. Нередко некоторые общие формы представления сетей позволяют упростить расчет или установить такие свойства исследуемого объекта, благодаря которым отпадает необходимость в выполнении части вычислений нли проведении дальнейшего анализа. Помимо того что исследование графической и матричной форм представления сетей помогает при выполнении вычислений, их изучение полезно и с педагогической точки зрения.
Количественные характеристики дуг сети, а также взаимосвязь между ее узлами могут быть представлены с помощью матрицы расстояний, илн матрицы стоимостей. Кроме того, взаимосвязь между узлами задается с помощью матрицы смежности или матрицы иициденций узлы-дуги. Для простоты изложения вопросов, связанных с матричным представлением сетей, будем ~рассматривать сеть б=(о), А), в которой узлы из множества, Х занумерованы числами 1, 2,...,п, а каждой дуге (1, 1) из множества А поставлен в соответствие количественный параметр си, который обычно называют обобщенной стоимостью, или длиной дуги.
Матрица стоимостей задается массивом С=1си) (для всех (1, 1) ееА). Элементы матрицы С определяют возможности рассматриваемой системы или естественные ограничения, накладываемые на нее. Они могут соответствовать расстоянию, транспортным затратам, пропускным способностям водных магистралей, максимально допустимым нагрузкам на ли~пни электропередачи, надежности компонент системы и т. п.
Если 0 — неориентнрь- Введение ваннаЯ сеть, то си=си длЯ всех 1'О 1)епА. В этом слУчае матрица С является симметричной. Матрица смежности ориентированной сети задается массивом Х= )хи1, где 1, если дуга (1, 1) сА направлена от узла 1ЕХ к узлу фЧ, хд —— О в противном случае. Если сеть б является неориентированной, то каждую дугу 1'О ДенА можно заменить двумя противоположно направленными дугами. При этом матрица Х будет симметричной.
Рис. 1.6. Неориентироианнаи сеть. Матрица инциденций узлы-дуги ориентированной сети задается массивом л= 1з;е1, где < 1, если узел 1Е1ц является начальным узлом дуги ааЕА, — 1, если узел 1Ей1 является конечным узлом дуги аа~А, О в противном случае. Если сеть 6 является неориентированной, то величины тна определяются следующим образом: 1, если узел 1~й1 принадлежит дуге а„ЕА, г$а = О в противном случае. С помощью матричного представления сетей могут быть получены важные свойства как неориентированных, так и ориентированных сетей. В качестве примера рассмотрим вначале неориентированную сеть 6= (1ч, А), изображенную на,рис.
1.6. Множества М и А определяются следующим образом: й1 = (1) = (1, 2, 3, 4), А=(аа)=(аман, а,,а„а„а,). Глава 1 Матрица смежности Х и матрица инциденций Е в данном примере имеют вид 1 2 3 4 1 0 1 1 0 2 1 1 1 1 Х =(х.~ = 3 1 1 0 1 ) 4 0 1 1 1 2 в Нв цв ив 1 1 0 0 0 0 1 0 1 1 1 0 0 1 0 1 0 1 О 0 0 0 1 1 2 Е= [зо(= 3 Исходя из структуры матрицы смежности Х, можно утверждать следующее: 1.
Если к сети добавляется узел, не связанный с ней дугами, то к матрице следует приписать нулевую строку н нулевой столбец. 2. Матрица является свмметричной. 3. Каждый ненулевой элемент главной диагонали соответствует петле. Рнс. 1.7. Орнентнроаанная сеть. В качестве упражнения читателю предлагается вывести аналогичные свойства матрицы инциденций а. Перейдем к рассмотрению ориентированной сети (рис. 1.7). Множество узлов М и множество дуг А данной сети опреде.ляются следующим образом: 1ч = Я = (1, 2, 3, 4„5, 6), А = (наг = (а„ ав ав а„ ав, ав нт нв пв1 21 Введение 1 2 3 4 5 О 1 О 1 О О О 1 О О О О О О О О 1 1 О 1 О О 1 О О )О О О О О О О 1 О 3 Х=1х,1= 4 аз а4 +1 О О О +1 ΠΠ— ! ΠΠΠΠΠΠΠ— ! а, а, О О О а, а, ΠΠ— ! ΠΠΠ— ! О +! +1 +! ΠΠ— ! ΠΠΠΠΠ— 1 О Х=Ре„1= 3 4 О О +! +1 Π— 1 О Исходя из структуры матрицы смежности Х рассматриваемой ориентированной сети, можно утверждать следующее: 1.
Каждый нулевой столбец матрицы соответствует источнику. 2. Каждая нулевая строка матрицы соответствует стоку. 3. Если все элементы главной диагонали нулевые, то сеть ие содержит петель, и наоборот, ненулевой элемент главной диагонали соответствует петле. 4.Матрица не является симметричной. В качестве упражнения читателю предлагается вывести аналогичные свойства матрицы инциденций Е ориентированной сети.
Следует отметить, что все сформулированные выше утверждения справедливы и тогда, когда вместо величин х;;, принимающих значения О или 1, берутся произвольные величины с„. Матричные представления сетей нередко оказываются чрезвычайно полезными при определении отношений предпочтения или установления эквивалентности сетевых моделей. Матрица смежности Х и матрица инциденций Х в данном примере имеют вид Глава 1 1.3. СОХРАНЕНИЕ ПОТОКА При изучении характеристик сети часто возникает необходимость в вычислении оптимального значения функции потока, протекающего от источника з к стоку !. Обычно такие вычисления проводятся в задачах, связанных с однопродунтовым потоком, поскольку потоки в дугах сети соответствуют потокам некоторого однородного продукта, такого, как электроэнергия, вода, информация, самолеты на воздушных трассах и т. п.
Пусть ~); — множество всех узлов, связанных с узлом Т дугами, направленными к й а а; — множество всех узлов, связанных с ! дугами, направленными в противоположную сторону. Целочисленная функция ~п, определенная на множестве А, называется потоком в ориентированной сети 6= (й(, А), если Г1! ~) О для всех (1, !) ЕА, (1.1) ~~)')!! — ~)т! —— О для всех !ЕЪ1, ! ~ з, 1Ф 1, (1.2) !ва !аз! ! 1! ( с,! для всех (1, )) ЕА. (1.3) Согласно приведенному определению, значение ~н можно рассматривать как объем продукта, протекающего по дуге ('й 1! от узла ! к узлу 1, причем данный объем не превосходит пропускной способности га! дуги (й !).
Если узел ! не является ни источником, ни стоком, то величина потока, втекающего в 1, должна равняться величнне потока, вытекающего из этого узла. Данное положение известно под названием принципа сохранения потока. Условие сохранения потока описывается с помощью выражения (1.2). В рассматриваемых в данной книге задачах, связанных с однопродуктовым потоком в сетях, принцип сохранения потока выполняется всегда. Поток в дуге может изменяться, что имеет место, например, для сетей с выигрышами или проигрышами (см. равд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
