Элементы теории графов 2 страница

A

B

C

D

К

F

G

Н

I

J

К

L

М

N

Λ0

Нули в строке Λ₀ дают вершины, которым не предшествует ни одна дру­гая вершина. Таким образом, вершины E и H составляют уровень N ₀. Исключив из сумм строки Λ₀ значения, записанные в строках E и H, получим строку Λ₁, в которой нули из Λ₀ заменены знаком «+».

A

B

C

D

К

F

G

Н

I

J

К

L

М

N

Λ1

+

+

Рис. 2.23. Порядковая функция на графе: а) исходный граф; б) уровни упорядоченного графа

Рис. 2.24

Появившиеся в строке Λ₁ нули дают вершины, которым не предшествует ни одна другая вершина, кроме ранее удаленных E и H. Это вершины B, I, J, ко­торые образуют множество уровня N ₁. Далее из Λ₁ вычтем суммы строк B, I, J, заменив все ранее появившиеся нули знаками «+» и получим строку Λ₂:

A

B

C

D

К

F

G

Н

I

J

К

L

М

N

Λ2

+

+

+

+

+

Новые нули, появившиеся в Λ₂, дают вершины, для которых не существу­ет других предшествующих вершин, кроме удаленных E, H, B, I, J. Вершины A, G, N составляют уровень N ₂. Этот процесс продолжается до тех пор, пока не будет закончен перебор всех вершин исходного графа (матрицы):

A

B

C

D

К

F

G

Н

I

J

К

L

М

N

Λ3

+

+

+

+

+

+

+

+

Λ4

+

+

+

+

+

+

+

+

+

Λ5

+

+

+

+

+

+

+

+

+

+

+

+

+

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

Рис. 25. Уровни упорядоченного графа

Когда граф содержит, по крайней мере, один контур, найдется строка Λ _i в которой невозможно добиться появления нового нуля. Этот факт дает автоматическое средство для выявления контуров в графе.

Прикладные задачи теории графов.

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

Если каждому ребру графа G (V, E) приписано число l (e) ≥ 0, называемое его длиной, общая постановка этой задачи заключается в нахождении мини­мальной длины пути μ _ab между двумя произвольными вершинами a и b:

.

1а. Нахождение кратчайшего пути в графе с ребрами единичной длины. Если все ребра графа имеют одинаковую длину, то длина их принимается рав­ной 1. Вершины такого графа представляют состояние некоторой системы, в которой все переходы, делающиеся за один шаг, эквивалентны. Когда граф со­держит небольшое количество ребер, то искомый путь можно непосредственно увидеть, найти без каких-либо правил, путем перебора. При значительном ко­личестве вершин и ребер в графе возникает необходимость в четком описании способа решения задачи. Общее правило нахождения кратчайшего пути состо­ит в том, чтобы каждой вершине х_i приписать индекс λ _i, равный длине кратчайшего пути из данной вершины в конечную. Приписывание индексов верши­нам производится в следующем порядке:

· конечной вершине x ₀ приписывается индекс λ₀ = 0;

· всем вершинам, принадлежащим множеству ребер, инцидентных x ₀ (которые связаны ребрами с x ₀), приписывается индекс λ₁ = 1;

· всем вершинам, еще не имеющим индексов, принадлежащих множеству ре­бер, инцидентных x_i, приписывается индекс λ _i + 1;

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

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

Пример определения кратчайшего пути на графе с ребрами одинаковой длины из начальной вершины Z в конечную X показан на рис. 2.26. Часть вер­шин исходного графа при решении поставленной задачи можно не помечать, так как они заведомо не входят в искомый маршрут.

1б. Нахождение кратчайшего пути в графе с ребрами произвольной дли­ны. Задача приписывания вершинам графа числовых индексов усложняется, ес­ли его ребра имеют произвольную длину. Путь, проходящий через наименьшее количество вершин, часто имеет большую длину, чем «обходные» пути.

Рис. 2.26. Построение кратчайшего пути в графе с ребрами одинаковой xihiim

Пример. Решение этой задачи для графа рис. 2.27 с начальной вершиной a и конечной k и ребрами произвольной длины произведем графически:

· из начальной вершины v_a проведем все ребра, по которым из нее можно не­посредственно попасть в любую другую, и проставим на ребрах расстояние от v_a до соответствующей вершины (рис. 2.28, а);

· если между вершинами, выделенными на первом шаге, существуют другие пути, то определить, является ли длина непрямого пути между v_a и любой дру­гой вершиной меньше прямого из v_a в рассматриваемую вершину (рис. 2.28, б);

· добавляются все вершины, в которые можно непосредственно попасть из вершин, выделенных на первом шаге, и к ним применяется процедура, изло­женная в предыдущем пункте (рис. 2.28, в);

