Программирование на сетях

Рис.1.4

Рис.1.5

Граф G также может быть задан матрицей смежности дуг (ребер). Предположим, что некоторый граф имеет m дуг (ребер). Его матрица смежности дуг (ребер) представляет собой квадратную матрицу m-го порядка. Строки и столбцы матриц соответствуют дугам (ребрам) графа. Элементами pBij Bматрицы для ориентированного графа буду 1 и 0. Если дуга uB1 Bпрямо предшествует дуге BuBjB,B Bто pBij B= 1 и 0 – в остальных случаях. Матрица смежности ребер неориентированного графа своими элементами также имеет 1 и 0. Элемент pBijB = 1, если ребра uBi Bи uBj Bсмежные, и 0 – в остальных случаях.

3. Упорядочение элементов орграфа

Существенно повысить наглядность графа и упростить расчет его числовых характеристик позволяет процедура упорядочения его элементов. При упорядочении устанавливается порядок следования вершин или дуг. Вершина xBiB предшествует вершине xBj B, если существует путь из xBi Bв xBjB. Другими словами, вершина xBi B- предшествующая («предок»), а вершина xBjB – последующая («потомок»). Необходимо выявить группы вершин по следующим правилам:

1) вершины первой группы не имеют предшествующих, а вершины последней группы не имеют последующих;

2) вершины любой промежуточной группы не имеют предков;

3) вершины одной и той же группы дугами не соединяются.

Упорядочение дуг происходит по тем же правилами. Полученный в результате упорядочения граф является изоморфным исходному. Упорядочение элементов графа можно выполнить графическим или матричным способом. Графический способ упорядочения ведется по следующему алгоритму (алгоритм Фалкерсона).

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

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

Пример. Упорядочить вершины графа и построить граф, изоморфный данному.

Решение. Просматривая граф, замечаем, что вершина xB6B не имеет предшествующих, так как в нее не входит ни одна дуга. Эта вершина относится к первой группе. Подобных вершин в данном графе больше нет. Исключим из рассмотрения эту вершину и дуги, из них выходящие. На рис. 1.6 пометим их одной черточкой. В оставшемся графе снова ищем вершины, в которые не входит ни ода дуга. Таковыми будут xB4 Bи xB7B. Эти вершины образуют вторую группу. Обозначим второе вычеркивание двумя черточками. И так далее. На рис. 1.7 представлен упорядоченный граф. Вертикальными линиями показаны группы разбиения и на них отложены вершины, принадлежащие соответствующим группам. Далее эти вершины соединены, как на исходном графе.

Рис.1.6 Рис.1.7

4. Постановка задачи о максимальном потоке. Основные определения

К задаче о максимальном потоке сводятся многие важные оптимизационные задачи, например: задача об оптимальном назначении; различные задачи организации снабжения; задачи строительства энергетических сетей, нефте- и газопроводов, железных и шоссейных дорог и много других прикладных задач. В таких задачах схема доставки груза, или схема сообщения, представляется в виде графа, по ребрам которого проходят заданные потоки. Основным в теории потоков является понятие сети.

Сеть — это взвешенный граф без циклов и петель, ориентированный в одном направлении от вершины, называемой источником, к вершине, называемой стоком.

На рис. 1.8 представлена сеть. Истоком I является вершина 1, стоком S –вершина 6. Представим, что по ребрам (i,j) сети направляется некоторое вещество (ресурс, информация и т.п.). В скобках указаны пропускные способности ребер. Первое число- это пропускная способность в прямом направлении (от вершины i к вершине j) и второе – в противоположном направлении.

Пропускная способность - максимальное количество вещества rBijB, которое можно пропустить по ребру (i,j). Количество xBij Bвещества, проходящего по ребру (i,j) в единицу времени, называется потоком по ребру. Считается, что если есть поток из вершины i в вершину j, то

xBijB = - xBji B (1.1)

Если поток по ребру (i,j) меньше его пропускной способности, т.е. xBij B< rBijB, то ребро называют ненасыщенным, если xBij B= rBijB, - насыщенным. Совокупность X = {xBijB} потоков по всем ребрам называют потоком по сети или просто потоком.

Поток по ребру не может превысить его пропускной способности, т.е.

(1.2)

где n – количество вершин сети.

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

 Скачать реферат