Навигация
Упорядочение элементов орграфа
24755
знаков
16
таблиц
8
изображений
3. Упорядочение элементов орграфа
Существенно повысить наглядность графа и упростить расчет его числовых характеристик позволяет процедура упорядочения его элементов. При упорядочении устанавливается порядок следования вершин или дуг. Вершина xBiB предшествует вершине xBjB, если существует путь из xBiBв xBjB. Другими словами, вершина xBiB- предшествующая («предок»), а вершина 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). Количество xBijBвещества, проходящего по ребру (i,j) в единицу времени, называется потоком по ребру. Считается, что если есть поток из вершины i в вершину j, то
xBijB = - xBjiB (1.1)
Если поток по ребру (i,j) меньше его пропускной способности, т.е. xBijB< rBijB, то ребро называют ненасыщенным, если xBijB= rBijB, - насыщенным. Совокупность X = {xBijB} потоков по всем ребрам называют потоком по сети или просто потоком.
Поток по ребру не может превысить его пропускной способности, т.е.
(1.2)
где n – количество вершин сети.
Приведем основное положение в теории потоков, которое называют условием сохранения потока: для любой вершины, кроме истока I и стока S, количество поступающего вещества в эту вершину, равно количеству вещества, вытекающего из нее. В промежуточных вершинах потоки не создаются и не исчезают.
Математическая запись этого ограничения с учетом формулы (1.1) следующая:
(1.3)
Отсюда вытекает, что общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.
(1.4)
где j – конечные вершины ребер, исходящих из I;
i – начальные вершины ребер, входящих в S.
Линейную функцию f называют мощностью потока на сети. Сформулируем задачу о максимальном потоке: найти множество XP* P= {xBijPB*P} потоков xBijPB *P по всем ребрам (i,j) сети, которое удовлетворяет условиям (1.1) - (1.3) и доставляет линейной функции (1.4) максимальное значение.
Как видно из формулировки, это типичная задача линейного программирования.
Обратимся к рис. 1.8, где изображена сеть. Для этой сети пропускную способность представим в виде матрицы, используя цифры в скобках. Здесь n = 6 и числа образуют квадратную матрицу шестого порядка (табл. 1.1). Если вершины k и l не соединены, то rBklB= rBlkB = 0. Сформировать матрицу чисел xBijB – это значит задать поток на сети, т.е. найти nP2 Pчисел, удовлетворяющих условиям (1.1) – (1.3). Рассмотрим полный путь 1 – 2 – 5 – 6.
Пропускная способность этого пути не больше 1 ед. и ограничивается ребром (2, 5), которое лежит на этом пути. Поток по этому пути мощностью в 1 ед. будет допустимым, и условии (1.1) – (1.3) должны выполняться для всех вершин и ребер этого пути.
Таблица 1.1
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 3 | 6 | 2 | 0 | 0 |
| 2 | 5 | 0 | 0 | 0 | 1 | 0 |
| 3 | 6 | 0 | 0 | 3 | 0 | 4 |
| 4 | 7 | 0 | 9 | 0 | 4 | 0 |
| 5 | 0 | 1 | 0 | 2 | 0 | 5 |
| 6 | 0 | 0 | 1 | 0 | 8 | 0 |
Рис. 1.8
Например, возьмем вершину 2 и проверим условие (1.3):
xB21B + xB25B = (-xB21B) + xB25B = (-1) + 1 = 0.
Похожие работы
... сети На сегодняшний день в мире существует более 150 миллионов компьютеров, более 80 % из них объединены в различные информационно-вычислительные сети от малых локальных сетей в офисах до глобальных сетей типа Internet Автоматизированное рабочее место «Отдел Кадров» является программой, активно использующей сетевое соединение отдельных компьютеров в локальную вычислительную сеть. Только при этом ...
... свойствами, делающими его необходимым для студентов, полезным для аудиторных занятий и удобным для преподавателей. Заключение Целью курсовой работы была разработка электронного учебного пособия на тему "Линейное программирование" средствами языка программирования PHP и СУБД MySQL. Для достижения поставленной цели были решены следующие задачи: изучить литературу по теме курсовой работы; ...
... профессором Н. Виртом, язык назван в честь французского математика и по замыслу автора предназначался для обучения программированию. Однако язык получился на столько удачным, что стал одним из основных инструментов прикладных и системных программистов при решении задач вычислительного и информационно-логического характера. В 1979 году был подготовлен проект описания языка – Британский стандарт ...
... Очень хорошая Хорошая Плохая Разводка кабеля Хорошая Удовлетворительная Хорошая Обслуживание Очень хорошее Среднее Среднее Древовидная структура ЛВС. На ряду с известными топологиями вычислительных сетей кольцо, звезда и шина, на практике применяется и комбинированная, на пример древовидна структура. Она образуется в основном в виде комбинаций вышеназванных топологий ...
0 комментариев