Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины.
Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ 1°. Перенумеровать Произвольным Образом Вершины Сети ...
1°. Перенумеровать произвольным образом вершины сети , отличные от входа и выхода .
2°. Построить произвольный поток на транспортной сети (например, положить ).
3°. Просмотреть пути, соединяющие вход сети c выходом . Если поток полный, то перейти к пункту 4°. В противном случае рассмотреть путь , соединяющий с , все дуги которого не насыщены. Построить новый поток :
где . Повторить этот процесс до получения полного потока .
4°. Присвоить целочисленные метки вершинам сети и знаки «+» или «-» дугам по следующим правилам:
а) входу присвоить метку 0;
б) если вершина получила некоторую метку, а — еще непомеченная вершина, то вершине , такой что присвоить метку , а дуге— знак «+»; вершине , такой что , присвоить метку , а дуге— знак «-». Остальные непомеченные вершины и дуги метки и знака не получают;
в) повторить процесс, описанный в пункте 4°б) до тех пор, пока не прекратится появление новых отмеченных вершин и дуг. Если в результате процесса 4°б) вершина не получит метки, то поток обладает наибольшей величиной. В противном случае перейти к пункту 5°.
5°. Рассмотреть последовательность отмеченных вершин , каждая из которых имеет метку, равную номеру последующей вершины, и последовательность дуг и (не обязательно путь), соединяющих последовательные вершины из . Построить новый поток :
Перейти к пункту 4°.
2. Соотношение между величиной потока и пропускной способностью разреза сети.
Введем новые понятия теории транспортных сетей.
Определение 4: Пусть множество - такое множество вершин графа, что . Множество дуг, заходящих в , т. е. соединяющих вершины с вершинами, называется разрезом сети .
Определение 5:Пропускной способностью разреза называется сумма пропускных способностей дуг, входящих в разрез, т. е.
.
Лемма: Для любого потока и любого разреза справедливо соотношение:
.
Доказательство: В силу того, что выход сети , для величины потока справедливы соотношения:
.
Следствие: Если для некоторого потока и некоторого разреза выполняется равенство , то поток обладает наибольшей величиной.
Лемма и следствие необходимы для обоснования рассмотренного алгоритма.
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
(2 семестр)
(для студентов специальности «Прикладная математика», «Компьютерные системы и сети»)
У Т В Е Р Ж Д Е Н О
на
Основные комбинаторные формулы.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило умножения:
Пусть составляются всевозможные строки
Размещения.
1) Размещения без повторений.
Определение 2: Пусть имеется различных предметов.
Перестановки.
1) Перестановки без повторений.
Определение 3: Пусть - конечное множество из
Сочетания.
1) Сочетания без повторений.
Определение 3: Сочетания из элементов по
Свойства сочетаний. Бином Ньютона.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Рекуррентные соотношения.
При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок:
Производящие функции.
Метод рекуррентных соотношений позволяет решать многие комбинаторные задачи. Но в ряде случаев рекуррентные соотношения трудно составить, а иногда ещё трудней решить. Часто эти труд
Обоснование алгоритма.
Докажем, что после конечного числа применений правила 3° для каждой дуги графа станет справедливым неравенство
Алгоритм построения Эйлерова цикла.
Обратимся к задаче об эйлеровом цикле, уже рассмотренной нами в предыдущем параграфе. Пусть — связный граф, степени всех вершин которого — ч
Обоснование алгоритма.
Пусть мы находимся в некоторой вершине . В исходном графе степень вершины
Потоки на транспортных сетях.
1. Основная задача теории транспортных сетей.
Определение 1: Транспортная сеть есть совокупность
Обоснование алгоритма.
Прежде всего, заметим, что реализация алгоритма состоит из конечного числа шагов. В самом деле, п. 3° может применяться лишь конечное число раз, так как на каждом шаге величина пот
Цикломатическое число графа. Деревья.
Во многих прикладных задачах существенны свойства графов, связанные с существованием в графе замкнутых цепей (циклов). К рассмотрению этих вопросов мы и приступим. Все графы данного
Оценка хроматического числа плоского графа.
1. Теорема о пяти красках. Теорема утверждает, что любой граф, обладающий плоской реализацией, может быть правильно раскрашен пятью красками. Вспоминая задачу, сформулированную в нача
Графы правильных многогранников.
Теория графов позволяет решать задачи из традиционных разделов математики, например, исследовать некоторые свойства правильных многогранников. При этом, используя элементы теории гр
Автомат Мура.
Определение:Конечным автоматом называется набор из 5 объектов , где:
Морфизмы.
Пусть - конечный автомат. Тогда по любой входной строке длины
Машина Тьюринга.
Понятие конечного автомата возникло из близкого понятия, введенного в 1936 г. логиком Тьюрингом. Тьюринг рассмотрел гипотетическую машину, имеющую конечное множество
Примитивно рекурсивные функции.
Операции над числовыми функции назовем операторами. В этом параграфе мы определим ряд операторов, обладающих тем свойством, что, применяя их к функциям, вычи
Машины Тьюринга.
Важный и широкий класс алгоритмов был описан Тьюрингом и Постом в 1936 - 1937 г. Алгоритмы этого класса осуществляются особыми машинами, называемыми сейчас машинами Тьюри
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов