Теория графов

Размещено на http://www.allbest.ru

1. ПОНЯТИЕ О ГРАФЕ. СПОСОБЫ ЗАДАНИЯ ГРАФА

1.1 Задание графа множествами вершин и линий

Граф геометрически представляет собой множество точек, соединенных линиями. Для более полного математического определения графа введем ряд обозначений. Множество точек или вершин х₁,х₂,…х_n графа G обозначим через Х, а множество линий d₁,d₂,…d_m, соединяющих между собой эти вершины - символом А. Тогда граф G можно полностью задать парой (Х,А). граф линейный программирование

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

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

Граф на рис. 2.1. можно представить в виде

G₁={ x₁, x₂, x₃; (x₁,x₂), (x₂,x₃), (x₃,x₁)}

На рис. 2.2 изображен смешанный граф, и его представление имеет вид

G₂={ x₁, x₂, x₃; 2(x₁,x₂), (x₂,x₃), (x₃,x₁)} ,

где цифра 2 означает две дуги из вершины х₁ в вершину х₂.

Размещено на http://www.allbest.ru

Рис. 2.2

1.2 Задание графа с помощью отображения

Иногда бывает удобно дать графу другое определение. Можно считать, что множество направленных дуг А, соединяющих элементы множества Х, отображает это множество само в себя. Граф G можно считать заданным, если даны множество его вершин Х и способ отображения Г множества Х в Х, т.е. G=(X,Г).

Для графа (рис. 2.1) отображение Г определяется следующим образом:

Г(х₁) = {x₂}; Г(х₂) = {x₃}; Г(х₃) = {x₁}.

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

Г(х₁) = {2x₂,x₃}; Г(х₂) = {x₃}; Г(х₃) = {x₁,x₂}. (2.1)

1.3 Задание графа с помощью обратного отображения

Поскольку Г(х_i) представляет собой множество таких вершин x_j X, для которых в графе G существует дуга (x_i,x_j), то через Г^-1(x_i) естественно обозначить обратное отображение, т.е. множество вершин x_k, для которых в G существует дуга (x_к,x_i). Граф можно задавать с помощью обратного отображения вершин. Тогда, например, для графа (рис. 2.2) можно записать

Г^-1(х₁) = {x₃}; Г^-1(х₂) = {2x₁,x₃}; Г^-1(х₃) = {x₁,x₂}. (2.2)

Вполне очевидно, что для неориентированного графа Г ^-1(х_i) = Г(х_i) для всех х Х.

1.4 Матричное представление графа

Для алгебраического задания графа удобно использовать матрицу смежности. Матрицей смежности графа, содержащего n вершин, называется квадратная матрица А размером (nxn), в которой элементы a_ij, стоящие на пересечении i-й строки и j-го столбца, численно равны количеству дуг графа, идущих из i-й вершины в j-ю. Для графа (рис. 2.2) матрица смежности имеет вид

A(1,1)={a}=

	J=1	J=2	J=3
i=1	0	2	1
i=2	0	0	1
i=3	1	1	0

Матрица смежности полностью определяет структуру графа. Множество столбцов, имеющих в строке x_i значения a_ij0, есть множество Г(х_i) с соответствующими коэффициентами (2.1), а множество строк i, имеющих в столбце x_j значения a_ij0, совпадает с множеством Г^-1(х_j) с соответствующими коэффициентами (2.2). Согласно определению матрицы смежности неориентированным графам соответствуют симметричные матрицы смежности. Матрица смежности для многоуровневого графа строится аналогично.

В графе (рис. 2.3) каждая вершина x_ij имеет два индекса: i - номер уровня; j - номер вершины данного уровня.

Рис. 2.3

Матрица смежности для графа (рис. 2.3) имеет вид A(2,2)={a}=

		K=1	K=1	K=1	K=2	K=2	k=2
		L=1	L=2	L=3	L=1	L=2	L=3
I=1	J=1	0	0	1	0	0	0
I=1	J=2	1	0	1	0	0	0
I=1	J=3	0	0	0	0	0	0
I=2	J=1	0	0	0	0	0	1
I=2	J=2	0	1	0	1	0	1
I=3	J=3	0	0	0	0	0	0

где индексы i, j характеризуют начальную вершину x_ij, а индексы k,l - конечную вершину x_kl.

2. ДОСТИЖИМОСТЬ И ОБРАТНАЯ ДОСТИЖИМОСТЬ ВЕРШИН ГРАФА

2.1 Матрица достижимостей и матрица обратных достижимостей

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

Матрица достижимостей R[1,1] = {r_ij} и матрица обратных достижимостей Q[1,1] = {q_ij} определяется следующим образом:

