- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
6.14. Потоки в сетях. Основные определения.
Если в графе ориентировать все ребра, то получится орграф, который называется направленным. Направленный орграф, полученный из полного графа, называется турниром.
Если в орграфе полустепень захода некоторой вершины равна нулю, т.е. d+(V)=0, то такая вершина называется источником, если же нулю равна полустепень исхода, т.е. d-(V)=0, то вершина называется стоком. Направленный орграф без петель с одним источником и одним стоком называется (двухполюсной) сетью.
Пусть G (V, E) – сеть, а S и t – соответственно источник и сток сети. На множестве дуг сети определена неотрицательная функция C: ER+, ставящая каждой дуге (u,v) неотрицательное вещественное число c(u, v), называемое пропускной способностью дуги (u, v).
Пусть задана функция f: ER. Дивергенцией функции f в вершине V называется число div(f,v), которое определяется следующим образом: div(f,v)= -
Функция f: ER называется потоком в сети G, если:
1) (u,v)E 0f(u,v)C(u,v)
2) vv\{s,t} div(f,v)=0
Число (f)=div(f,s) называется величиной потока f.
Замечание. Первое условие в определении потока означает, что поток через дугу неотрицателен и не превосходит пропускной способности дуги. Второе условие означает, что величина потока, входящего в каждую вершину сети (кроме истока и стока), равно количеству потока, выходящего из этой вершины.
С помощью потоков в сети можно моделировать:
1) автомобильные потоки на дорогах
2) перекачку нефти на нефтепроводе
3) последовательность технологических операций для производства готовых изделий из сырья.
4) передачу информации в компьютерной сети
В данной лекции рассматривается решение только одной (но самой существенной) задачи этой теории – нахождения максимального потока в сети.
Для решения этой задачи сеть разбивается на два непересекающихся множества таким образом, чтобы исток попал в одно множество, а сток – в другое. В этом случае говорят, что на сети произведен разрез, отделяющий исток от стока.
Пусть P – (s,t) разрез, PE. Всякий разрез определяется разбиением множества вершин V на два подмножества A и B так, что A,BV, AB=V, AB=0, sA, tB. Разрез обозначается P(A) и представляет собой множество дуг (U,V)E, таких, что UA, VB.
Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг C\A=
Минимальным разрезом, разделяющим исток s и сток t сети, называется произвольный разрез P(A) sA, tV\A с минимальной пропускной способностью.
Теорема Форда и Фалкерсона.
Величина каждого потока от входа к выходу не превосходит пропускной способности минимального разреза, разделяющего вход и выход сети. При этом существует максимальный поток, величина которого равна пропускной способности минимального разреза.
Все известные алгоритмы построения максимального потока основаны на последовательном увеличении потока.
Дуга (U,V) является допустимой, если для нее выполняется одно из условий:
направление дуги совпадает с направлением потока и значение потока по этой дуге меньше её пропускной способности f(U,V)<C(U,V)
направление дуги противоположно направлению потока и по ней проходит некоторый нулевой поток f(U,V)>0
Дуги, для которых выполняется условие 1), называются увеличивающими или согласованными дугами. Дуги, для которых выполняется условие 2) называются уменьшающими или несогласованными дугами.
Увеличивающей цепью называется простая цепь, соединяющая исток и сток сети, все дуги которой являются допустимыми.
Знание увеличивающей цепи позволяет увеличить поток по ней на величину = { (e)}, где (e)=
При этом по каждой увеличивающей дуге поток увеличивается на , а по каждой уменьшающей дуге уменьшается на .
Такое изменение потока по каждой дуге в сумме компенсируется для каждой вершины сети, отличной от истока и стока, т.е. для любой вершины сети vV\{s,t} по-прежнему будет выполняться div(f,v)=0.