Студопедия

КАТЕГОРИИ:


Архитектура-(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)

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

Матричные способы задания графов. Упорядочение элементов орграфа

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

Определение 12.3. Матрицей инцидентности орграфа без петель с n вершинами и m дугами называется матрица, любой элемент которой определяется по следующей формуле:

Для неориентированного графа вместо «–1» ставится «1».

Пример. Для заданного ориентированного графа (рис. 12.10) построить матрицу инцидентности:

Рис. 12.10

Матрица инцидентности орграфа:

.

Определение 12.4. Матрица смежности вершин орграфа – квадратная матрица n -го порядка (n – число вершин). Строки и столбцы матрицы соответствуют вершинам графа. Элементы Sij матрицы равны числу дуг, направленных из i -й вершины в j -ю.

В случае неориентированного графа ему вместе с ребром (xi,xj) принадлежит и ребро (xj,xi), поэтому матрица будет симметрической.

Пример. Для заданного ориентированного графа (рис. 12.11) построить матрицу смежности вершин:

Рис 12.11

Матрица смежности вершин орграфа:

.

Определение 12.5. Матрица смежности дуг орграфа – квадратная матрица m -го порядка (m – число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы qij равны 1, если дуга ui непосредственно предшествует дуге uj, и нулю в остальных случаях.

Для неориентированного графа матрица смежности дуг симметрическая с элементами равными 1, если ребра имеют общую вершину, и 0 в остальных случаях.

Пример. Для заданного ориентированного графа (рис. 12.12) построить матрицу смежности дуг:

Рис.12.12

Матрица смежности дуг орграфа:

.

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

Определение 12.6. Вершина xi предшествует вершине xj, если существует путь из xi в xj, тогда xi называется предшествующей вершине xj, а xj – последующей за xi.

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

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

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

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

В результате упорядочения элементов получают граф, изоморфный данному.

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

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

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

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

Пример. Упорядочить вершины орграфа (рис. 12.13):

Рис. 12.13

Упорядочим вершины орграфа по алгоритму Фалкерсона (рис. 12.14):

Рис. 12.14

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

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

Определение 12.8. Максимальное количество rij вещества, которое может пропустить за единицу времени дуга, идущая из вершины xi в xj называется его пропускной способностью. В общем случае rij ≠ rji.

Определение 12.9. Количество xij вещества, проходящего через дугу из вершины xi в xj в единицу времени, называется потоком по дуге.

Предполагается, что если из вершины xi в xj направляется поток величиной xij, то величина потока из xj в xi равна – xij, то есть xji = –xij. (12.1)

Принимается также, что xii= 0. (12.2)

Определение 12.10. Совокупность X= { xij } потоков по всем дугам сети называется потоком по сети или просто потоком.

Поток по любой дуге не превышает его пропускную способность:

xij ≤ rij . (12.3)

Если xij<rij, то дугу между вершинами xi и xj называют ненасыщенной.

Общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, то есть мощность потока (12.4),

где j – конечные вершины дуг, исходящих из I; i – начальные вершины дуг, входящих в S.

Задача о максимальном потоке формулируется следующим образом: найти совокупность X*= { x*ij } потоков x*ij по всем дугам сети, которая удовлетворяет условиям (12.1) – (12.3) и максимизирует линейную функцию (12.4).

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

<== предыдущая лекция | следующая лекция ==>
Экстремальное дерево графа | Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
Поделиться с друзьями:


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


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



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




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