r_{ij= {} 1, если вершина x_j достижима из x_i, (2.3)

0 в противном случае;

q_{ij= {} 1, если из вершины x_j можно достигнуть (2.4)

вершину x_i, 0 в противном случае.

2.2 Определение матриц достижимостей и обратных достижимостей с помощью прямых и обратных отображений

Обозначим через RM(x_i) множество вершин графа, достижимых из заданной вершины x_i. Это множество состоит из таких элементов x_j, для которых элемент r_ij (2.3) в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице достижимостей R равны 1, поскольку каждая вершина достижима из себя самой с помощью пути длиной 0.

Поскольку отображение Г(x_i), описанное в п.2.1.2, является множеством таких вершин x_j, которые достижимы из x_i с использованием дуг длиной 1 [т.е. Г(x_i) - такое множество вершин, для которых в графе существуют дуги (x_i,,x_j)], то Г(Г(x_i)) = Г²(x_i) состоит из вершин, достижимых из x_i с использованием путей длиной 2. Аналогично Г^р(x_i) является множеством вершин, которые достижимы из x_i с помощью путей длиной Р.

Так как любая вершина графа, которая достижима из x_i, должна быть достижима с использованием пути (или путей) длиной 0, или 1, или 2,…,

или Р (с некоторым конечным, но, возможно, достаточно большим значением Р), то множество вершин, достижимых из x_i, можно представить в виде

RM(x_i) = {x_i} Г(x_i) Г²(x_i) Г^р(x_i). (2.5)

Таким образом, множество RM(x_i) может быть получено последовательным выполнением (слева направо) операций объединения в соотношении (2.5) до тех пор, пока «текущее» множество не перестанет увеличиваться по размеру при очередной операции объединения. С этого момента последующие операции не будут давать новых членов множеству, и, таким образом, будет образовано достижимое множество RM(x_i). Число объединений, которое нужно выполнить, зависит от графа, но, очевидно, что число Р меньше числа вершин в графе.

Имея RM(x_i) для всех вершин графа, можно построить матрицу достижимостей R так. Положим r_ij = 1, если x_j R(x_i) и r_ij = 0 в противном случае. Полученная таким образом матрица R является матрицей достижимостей.

Для построения матрицы обратных достижимостей применим обратные отображения (п.2.1.3). Обозначим через QM(x_i) множество таких вершин графа, что из любой вершины этого множества можно достигнуть вершины x_i.

Аналогично построению достижимого множества RM(x_i) на основе соотношения (2.5) можно «сформировать» множество QM(x_i), используя следующее выражение:

QM(x_i) = {x_i} Г^-1(x_i) Г^-2(x_i) … Г^-р(x_i), (2.6)

где Г^-2(x_i) = Г^-1(Г^-1(x_i) и т.д.

Операция выполняется слева направо до тех пор, пока очередная операция объединения не перестанет изменять «текущее» множество QM(x_i).

Имея QM(x_i) для всех вершин графа, можно построить матрицу обратных достижимостей Q. Положим q_ij = 1, если x_j QM(x_i) и q_ij = 0 в противном случае.

Из определений матриц R и Q очевидно, что столбец x_i матрицы Q совпадает со строкой x_i матрицы R, т.е. Q = R^T.

2.3 Определение матриц ограниченных достижимостей и ограниченных обратных достижимостей с помощью прямых и обратных отображений

Матрицы достижимостей и обратных достижимостей, определяемые в п.2.2.2, являются полными в том смысле, что на длины путей от x_i и x_j не накладывались никакие ограничения. С другой стороны, можно определить матрицы ограниченных достижимостей и обратных достижимостей - надо потребовать, чтобы длины путей не превышали некоторого заданного числа. Эти матрицы также могут быть построены с помощью соотношений (2.5) и (2.6) - надо действовать точно так, как раньше, при нахождении «неограниченных» матриц, но теперь р будет верхней границей допустимых путей.

2.4 Определение матриц достижимостей и обратных достижимостей с помощью матрицы смежности

Матрица смежности, как отмечалось выше, полностью определяет структуру графа. Возведем матрицу смежности в квадрат. Пусть элемент d⁽²⁾_ik матрицы А² определяется по формуле

(2.7)

Слагаемое (d_ijd_jk) в уравнении (2.7) отлично от нуля тогда и только тогда, когда оба числа d_ij и d_jk отличны от нуля, в противном случае слагаемое равно 0. Поскольку из соотношений d_ij 0, d_jk 0 следует существование путей длиной 2 из вершины x_i к вершине x_k, проходящих через вершину x_j, то d⁽²⁾_ik равно числу путей, идущих из x_i в x_k.

Аналогично, если d^(p)_ik является элементом матрицы A^р, то d^(p)_ik равно числу путей длиной р, идущих от x_i к x_k.

Однако надо подчеркнуть, что в матрицах достижимостей и обратных достижимостей не требуется учета числа путей из вершины x_i в вершину x_j. В матрицах отмечается лишь то, что есть такой путь или его нет, т.е. необходима операция нормализации. С учетом последнего замечания формула для определения матрицы достижимостей R на основе матрицы смежности А имеет вид

R = (E + A + A² + … + A^p) //норм. (2.8)

Здесь Е - единичная матрица, а «норм» означает операцию нормализации, заключающуюся в том, что элементы матрицы R, не равные нулю, заменяются на 1.

Таким образом, матрица R может быть получена последовательно выполняемой (слева направо) операцией суммирования указанных в (2.7) матриц до тех пор, пока «текущая» матрица не перестанет изменяться при очередной операции суммирования. Для получения матрицы ограниченных достижимостей значение р должно быть ограничено.

С учетом определения (2.4) матрицу обратных достижимостей можно определить с помощью матрицы смежности по формуле

Q = (E + A^T + (A^T)² + … + (A^T)^P) // норм. (2.9)

Аналогично предыдущему случаю для получения матрицы ограниченных обратных достижимостей необходимо ограничить величину р.

Формулы (2.8) и (2.9) справедливы как для одноуровневых (вершины задаются одним индексом), так и для многоуровневых (вершины задаются несколькими индексами) графов. Так, для многоуровневого графа (рис. 2.3) матрицa достижимостей , вычисленная на основе формулы (2.8) , имеет вид

R(2,2)={r}=

		k=1	k=1	k=1	k=2	k=2	k=2
		l=1	l=2	l=3	l=1	l=2	l=3
i=1	j=1	1	0	1	0	0	0
i=1	j=2	1	1	1	0	0	0
i=1	j=3	0	0	1	0	0	0
i=2	j=1	0	0	0	1	0	1
i=2	j=2	1	1	1	1	1	1
i=2	j=3	0	0	0	0	0	1

2.5 Разбиение графа на подграфы

Операция разбиения графа позволяет в ряде случаев существенно упростить задачу анализа сложной системы, представленной в виде графа. Иногда такое разбиение само является целью анализа графовой модели системы. Изложение методики разбиения будет вестись, как и ранее, на основе множественного подхода (использования операций теории множеств - пп. 1.2,1.3) и матричного подхода (использования теории матриц - пп. 1.4, 1.5).

2.5.1 Определение существенных вершин на пути из вершины x_i в вершину x_j

Так как RM(x_i), определяемое формулой (2.5), является множеством вершин, достижимых из x_i, а QM{x_j}, определяемое формулой (2.6), является множеством вершин, из которых можно достигнуть x_j, то их пересечение RM(x_i) QM(x_j) определяет множество таких вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от x_i к x_j. Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин x_i и x_j. Все остальные вершины x_k RM(x_i) QM(x_i) называются несущественными или избыточными, поскольку их удаление не влияет на пути от x_i к x_j.

2.5.2 Определение сильных компонент графа на основе множественного подхода

Определим вначале понятие «сильно связный граф». Ориентированный граф называется сильно связным, если для любых двух различных вершин x_i и x_j cуществует, по крайней мере, один путь, соединяющий x_i и x_j. Это определение означает также, что любые две вершины такого графа взаимно достижимы.

На основании введенного понятия сильная компонента (СК) графа может быть определена как максимальный (содержащий наибольшее число вершин) сильно связный подграф исходного графа. Поскольку в сильно связном графе произвольная вершина x_j достижима из любой другой вершины x_i, то в ориентированном графе существует одна и только одна СК, содержащая данную вершину x_i.

Таким образом, в СК каждую вершину x_i можно считать одновременно начальной и конечной вершиной пути, определяющего цикл, содержащий x_i. Естественно, что в СК должны оставаться только существенные вершины некоторого цикла, содержащего x_i. Такое множество существенных вершин определяется пересечением RM(x_i) QM(x_i) и задает сильную компоненту, содержащую вершину x_i. Если эти вершины удалить из графа G = (X,Г), то в оставшемся подграфе можно таким же способом выделить новую СК, содержащую x_j X - RM(x_i) QM(x_i). Эту процедуру можно повторять до тех пор, пока все вершины графа G не будут сгруппированы в соответствующие СК. После завершения этой процедуры граф G будет разбит на свои сильные компоненты, а граф G^*, отображающий с помощью дуг связь между собой сильных компонент, называют конденсацией графа G.

Подчеркнем, что конденсация G^* не может содержать циклов, поскольку наличие цикла означает, что любые вершины этого цикла взаимно достижимы, а поэтому совокупность всех вершин цикла может принадлежать лишь некоторой СК в G^*.

2.5.3 Определение сильных компонент графа на основе матричных представлений графа

Процедуру, связанную с нахождением СК графа, можно сделать более удобной, если непосредственно использовать матрицы достижимостей R и обратных достижимостей Q. Определим скоттово (адамарово) произведение (п.1.5.6) R O Q. В полученной матрице R O Q строка x_i содержит единицы только в тех столбцах x_j, для которых выполняется условие: вершины x_i и x_j взаимно достижимы; в других местах строки x_i стоят нули. После определения СК, содержащей вершину x_i, из матрицы R O Q удаляются строки и столбцы, соответствующие вершине СК. Описанную процедуру удаления повторяют каждый раз после определения новой СК.

2.5.4 Определение оптимальной базы графа

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

1. Каждая вершина графа достижима хотя бы из одной вершины множества В.

2. Среди вершин базы В нет вершины, которая достижима из другой вершины множества В.

3. Множество вершин В должно быть наименьшим.

Рассмотрим алгоритм нахождения базы графа.

1. Для графа строится его конденсация (п.2.3.2).

2. Среди вершин Y_i графа конденсации находим такие, в которые не заходит ни одна дуга (Y_i являются сильными компонентами исходного графа). Пусть такими вершинами будут Y_l, Y_m.

3. Для построения базы нужно из каждой выбранной на 2-м шаге сильной компоненты (Y_l = {X₁^l, X₂^l,…, X_N^l}, Y_m = {X₁^m, X₂^m,…, X_N^m}) взять по одной вершине (x_i^l, x_j^m). Эти вершины и будут определять базу графа. Чтобы определить оптимальную базу, нужно знать длину дуг. Оптимальная база имеет минимальное суммарное расстояние до всех вершин графа. Алгоритм определения длин кратчайших путей между всеми вершинами графа одновременно будет дан в п.3.4.2.

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

2.5.5 Определение оптимальной антибазы графа

Антибазой графа В^-1 является такое множество вершин графа, которое удовлетворяет следующим условиям.

1. Из каждой вершины графа можно достичь хотя бы одной вершины множества В^-1.

2. Среди множества вершин В^-1 нет вершины, которая достижима из другой вершины этого множества В^-1.

3. Множество вершин В^-1 должно быть минимальным.

Рассмотрим алгоритм нахождения антибазы графа.

1. Для графа строится его конденсация (п.2.3.2).

2. Среди вершин Y_i графа конденсации находим такие, из которых не выходит ни одна дуга. Пусть такими вершинами будут Y_k, Y_f.

3. Для построения антибазы нужно из каждой выбранной на 2-м шаге сильной компоненты (Y_k = {x₁^k, x₂^k,…, x_N^k}, Y_f = {x₁^k, x₂^k,…, x_N^k}) взять по одной вершине (x_i^k, x_j^k). Эти вершины будут определять антибазу графа. Оптимальная антибаза имеет минимальное суммарное расстояние от всех вершин графа (см. п.3.4.2).

3. АЛГОРИТМЫ ОПТИМИЗАЦИИ НА ГРАФОВЫХ МОДЕЛЯХ

В данной главе рассматриваются графовые модели [4,5] для оптимизации транспортных сетей и потоков, решения задач календарного планирования, задач о назначениях и других задач дискретной оптимизации. Изложение алгоритмов оптимизации ориентировано на реализацию с помощью цифровых вычислительных машин.

3.1 Решение задачи о максимальном потоке методом расстановки пометок на графе (алгоритм Форда-Фалкерсона)

Граф, элементам которого поставлены в соответствие некоторые параметры, называется сетью. В зависимости от приложений различают транспортные, электрические, информационные и т.п. сети.

Поскольку в теории графов рассматриваются общие методы исследования графов и сетей, независимо от их природы, то для характеристики сетей вводятся некоторые общие понятия. Рассмотрим их, проводя для наглядности аналогию с транспортной сетью.

Каждая вершина I характеризуется интенсивностью d(i). Те вершины, для которых D(i) 0, называются источниками, вершины, для которых D(i) 0 - стоками, остальные - нейтральными. Так, для транспортной сети источниками являются пункты-поставщики, стоками - пункты-получатели, нейтральными - пункты, где отсутствует как производство, так и потребление данного продукта.

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

Если в сети с одним источником S и одним стоком t задана функция пропускной способности {r_ij}, то в ней может быть задана также функция, называемая потоком.

Потоком в сети называется функция, сопоставляющая с каждой дугой целое число d_ij и обладающая свойствами:

0 d_ij r_ij, {x_i, x_j} X; (3.1)

(3.2)

(3.3)

Для транспортной сети величина d_ij характеризует интенсивность потока по дуге . Эта величина означает количество вещества, проходящего через дугу в единицу времени.

Таким образом, потоком в сети или просто потоком называется совокупность {_ij} по всем дугам сети.

Условия (3.1) означают, что поток по каждой дуге неотрицателен и не превышает ее пропускной способности; условия (3.2) показывают, что количество вещества, протекающего в любую нейтральную вершину, равно количеству вещества, вытекающего из нее. Следовательно, общее количество вещества, вытекающего из источника, совпадает с общим количеством вещества, притекающего в сток, что и отражается в условии (3.3).

Линейная форма V в (3.3) есть величина потока в сети. Одна из основных задач на сетях состоит в определении величины наибольшего потока, допустимого в сети при заданных ограничениях на интенсивности потоков дуг. Математически она формулируется так: найти значения переменных d_ij, максимизирующие линейную форму (3.3) при ограничениях (3.1)-(3.2).

Рассмотрим решение поставленной задачи методом расстановки пометок непосредственно на графе (алгоритм Форда-Фалкерсона). Решение проводится путем многократного повторения двух шагов алгоритма.

Первый шаг. Пометим вершину-исток S меткой (0,) и отнесем вершину S к множеству R, а остальные вершины графа к множеству . Далее расстановка меток осуществляется последовательно. Рассмотрим правило формирования меток. Выберем любую помеченную вершину i (первоначально это единственная вершина S) (в дальнейшем для упрощения записи формул, относящихся к одному графу, вместо «вершина x_i» будем писать просто номер вершины «i». Отмеченные вершины относятся к множеству R, непомеченные к множеству . Рассмотрим все непомеченные вершины j, связанные дугами с вершиной i. Вершину j относят к множеству R, если выполняется одно из условий:

i R и d_ij r_ij; (3.4)

i R и d_ji 0. (3.5)

Тем вершинам j, для которых выполняется условие (3.4), припишем метку (i⁺, _j), где _j = min{_i, r_ij - d_ij}. Тем вершинам j, для которых выполняется условие (3.5), припишем метку (i^-, _j), где _j = min{_i, d_ji}.

Изложенное правило формирования меток для наглядности представим графически с помощью рис. 3.1 и 3.2 соответственно для случаев (3.4) и (3.5).



После помечивания вершины j, ближайшей к S, аналогично производим помечивание других вершин. Эту процедуру помечивания повторяем до тех пор, пока не пометим вершину t, или до тех пор, пока нельзя будет сделать новых пометок.

В первом случае (помечена вершина t) перейдем ко второму шагу, во втором случае исходный поток максимален.

Второй шаг. Вершина t имеет пометку (j⁺, _t) или (j^-, _t). Если пометка вида (j⁺, _t), заменяем d_jt на (d_jt + _t), если пометка вида (j^-, _t), то заменяем d_tj на (d_tj - _t). Затем в любом случае переходим к вершине j. В отношении любой вершины j поступаем аналогично: если ее пометка вида (i⁺, _j), то заменяем d_ij на (d_jt + _t), если ее пометка вида (j^-, _j), то заменяем d_ji на (d_ji - _t) и переходим к вершине i. Так поступаем, пока не достигнем источника S. После этого стираем все пометки и вновь переходим к первому шагу.

Таким образом, процесс расстановки пометок представляет собой систематический поиск цепи из S в t, на которой поток может быть увеличен. Если в результате первого шага сток оказался непомеченным, то вдоль найденной цепи можно увеличить поток. Если, с другой стороны, первый шаг закончился, а сток остался непомеченным, то достигнутый поток максимален. Изложенный алгоритм может использоваться для решения задачи и в более общем случае.

Несколько источников и стоков

Предположим, что множество узлов сети разбито на три множества: S - множество источников, Т - множество стоков, R - множество промежуточных узлов. Расширим сеть, добавив два узла S^* и Т^* и все дуги (S^*, S) и (Т, Т^*). Доопределим значения пропускных способностей на вновь введенных дугах:

r^*(S^*, x_i) = , x_i S;

r^*(x_j, T^*) = , x_j T.

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

3.2 Решение задачи о максимальном потоке в табличной форме

Метод расстановки пометок на графе имеет большую наглядность для уяснения алгоритма. Однако при практических расчетах, особенно при постановке задачи для расширения на ЦВМ, часто более удобным является решение задачи в табличной форме. Рассмотрим решение задачи для случая определения максимального потока в многоуровневом графе [5]. Решение приводится на основе использования многомерных матриц (пп. 1.4, 1.5). Условие задачи зададим с помощью многомерной матрицы

,

где - номера начального и конечного уровней; - номера начальной и конечной вершин графа; - пропускные способности дуг из вершины j⁺ (уровня ) в вершину (уровня ).

Общий шаг алгоритма. Общий шаг состоит из трех действий.

1. Помечаем столбец, соответствующий вершине-источнику , знаком *. Затем отыскиваем в строке все положительные . Содержащие их столбцы помечаем сверху числом, соответствующим номеру источника . Далее переходим к просмотру тех строк, которые имеют те же номера, что и отмеченные столбцы. В каждой строке отыскиваем все положительные , расположенные в непомеченных столбцах, и отмечаем эти столбцы номером просматриваемой строки . Процесс оканчивается: а) когда помечен сток; б) когда все строки просмотрены и нельзя отметить новые столбцы. В случае «а» новый путь из источника в сток находим, начиная от стока по отметкам столбцов. Последняя вершина пути - сток . По отметке, например над столбцом , находим предшествующую вершину . Число отметим знаком минус

, а число знаком плюс . Пусть столбец был помечен номером . Двигаемся от числа по столбцу до строки . Продолжаем этот процесс до тех пор, пока не придем к источнику *.

В случае «б» алгоритм поиска нового пути закончен.

2. Определяем величину, на которую можно увеличить поток на найденном пути, = min {}.

3. Вычисляем новые пропускные способности дуг. Для этого из всех вычитаем , а ко всем прибавляем . Получаем новую матрицу пропускных способностей. Затем стираем в таблице все пометки и возвращаемся к действию 1.

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

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

3.3 Решение задачи о максимальном потоке в графе на основе линейного программирования

Рассмотрим сеть (рис. 3.3) с одним истоком (вершина 1) и одним стоком (вершина 4), на которой заданы пропускные способности дуг c₁=11, с₂=7, с₃=5, с₄=8. Обозначим величину потока из вершины 1 в вершину 2 через х₁, из 2 в 4 - через х₂, из 1 в 3 - через х₃, из 3 в 4 - через х₄. Произвольно задавать х_i (i=1..4) нельзя. Эти числа должны удовлетворять ряду ограничений.

Рис. 3.3

1. Поток дуги не может быть больше её пропускной способности:

0 х₁11, 0 х₂7, 0 х₃5, 0 х₄8.

2. Для любой вершины, не являющейся ни истоком, ни стоком, суммарный поток входящих дуг равен суммарному потоку выходящих дуг:

х₁-х₂=0, х₃-х₄=0.

3. Вводится понятие суммарного потока Ф на конечных дугах сети, отличное от понятия потока на дуге x_i, i=1..4. Сумма потоков, исходящих из начальной вершины, равен сумме потоков, входящих в конечную вершину:

х₁+х₃=Ф, х₂+х₄=Ф.

Возникает задача: определить величину максимального потока в графе при заданных пропускных способностях, т.е. найти х_i, i=1..4, удовлетворяющие условиям 1 - 3, максимизирующие целевую функцию F_max=Ф.

Существуют различные методы решения задач линейного программирования. Одним из наиболее распространённых методов решения задачи ЛП является симплексный метод. Он позволяет за конечное число шагов определить область допустимых базисных решений и найти оптимальное решение задачи.

Сначала необходимо представить задачу в удобном для программирования виде. Для этого заменим в уравнениях Ф на х₅, а часть равенств представим в виде неравенств (для решения задачи стандартным симплекс-методом). Получаем задачу ЛП:

F_max=x₅.

В соответствии с этим можно записать начальную симплекс -таблицу.

Таблица 3.1

	- x1	- x2	- x3	- x4	- x5	B
0	1	0	1	0	-1	0
0	0	1	0	1	-1	0
Y3	-1	1	0	0	0	0
Y4	1	-1	0	0	0	0
Y5	0	0	-1	1	0	0
Y6	0	0	1	-1	0	0
Y7	1	0	0	0	0	11
Y8	0	1	0	0	0	7
Y9	0	0	1	0	0	5
Y10	0	0	0	1	0	8
Fmax	0	0	0	0	-1	0

Решая задачу, получим конечную симплекс-таблицу с решением прямой задачи:

Таблица 3.2

	0	0	- y9	- y4	- y8	B
X1	0	0	0	1	1	7
X2	0	0	0	0	1	7
Y3	0	0	0	1	0	0
X4	-1	1	1	1	0	5
Y5	1	-1	0	-1	0	0
Y6	-1	1	0	1	0	0
Y7	0	0	0	-1	-1	4
X5	-1	0	1	1	1	12
X3	0	0	1	0	0	5
Y10	1	-1	-1	-1	0	3
Fmax	-1	0	1	1	1	12

Решение задачи для исходных переменных:

x₁=7; x₂=7; x₃=5; x₄=5; x₅=12;

при этом F_max=12.

3.4 Решение задачи о кратчайшем пути в транспортной сети непосредственно по графу

Пусть дан конечный граф, каждой дуге которого поставлено в соответствие число c_ij, называемое длиной дуги. Требуется найти путь наименьшей длины, ведущий из некоторой вершины S в некоторую вершину t. Рассмотрим один из алгоритмов решения данной задачи - алгоритм Минти. Он позволяет связать кратчайшими путями фиксированную вершину сети со всеми остальными.

Предварительный шаг. Пометим вершину S числом _s = 0. Далее продолжаем расстановку пометок следующим образом. Помеченные вершины будем относить к множеству R, непомеченные - к множеству . Итак, S R.

Общий шаг. Итак, R - множество помеченных вершин. Хотя бы одна вершина всегда имеется в R. Каждой вершине i R поставлено в соответствие число _i. Рассмотрим все дуги (), исходящие из множества помеченных вершин R и заканчивающиеся на непомеченных вершинах j . Найдем для каждой дуги () величину h_ij = _i + c_ij. Выделим дуги, на которых достигается минимум этой суммы, и отметим числом _j=min h_ij, (i R, j) те вершины j , на которых заканчиваются выделенные дуги. Будем производить таким образом помечивание вершин до тех пор, пока не пометим вершину t. Число _t указывает длину кратчайшего пути от S к t.

Заключительный шаг. Искомый путь определяем, двигаясь от t к S по выделенным дугам в направлении, обратном их ориентации.

Таким образом, при решении задачи выполняется конечное число раз общий шаг и один раз заключительный шаг.

3.5 Решение задач о кратчайших путях в табличной форме

3.5.1 Определение кратчайшего пути между двумя вершинами графа

Рассмотрим алгоритм решения для случая многомерного графа [5]. В конечном многомерном графе каждой дуге поставлено в соответствие число С_{i1,i2,,,il,m1,m2,,ml}, называемое длиной дуги из вершины x_i1,i2,,il в вершину x_m1,m2,,ml. Требуется найти путь наименьшей длины, ведущий из некоторой вершины S в некоторую вершину t. Для использования табличного представления многомерных матриц (пп. 1.4, 1.5) введем помечивание индексов C_i1,i1,,m1,ml. Алгоритм включает в себя 3 шага.

Предварительный шаг. В табличном представлении матрицы C столбец помечается знаком *. Диагональному элементу в столбце , т.е. , придается значение . Помеченные вершины будем относить к множеству R, непомеченные - к , т.е. S R.

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

h_m,l=C_{m,m +} C_m,l,

для чего входим в -строку и складываем диагональный элемент строки и элемент . Находим минимум , затем столбец l_i помечаем значением мультииндекса , а диагональному элементу столбца l_i придаем значение =. И так до тех пор, пока не пометим вершину t.

Заключительный шаг. Искомый путь определяем, двигаясь от t к S по отметкам вершин.

Рассмотренный алгоритм может использоваться для определения и наибольшего пути в многомерном ориентированном графе, если длину дуг C_i1,i1,,m1,ml взять условно со знаком минус, а длину отсутствующих в графе дуг, как и ранее при поиске кратчайшего пути, брать равной бесконечности. Поиск наибольшего пути требуется, например, в задачах расчета сетевых графиков. Он носит название критического пути [4].

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

3.5.2 Определение длин кратчайших путей между всеми вершинами графа одновременно

Пусть матрица указывает длину дуг графа с числом вершин N. Элементы главной диагонали матрицы всегда равны нулю. Если между парой вершин отсутствует ветвь, то соответствующий элемент принимается равным бесконечности. Очевидно, матрица расстояний c¹(1,1) неориентированного графа всегда симметрична относительно своей главной диагонали; для ориентированного графа она может быть несимметричной. Возведем матрицу c¹(1,1) в квадрат с²(1,1) = c¹(1,1) c¹(1,1), где элемент

с²_ij =

Интерпретируя умножение как последовательное, а сложение как параллельное соединение дуг, легко понять, что произведение соответствует двухтранзитному пути (т.е. пути, проходящему через две транзитные дуги графа) от вершины i к вершине j через узел k. При этом произведение (),() фактически соответствует однотранзитным путям (включающим только одну ветвь), так как длины путей c_ii и c_jj равны нулю. Для подсчета длины каждого из таких транзитных путей необходимо операцию умножения заменить операцией сложения, т.е. вместо будем иметь. Если же имеется несколько параллельных путей, то для определения длины кратчайшего пути между вершинами необходимо операцию сложения в формуле для определения c²_ij заменить операцией выбора из всех длин одно- и двухтранзитных путей наименьшей длины, т.е.

Таким образом, элемент c²_ij матрицы с²(1,1) равен длине кратчайшего пути от вершины i к вершине j среди всех одно- и двухтранзитных путей.

При возведении с¹(1,1) в r-ю степень при использовании указанных выше операций получим матрицу c^r(1,1) = c^r-1(1,1)c¹(1,1), элемент которой , будет равен длине кратчайшего пути от вершины i к вершине j среди всех однотранзитных путей и т.д. до r-транзитных путей.

При наличии в графе N вершин число транзитных дуг в пути без петель не может быть больше N-1. Для конкретной сети может оказаться, что при r < N - 1 выполняется условие

c^r(1,1) = c^r-1(1,1)c¹(1,1).

Тогда вычисление матрицы более высокой степени прекращается, так как при этом всегда выполняются равенства с^r+1(1,1) = c^r(1,1); c^N-1(1,1) = c^r-1(1,1). Матрица c^N-1(1,1) называется матрицей кратчайших путей. Рассмотренный способ позволяет определять длину кратчайшего пути, но не указывает дуги, которые входят в этот путь, однако в ряде задач такой информации бывает достаточно для принятия оптимального решения.

3.5.3 Решение задачи о кратчайшем пути в графе на основе линейного программирования [1,4]

Модель линейного программирования для задачи о кратчайшем пути строится следующим образом.Пусть X_ij ,d_ij представляют соответственно величину и стоимость потока по дуге (i,j). Тогда задача о кратчайшем пути в сети с N узлами формулируется как :

минимизировать Z=

при ограничениях

=1 (исходный пункт),

= (для всех к # 1 или N )

=1 (пункт назначения)

Целевая функция требует, чтобы общее ”расстояние”, пройденное единицей потока, было минимальным. Здесь принято, что =1,если дуга (i,j) принадлежит кратчайшему пути и =0, если дуга (i,j) не принадлежит кратчайшему пути.

3.6 Кратчайший остов графа

3.6.1 Понятие дерева

Одним из наиболее важных понятий теории графов является дерево. Его упрощенное определение можно дать так. Дерево - граф, имеющий начало, от которого дуги (ребра) расходятся, как ветви дерева [2]. Дерево, как и граф, может быть ориентированным и неориентированным.

Неориентированное дерево - это сильно связный граф, не имеющий циклов. (Понятие сильно связного графа дано в п.2.3.2).

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

3.6.2 Определение числа остовных деревьев графа

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

Определим число всех остовных деревьев для неориентированного графа. Пусть матрица M={m_ij} для неориентированного графа определена следующим образом: диагональный элемент m_ii есть число ребер, имеющих вершину x_i в качестве одной из концевых вершин, а элемент m_ij - число параллельных ребер между вершинами x_i и x_j со знаком минус. Число всех остовных деревьев равно определителю подматрицы, получающейся вычеркиванием одной строки и одного столбца из матрицы М.

Для ориентированного графа без петель (петлей называется дуга, начальная и конечная вершины которой совпадают) матрицу определим следующим образом: m_ii - число дуг, которые имеют своей конечной вершиной, вершину x_i т.е. заходят в x_i; m_ij = -k, где k есть число параллельных дуг из x_i в x_j. Тогда число ориентированных остовов с корнем x_r равно определителю подматрицы, полученной вычеркиванием r-й строки и r-го столбца из матрицы М.

3.6.3 Алгоритм построения всех остовных деревьев графа на основе полного перебора последовательностей ребер или дуг

Алгоритм можно представить в виде последовательности из 7 пунктов (этапов). Он справедлив как для неориентированных, так и ориентированных графов.

1. Все ребра (дуги) перенумеровываются от 1 до m, где m - число ребер (дуг) в графе.

2. Составляются различные перестановки последовательностей ребер (дуг), например, для трех ребер в графе последовательности

1 - d₁, d₂, d₃; 2 - d₁, d₃, d₂; 3 - d₂, d₁ d₃;

4 - d₂, d₃, d₁; 5 - d₃, d₁, d₂; 6 - d₃, d₂, d₁.

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

4. После каждого включения ребра (дуги) в дерево просматривается список «Пропущенное ребро». После использования в дереве пропущенного ребра (дуги) оно вычеркивается из списка «Пропущенное ребро». Ребро (дуга) вычеркивается из списка «Пропущенное ребро» также и в том случае, если пропущенное ребро (дуга) приводит к образованию цикла (для неориентированного графа) или к двум путям в вершину (для ориентированного графа).

5. Пункты 3,4 повторяются до тех пор, пока не будут просмотрены все ребра (дуги) данной последовательности. Для ориентированного графа необходимо убедиться, что полученное дерево есть остовное дерево графа, т.е. из вершины-корня достижимы все вершины графа.

6. Полученное остовное дерево сравнить с имеющимися и, если нет повторения, занести в память (список деревьев).

7. Если число остовных деревьев меньше максимального (п.3.5.2), то перейти к п.3.

3.6.4 Определение кратчайшего остова неориентированного графа на основе упорядочения ребер графа (алгоритм Прима-Краскала)

Такая задача возникает при прокладке дорог, газопроводов, линий электропередач и т.д., когда необходимо связать n точек так, чтобы общая длина «линий связи» была минимальной. Следует отметить, что «кратчайший остов графа» не имеет никакого отношения к дереву, дающему все кратчайшие пути, выходящие из некоторой выбранной вершины. Так, для графа (рис. 3.4), где числа, стоящие около ребер, являются их весами, дерево, дающее все кратчайшие пути, выходящие из вершины х₁, изображено на рис. 3.5, а кратчайший остов графа представлен на рис. 3.6.

X1

Рис. 3.4

X1

Рис. 3.5

Рис. 3.6

Итак, кратчайший остов графа связывает кратчайшим образом все вершины графа, а не только х₁ с другими вершинами.

Для построения кратчайшего остова с помощью алгоритма, изложенного в п. 3.5.3, необходимо в п. 2 сформировать последовательность ребер в порядке возрастания их весов.

3.6.5 Решение задачи о кратчайшем пути в графе на основе линейного программирования [1,4]

Рассмотрим решение задачи на примере исходного графа, изображённого на рис. 3.7. Необходимо для него сформировать минимальное остовное дерево.



Рис. 3.7 Исходный граф

Решать данную задачу, как задачу линейного целочисленного программирования. Для этого необходимо сформировать целевую функцию и ограничения, накладываемые на переменные.

Ограничения записываются следующим образом.

Для исходной вершины: ,

где все x_i выходят из исходной вершины, а N число вершин графа.

Для остальных вершин: сумма дуг (переменных), прилегающих к рассматриваемой вершине, равна единице, причём дуги, входящие в вершину, берутся со знаком “+”, а выходящие со знаком “”.

Вид целевой функции будет следующим:

,

где значения коэффициентов целевой функции С_i характеризуют стоимости потоков (рис. 3.7) .

На переменные x_i необходимо наложить условия неотрицательности и целочисленности.

Cистема ограничений и целевая функция для данной задачи имеют вид:

x₁ + x₂ + x₃ = 4

x₁ + x₅ x₄ = 1

x₂ x₅ x₆ + x₇ = 1

x₃ x₇ x₈ = 1

x₄ + x₆ + x₈ = 1

x_i 0

x_i целые

F = 2x₁ + 2x₂ + 3x₃ + 5x₄ + 4x₅ + 3x₆ + x₇ + 0x₈ min

Решение задачи имеет вид:

x1 = 1

x2 = 1

x3 = 2

x4 = 0

x5 = 0

x6 = 0

x7 = 0

x8 = 1

F_min = 10

В этом случае получаем граф оптимального решения, изображённый на рис. 3.8.



Рис. 3.8. Граф оптимального решения

Дуги, не принадлежащие остовному дереву, имеют поток по ним равным нулю (переменные X_i=0) .

3.7 Задача о назначениях

3.7.1 Матричная формулировка задачи

Задача о назначениях может быть сформулирована следующим образом: необходимо наилучшим образом назначить N работников { C₁, C₂,, C_N } на N работ {B_1, B_2,, B_N }. Наилучшим назначением считается такое, которое обеспечивает максимальную выработку суммарной продукции ( или минимальные затраты). Необходимая информация для решения задачи о назначениях содержится в квадратной матрице производительностей А={a_ij}, где a_ij - производительность i-го работника (машины) при выполнении j-ой работы. В случае минимизации затрат коэффициент a_ij означает затраты при выполнении i-ым работником (машиной) j-ой работы.

...