· шаги 3 и 2 повторяются, пока не появится конечная вершина k.

Рис. 2.27. Граф с ребрами произвольной длины

Кратчайший путь на рис. 2.28 показан сплошными линиями, все осталь­ные – пунктирными (рис. 2.28, б, в, г). Если длины прямого и непрямого пути равны, оба изображаются сплошными линиями. Над каждой вершиной про­ставлена длина кратчайшего пути до нее от начальной вершины. Эта задача решается и при дополнительном ограничении: число вершин, через которые проходит кратчайший путь, может быть минимальным.

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

Например, это процесс разработки, сооружения, монтажа и наладки обо­рудования крупного энергетического объекта, включая этапы выбора и подго­товки места строительства; выполнение комплексной научно-исследователь­ской темы с участием ряда организаций и т.п. Подобные проекты связаны с вы­полнением множества отдельных непересекающихся операций a ₁, a₂, …, a_n ко­торые выбираются так, чтобы можно было установить все существенные отно­шения, предшествующие данной операции. Хотя некоторые операции проекта независимы друг от друга, в общем случае между ними существует достаточно сильная зависимость во времени.

Рис. 2.28. Преобразования первого шага а), второго б), третьего в) и окончательный вариант г)

Например, настройка устройств РЗА энергообъекта может производиться только после предварительных расчетов и монтажа; ремонт обмотки силового трансформатора – начат только после отключения и отсоединения его от сети, выемки внутренней части, расшихтовки сердечника и т.д.

Если заданы все подобные временные зависимости, то они могут быть представлены в виде ориентированного графа (рис. 2.29), который называют сетевым. Каждая дуга графа рис. 2.29 соответствует одной операции, а каждая вершина называется событием и соответствует некоторому моменту времени. Так вершина v ₁ представляет событие, связанное с началом всего проекта, когда могут выполняться только операции a ₁, a₂, a ₃. Проект считается законченным после выполнения операций аи, a ₁₁, a _{1 2} , a ₁₃, а следовательно, всех операций проек­та, когда наступает событие, соответствующее вершине v ₈. Промежуточные вершины отражают взаимосвязи операций во времени. Вершины выбираются и сопоставляются с дугами так, чтобы для каждой операции (дуги) и события (вершины) было справедливо следующее утверждение: если операция a_i, имеет начальное событие в виде вершины v_i, то она не может быть начата до тех пор, пока все операции, заканчивающиеся в v_i не будут выполнены: операция a ₁₀ (также, как и a ₁₂) (рис. 2.29) может быть начата только после выполнения опе­раций a ₅ и a ₇. Косвенно начало операции a ₁₀ зависит от моментов выполнения операций a ₁, a ₂, a ₄, так как они непосредственно определяют начало операций a ₅ и a ₇. Граф, представляющей процесс выполнения операций, является ацикли­ческим. Наличие цикла создало бы невозможную ситуацию, в которой ни одна из операций, входящих в цикл не могла бы начаться первой.

Рис. 2.29.

На основании изложенного, определяются основные требования к по­строению сетевого графа:

1) в сетевом графе не должно быть тупиков – событий, из которых не выходит ни одной работы, если эти события не являются завершающими;

2) в сетевом графе не должно быть событий, в которые не входит ни од­ной работы, если эти события не являются исходными;

3) в сетевом графе не должно быть замкнутых контуров, циклов.

Предположим, что для выполнения каждой операции a, требуется извест­ное фиксированное время t (a_i), которое соответствует числам на дугах графа рис. 2.29. Несколько операций можно выполнять одновременно, если ни одна из операций рассматриваемой группы не ограничена моментами выполнения других операций, входящих в нее. Длина (сумма временных интервалов) любо­го пути из v ₁ в v_i соответствует времени, измеряемому от начала выполнения проекта до наступления события v_i, после осуществления которого, могут быть начаты операции, имеющие v_i, в качестве начальной вершины.

Путь, имеющий наибольшую продолжительность, называется критиче­ским – общая минимальная продолжительность всех работ, осуществляемых в данном проекте. Нахождение его выполняется по методу, аналогичному рассмотренному выше для поиска кратчайшего пути в графе с ребрами произволь­ной длины с заменой минимума целевой функции на максимум. Чтобы сокра­тить сроки выполнения проекта необходимо сократить сроки работ, находя­щихся на критическом пути. Критических путей (рис. 2.29) может быть не­сколько: P _кр1 = t _кр = { v ₁, v ₂, v ₄, v ₅, v ₆, v ₈,} = 13 и P _кр2 = t _кр = { v ₁, v ₂, v ₄, v ₆, v ₈,} = 13.

