Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Сети и потоки на сетях. Постановка задачи о максимальном потоке




Матричное задание графа. Упорядочение вершин.

 

При большом числе вершин и дуг/ребер изображение графа теряет наглядность. В этих случаях для задания графов и работы с ними используют матрицы.

1. Граф без петель, имеющий n вершин и m дуг/ребер можно задать матрицей инциденций, строки которой соответствуют вершинам, а столбцы – дугам. Элементы матрицы, размерности nm, определяются по формуле

 

Для неориентированного графа вместо ”-1” ставится 1.

Пример.

 

2. Граф можно матрицей смежности вершин, строки и столбцы которой соответствуют вершинам графа. Элементы матрицы Sij равны числу дуг/ребер, идущих из хi в хj. Матрица смежности для неориентированного графа будет симметричной.

Пример.

 

 

Аналогично может быть задана матрица смежности дуг/ребер.

Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.

Если существует путь из хi в хj, то вершина хi называется предшествующей вершине хj, а хj – последующей хi.

Упорядочение вершин связного графа без контуров означает разбиение его вершин на группы так, чтобы:

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

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

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

 

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

 

1. Находятся вершины графа, в которые не входит ни одна дуга. Такие вершины образуют

1-ю группу.

2. Вершины и выходящие из них дуги установленной группы исключаются из дальней-

шего рассмотрения.

3. Устанавливается следующая группа вершин, в которые не входит ни одна дуга.

4. Если процесс упорядочения не окончен, то переход п. 2.

5. В полученном графе, изоморфном исходному, перенумеровываются вершины.

Пример.

 

 

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

Для наглядности представим, что по ребрам от истока к стоку направляется некоторое вещество (груз, ресурс, информация и т.п.).

Максимальное количество rij вещества, которое может пропустить за единицу времени ребро (i, j), называется его пропускной способностью. В общем случае rij ≠ rji. Если вершины не соединены, rij = 0. Т.к. нет петель, то rii = 0. Пропускную способность можно задать квадратной матрицей.

Количество хij вещества, проходящего по ребру (i, j) в единицу времени, называется потоком по ребру (i, j). Предполагается, что если из хi в хj направляется поток хij, то из xj в xi направляется поток (-хij)

xij = - xji. (1)

Поток по каждому ребру не превышает его пропускную способность

xij rij (i = ; j = ). (2)

Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из неё

(i I, S). (3)

Совокупность Х = потоков по всем рёбрам сети называют потоком по сети. Общее количество вещества вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.

F = xIj = xiS. (4)

Функцию F называют мощностью потока.

Если на сети задан поток Х = , то ребро (i,j) называется насыщенным, если поток xij по нему совпадает с его пропускной способностью rij (xij = rij), и ненасыщенным, если xij < rij.

Задачу о максимальном потоке можно сформулировать следующим образом: найти совокупность Х* = {x*ij} потоков x*ij по всем рёбрам сети, которая удовлетворяет условиям (1) – (3) и максимизирует линейную функцию (4). Это типичная ЗЛП.

Замечание. Не всякие n2 чисел могут задавать поток по сети. Только такие n2 чисел xij задают поток, которые удовлетворяют условиям (1) – (3).

Пример.

 




Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 581; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.