Разница между продолжительностью критического пути t _кр и любого дру­гого t_i называется резервом времени пути P _п = t _кр – t_i.

Разница между поздним t _п и ранним t _р сроками совершения того или ино­го события называется резервом времени события P _с = t _п – t _р.

Реально продолжительность каждой операции есть случайная величина, определяемая соответствующим законом распределения, оценки параметров и распределения которой используются при последующем анализе. При решении несложных задач предлагается использовать «бета-распределение», при кото­ром для каждой операции находятся (или задаются) три временные оценки: a – пессимистическая, b – оптимистическая и m – наиболее вероятная. Тогда сред­нее значение времени выполнения операций и его стандартное отклонение оце­ниваются как ; .

Показатели возможного разброса сроков окончания операций использу­ются для оценки вероятности окончания проекта в заданный срок. Кроме дли­тельности выполнения проекта рассматриваются и другие количественные ха­рактеристики: затраты людских или денежных средств (ресурсов, материалов, механизмов), очередность строительства или ввода связанных объектов и т.п., которые могут оказаться взаимозависимыми. Учет их позволяет сократить дли­тельность операций с помощью дополнительных ресурсных вложений. Реше­ние подобных задач осуществляется с использованием современных компью­терных технологий и программных продуктов, в частности, MS Project 2003.

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

Потоком в сети N называется целочисленная функция φ, определенная на дугах исходного графа. Целое число 0 ≤ φ(u) ≤ c (u) называется потоком по дуге a и интерпретируется как количество вещества, протекающего в единицу времени по дуге (скорость, мощность, потери). Если величина потока равна пропускной способности дуги φ(u) = c (u), поток называется насыщенным. На­правление потока определяется знаком φ(u). Поток полный, если любой путь, ведущий из v_i в v_j содержит, по крайней мере, одну насыщенную дугу.

Вершины в сети N классифицируются по их воздействию на поток φ: соз­дают (источники), поглощают (стоки) или сохраняют поток. Любой поток можно преобразовать в поток, только с одним источником и одним стоком, увеличив количество вершин в сети. В результате образуется сеть с одним ис­точником и одним стоком. Для такой сети справедливы известные из электро­техники законы Кирхгофа. Когда начальный поток является неполным, можно определить путь из вершины x ₀ в x_k который не содержит насыщенных дуг. На первом шаге полагаем, что величины φ(u), составляющие этот путь равны ну­лю. На втором к нулевому начальному потоку добавляется наименьшая из ве­личин c (u) – φ(u), вычисленных для дуг рассматриваемого пути, после чего рассматриваемый путь будет содержать, по крайней мере, одну насыщенную дугу. На последующих шагах подобным образом поступают с другими возмож­ными путями и получают полный поток.

Пример. Для сети энергосистемы, представленной графом рис. 2.30 с ука­занными на нем пропускными способностями дуг, соответствующими переда­ваемой мощности (величине протекаемого тока), определить максимальный по­ток из начальной вершины v ₀ в конечную v_k.

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

Рис. 2.30.

Таблица 2.1.

Дуги	Начальный поток Ф = 0	Путь P = { v 0, v 4, v 3, vk }	Путь	Путь P = { v 0, v 1, v 2, vk }
v 0, v 4
v 0, v 1
v 4, v 3
v 4, v 2
v 1, v 2
v 2, vk
v 3, v 2
v 3, vk

Специально отмеченные величины потока являются величинами, насы­щающими соответствующие дуги. В третьем столбце рассмотрен путь P = { v ₀, v ₄, v ₃, v_k }. Дуга v ₄, v ₃ насыщается, когда поток увеличивается до макси­мально возможной величины φ(u) = 2. В четвертом столбце представлен путь P = { v ₀, v ₄, v ₂, v_k }, в котором предыдущий по дуге v ₀, v ₄ поток увеличивается на 3 единицы, доводя его до насыщенного (φ(u) = 5), и, следовательно, не имеет смысла рассматривать другие дуги, содержащие v ₀, v ₄. Пятый столбец содержит данные, относящиеся к пути P = { v ₀, v ₁, v ₂, v_k } с насыщенным по дуге v ₁, v ₂ потоком φ(u) = 2, который увеличивает еще на 2 единицы результирующий поток сети.

Разрезав сеть по дугам v ₀, v ₄, v ₀, v ₁ и v ₃, v_k, v ₂, заключаем, что максимальный поток Ф = 7. Равенство исходящих из v ₀ и входящих в v_k потоков подтверждает­ся законом Кирхгофа. Особо отметим, что дуга v ₃, v ₂ не участвует в передаче мощности и при решении данной задачи она может быть исключена из состава сети. Однако при постановке целого ряда других задач (например, связанных с надежностью электроснабжения) ее роль может оказаться решающей.

4. Применение понятия дерева для конструирования кратчайшей сети. Предположим, что несколько электроприемников (РП, подстанций, узлов на­грузки или электростанций) объединяются в единую сеть. Поскольку требова­нием является только наличие связи между вершинами, задача сводится к поис­ку соединения минимальной длины (стоимости). Когда число узловых точек мало, решение получают последовательным перебором, но при увеличении ко­личества вершин задача усложняется. В терминах теории графов она формули­руется следующим образом. Пусть G – связный граф, каждому ребру которого приписано неотрицательное число c_ij – мера, вычисляемая по заданным коорди­натам как расстояние между узлами сети. Требуется построить граф T, у кото­рого сумма мер c_ij, у имеет минимальное значение M (T) = ∑ c_ij = min. Такой граф должен быть деревом, так как если бы он содержал цикл, удаление одного из ребер не нарушило бы его связанности.

Для построения этого графа используется алгоритм Краскала. 1. Ребра графа G упорядочиваются в порядке неубывания их мер. 2. Начав с первого ребра в этом списке, обладающего наименьшей мерой, определяется последо­вательность ребер в соответствии со следующим условием: на каждом после­дующем шаге выбирается ребро отличное от предыдущих, с наименьшей ме­рой, не образующее циклов с ранее выбранными ребрами. Если имеется не­сколько ребер с одинаковой мерой; то выбирается любое из них. Построенное таким образом дерево и есть сеть минимальной длины (стоимости).

При использовании этого алгоритма составления полного списка ребер в порядке возрастания их весов обычно не требуется, так как n ­1 искомых ребер, образующих сеть минимальной стоимости, будут найдены после просмотра только «верхней» части списка.

Если число узлов проектируемой сети относительно невелико, появляется возможность (особенно при разработке низковольтных сетей, сетей контроль­ных кабелей и кабелей связи) вторичной оптимизации дерева T, что может при­вести к дополнительному сокращению его длины (стоимости) на 7 ÷ 12%. Такая задача известна как задача Штейнера. Решение ее заключается в нахождении дерева L, которое «стягивает» множество вершин дерева Т так, что сумма мер вновь образованных ребер удовлетворяет неравенству M (L) < M (T).

Это достигается за счет изменения первоначальной структуры сети T вве­дением дополнительных «искусственных» вершин k, которые можно интерпре­тировать как транзитные устройства, распределительные пункты, клеммные ко­робки. Условия построения кратчайшего дерева заключаются в следующем.

1) Каждая «искусственная» вершина k_i вновь образованного дерева L имеет степень ρ = 3 и угол между ребрами, инцидентными ей – 120°. Эта верши­на является центром треугольника, вершинами которого служат три другие вершины, с которыми она связана. Отдельные вершины этого треугольника мо­гут оказаться при этом другими «искусственными» вершинами.

2) Максимальное число «искусственных» вершин k в L определяется со­отношением 0 ≤ k ≤ n – 2, где n – число вершин исходного графа T.

Пример. В соответствии с заданными координатами рис. 2.31, а построено дерево T, длина которого M (T) = 75. Путем введения двух дополнительных «ис­кусственных» вершин k = n – 2 = 4 – 2 = 2 построено дерево L, длина которого M (L) = 69 определена посредством несложных вычислений на основе информа­ции, представленной на рис. 2.31, б.

Рис. 2.31. Вторичная оптимизация дерева путем введения «искусственных» вершин

Рис. 2.32. Сокращение длины (стоимости) сети за счет введения «искусственных» вершин

Разность длин Δ N деревьев T и L: Δ N = M (T) – V (L) = 75 – 68 = 7. Полу­ченный результат означает, что выигрыш, который получен при вторичной оп­тимизации, может быть эффективен только в том случае, если затраты на со­оружение дополнительных «искусственных» вершин (распределительных уст­ройств) не превышают 7.

Следует отметить, что прокладка реальных инженерных коммуникаций, в том числе и электрических сетей, ведется обычно согласно плану расположения оборудования, и трассы линий находятся под прямым углом друг к другу. Рас­стояние между узлами сети (вершинами графа) с координатами (x ₁, y ₁),(x ₂, y ₂) вычисляется по формуле d ₁₂ = | x ₁ – x ₂|+| y ₁ – y ₂|.

При решении задачи Штейнера в этом случае через каждую вершину v_i дерева T проводятся горизонтали и вертикали, пересечения которых рассматри­ваются как возможное местоположение «искусственных» вершин.

Пример. Исходный граф T поострен в соответствии с рис. 232, а. Одно из решений задачи Штейнера представлено на рис. 2.32, б.

Дата добавления: 2015-04-30