Дискретная математика (Конспекты 15 лекций)

Дискретная математика (Конспекты 15 лекций)

Московский государственный институт радиотехники, электроники и автоматики

(технический университет)

Лекции по

1 курс

Москва 2000

Лекция 1

Множество. Алгебра множеств.

Введем обозначения.

R – множество действительных чисел.

X e R – элемент X принадлежит множеству R.

Равные множества – множества, состоящие из одинаковых элементов.

A = B – множество А равно множеству B.

0 – пустое множество.

A П1 = x1x3 - ядровый

I2 = { 011 111} П2 = x2x3

Если координата вектора меняет значения, то переменная не входит

I3 = { 111 110} П3 = x1x2

_

I4 = { 110 100} П4 = x1x3

Dсокр. = П1 V П2 V П3 V П4

Nf = I1 U I4 U I2 (U – объединение)

Получили неприводимое покрытие, добавив к ядру недостающие интервалы так,

чтобы все единичные вершины были задействованы.

D1= П1 V П4 V П2

Nf = I1 U I4 U I3

D2= П1 V П4 V П3

Сосчитаем ранги тупиковых ДНФ

R1 = 6

R2 = 6

Dmin = D1 = D2

Метод карт Карно для нахождения минимальной ДНФ

n = 4

Карта Карно – плоскостная интерпретация 4-мерного булева куба.

| |00 |01 |11 |10 |

|00 | |0001| | |

|01 |0100|0101|0111 |0110|

|11 | |1101| | |

|10 | | | | |

Считаем, что левый край склеен с правым, а верхний – с нижним.

Если таблицу Карно свернуть таким образом, то получится тор (torus -

геометрическая фигура, напоминающая бублик).

Правила поиска интервалов.

1. Интервалом ранга 1 могут быть 2 соседних строки (2 соседних столбца)

2. Интервалом ранга 2 может быть вся строка, весь столбец или квадрат 2х2.

3. Интервалом ранга 3 – любые 2 соседние по горизонтали и вертикали клетки.

4. Одна отдельно взятая вершина будет интервалом ранга 4.

Алгоритм – тот же самый.

Лекция 6

Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ

Этот метод удобен для нахождения минимальной ДНФ функции от любого числа

переменных.

Определение. Элементарная конъюнкция K1 покрывает ЭК K2, если каждая

переменная, входящая в K1, входит и в K2.

__ __ __

X1X3 – покрытие X1X2X3X4

Nk1 ? Nk2

K2 = K1K

K – конъюнкция из других переменных.

__ _ _ __ _ _

X1X3 V X1X2X3X4 = X1X3 (1 V X2X4) = X1X3 – поглощение

Склеивание двух ЭК

_

Kx V Kx = K

Идея метода Квайна (алгоритм)

1. Выписываются все элементарные конъюнкции из СДНФ функции.

2. Проводятся все возможные склеивания между этими ЭК. Полученные новые ЭК

сохраняются вместе со старыми.

3. Между ними снова проводим все возможные склеивания до тех пор, пока это

возможно. В результате среди ЭК появятся все простые импликанты функции.

4. Проводим поглощение между всеми получившимися ЭК, то есть оставляем

только те ЭК, которые не покрываются никакими другими.

5. В результате получаются только простые импликанты. Их дизъюнкция

является сокращенной ДНФ. Дальше все идет в соответствии с тривиальным

алгоритмом минимизации.

Формализация Мак-Клоски.

Каждой ЭК ставим в соответствие булев вектор. (x с отрицанием – 0, без

отрицания – 1).

1. Выписываем все ЭК из СДНФ функции в формализованном виде в столбец,

располагая их в порядке возрастания числа единиц в векторах и разбивая на

классы по числу единиц.

2. Между ЭК проводим все возможные склеивания. Результат записываем в новый

столбец справа, а ЭК, участвовавшие в склеивании, помечаем звездочкой.

Склеивать можно только ЭК из соседних классов.

3. Для полученного столбца еще раз применяем шаг 2.

4. Все ЭК, которые остались непомеченными звездочкой, являются простыми

импликантами.

5. Строим таблицу Квайна по следующему правилу:

А) Каждой строке ставим в соответствие простую импликанту Пi.

Б) Каждому столбцу – ЭК из СДНФ Kj.

6. Если Пi.покрывает Kj , то в соответствующей клетке ставим знак +.

7. Ищем ядровые импликанты (столбец, содержащий только 1 знак +). Та строка

и есть ядровая (строка, в какой этот крестик содержится).

8. Строим сокращенную таблицу (Вычеркиваем ядровые строки, а затем –

столбцы, где есть вычеркнутые крестики).

9. Ядро дополняем до тупиковой ДНФ (Ищем минимальную комбинацию строк так,

чтобы в каждый столбец входил хотя бы один крестик). Дизъюнкция этих

строк даст тупиковые ДНФ.

10. Среди всех тупиковых ДНФ выбираем минимальную.

Лекция 7

Функционально полные системы функций

Определение. Система функций ? ’ {f1…fn} называется полной, если любую

булеву функцию можно представить в виде суперпозиции функций из этой

системы (т.е. можно представить формулой, куда входят только функции из

этой системы).

?? ’ F?

? ’ {V, &, NOT или отрицание - --}

Теорема 1.

Если система ?1 полна, и любая ее функция представима в виде суперпозиции

функций из системы ?2, то и система ?2 также полна.

Доказательство

?1’ {ф1…фk}

??i ’ Е?2 - условие.

?f ’ F?1 = F?2 – ч.т.д.

Мы заменили все функции суперпозицией из ?2.

Теорема 2.

Если система функций полна, то будет полной и система, состоящая из

двойственных функций.

Доказательство следует из принципа двойственности.

Основные типы функционально полных систем.

? ’ {&, V, NOT}

? ’ {&, NOT}

____

_ _

X V Y = (XY)

? ’ {/} – полна.

___

X/Y = (XY)

X/X = NOT(XX) = NOT(X)

? = {v}

Система Жегалкина {+,&,1}.

NOT (X) = x+1

X V Y = xy+x+y

Многочлены Жегалкина.

Одночленом будем называть любое выражение вида

А * X1X2X3…Xn

A = {0 или 1} x1x3 – одночлен.

Многочленом Жегалкина называется сумма по модулю 2 различных одночленов.

А1X1+А2X2+А3X3+A4X1X2 + A5X1X3+A6X2X3+A7X1X2X3 – общий вид многочлена

Жегалкина для трех переменных. Чтобы выписать общий вид многочлена

Жегалкина для нужного числа переменных нужно перебрать все возможные

конъюнкции переменных и сложить их по модулю 2 друг с другом, а также с

переменными, входящими в функцию. Перед каждой конъюнкцией нужно расставить

буквенные коэффициенты.

Теорема

Любая булева функция, тождественно не равная нулю, представима и притом

единственным образом в виде многочлена Жегалкина.

Доказательство на лекции 8.

Поиск многочлена Жегалкина (МЖ) для любой выбранной булевой функции

производится методом неопределенных коэффициентов. Для этого нужно выписать

общий вид МЖ для нужного числа переменных, затем, подставив искомые

значения переменных в МЖ, приравнять его к функции на нужном векторе. Таким

образом получается система уравнений с неизвестными числами А. Решив ее,

мы получим искомый МЖ.

Лекция 8

Продолжение темы «Многочлены Жегалкина»

Теорема.

Любая булева функция представима в виде многочлена Жегалкина (МЖ).

Доказательство

1. Существование

F = ДНФ = F{&,V, NOT}

X V Y = XY+X+Y

NOT(X) = X+1

Из этого следует, что функция представима в виде МЖ.

2. Единственность

Сосчитаем МЖ

ЭК без отрицания 2n – 1 + 1

Всего разных многочленов Жегалкина 2N – 1, где N = 2n

Это число совпадает с числом разных булевых функций, отличных от нуля.

Отсюда следует, что любой булевой функции соответствует единственный

многочлен Жегалкина. Теорема доказана полностью.

Классы функций. Замкнутые и незамкнутые классы. Получение констант и

элементарных булевых функций из заданной системы функций

Определение. Функция называется линейной, если ее многочлен Жегалкина не

содержит ни одной конъюнкции переменных.

Замкнутые классы функций.

Определение.

Пусть дан класс функций B (т.е. конечное или бесконечное множество

функций),объединенных по общему признаку. Замыканием этого класса

(обозначение – [B]) будем называть множество всех суперпозиций функций из

класса B.

Класс B будем называть замкнутым, если его замыкание совпадает с ним самим.

B = [B]

Теорема 1

Класс всех линейных функций замкнут.

Доказательство.

Пусть L – класс линейных функций (так и будем обозначать в дальнейшем).

L = {a0+a1x1+a2x2+…+anxn}

Подставим вместо переменной x в одну из функций функцию y такого же вида.

Получим

L = [L].

Утверждение (теорема 2)

Необходимое условие линейности.

Если функция линейна и не равна некоторой постоянной, то на половине своих

наборов она равна 1.

Если в векторе значений функции число 0 и 1 различно, то функция

обязательно нелинейна, а если число нулей совпадает с числом единиц, то эта

функция может быть линейной, а может быть и нелинейной. В таком случае,

чтобы это проверить, нужно выписать для нее многочлен Жегалкина.

Функция называется самодвойственной, если двойственная к ней функция

является самой этой функцией. F* = F.

S – класс всех самодвойственных функций.

Класс S является функционально замкнутым.

Доказательство следует из принципа двойственности.

У самодвойственной функции на противоположных наборах противоположны

значения.

Функция называется монотонной, если из условия ? ? ? следует, что f(?)) ?

f(?)).

Теорема.

Класс M монотонных функций замкнут.

Свойство.

У монотонных функций сокращенная ДНФ не содержит отрицаний переменных, то

есть все простые импликанты не содержат отрицаний.

Другие замкнутые классы

T0 – константа 0 (класс функций, обращающихся на нулевом векторе в 0).

Т1 – константа 1) (класс функций, обращающихся на единичном векторе в 1)

Теорема

Классы Т0 и Т1 функционально замкнуты.

Лемма о несамодвойственной функции.

Если функция несамодвойственна, то путем подстановки вместо аргументов

переменной x или not(x) можно получить константу.

011 – нарушена самодвойственность

f(not(x),x,x) = const = 1 при любом x.

001 – нарушена самодвойственность

Если 0, то х с отрицанием, если 1, то без отрицания.

Доказательство _ _ _ _ _ _

_ _

F ? S ? ?? : F*(?)) ? F(?)) ? F*(?)) = F(?))? F(?)) = F(?)) ? F(?)) =

F(?)

?((x) = {x1?1, x2?2, … xn?n}

?((0) = {0?1, 0?2, … 0?n}

Путем подстановки получаем, что ?((x) = const.

Лемма о немонотонной функции

Путем подстановки вместо аргументов-констант и переменной х можно получить

not(x).

000 ? 001

F(000) = 1 F(001) = 0

F(00X) = NOT(X)

F(100) = 1

F(110) = 0

100 < 110

F(1,x,0) = NOT(X)

Лемма о нелинейной функции

Если F(X) нелинейна, то из нее путем подстановки вместо аргументов-констант

переменных (x, y, not x, not y) иожно получить: конъюнкцию этих переменных,

дизъюнкцию этих переменных, отрицание конъюнкции, отрицание дизъюнкции.

F = 1 + x1+x3+x1x3+x1x2x3 = x1x3(1+x2) +x3+x1+1

F(x1,0,x3) = x1x3+x3+1

___

F(x0y) = (xy)

Лекция 9

Доказательство леммы 3

F(x1…xn) = x1x2 (f1(x1…xn)) + x1f2(x1…xn) + x2f3(x1…xn) + f4(x1…xn)

Вместо x1…xn ставим константы ?1…?n, такие, что

f1(?1…?n) = 1

1. A = B = 0

F(x1x2…?3…?n) = x1x2 + C = {x1x2, если с = 0 и NOT(x1x2, если с = 1)

Аналогично получаем дизъюнкцию и ее отрицание.

Теорема Поста.

Система функций полна тогда и только тогда, когда она не находится ни в

одном из пяти важнейших замкнутых классов, а именно S, M, L, T0, T1.

1. Необходимо.

Дана полная система функций. Отсюда следует, что она не принадлежит

никакому замкнутому классу (см. выше).

Доказательство следует из того факта, что по определению и по тому, что мы

доказали, что все важнейшие классы замкнуты. Если предположить, что система

целиком входит в один из замкнутых классов, то

[?] = [B] = B

Но ? - множество всех булевых функций, а B – не всех.

Получили противоречие.

Доказательство дано в виде алгоритма получения из системы ? основных

элементарных булевых функций, образующих полную систему, значит и эта

система будет полна.

Дано

? ? {S, M, L, T0, T1}

Каждая функция (f с индексами 1…5) не принадлежит каждому соответствующему

ей важнейшему замкнутому классу.

1. Получение констант.

F1(00…0) = 1

a) F(111) = 1

b) F(111) = 0

F(xxxx) = 1

F2(111) = 0

2. Получение отрицаний

Из F4 по лемме 2 мы можем получить отрицание.

3. Используя F5 по лемме 3 получаем xy, x V y, not(xy), not(x V y)

Лекция 10

Функциональные элементы. Схемы

Функциональный элемент с n упорядоченными входами и одним выходом

.

При подаче на выходы любой комбинации двоичных сигналов, на выходе также

возникает сигнал.

Каждый вход – аргумент функции.

Выход – булева функция от аргументов.

Из функциональных элементов можно строить по правилам их соединения схемы

(логические сети).

Два и более входов можно отождествлять.

Возможные соединения функциональных элементов соответствуют булевым

функциям и их суперпозициям.

Полный набор булевых функций, который мы будем использовать для построения

логических сетей (схем) в какой-нибудь задаче, мы назовем базисом из

функциональных элементов.

Число функциональных переменных считаем сколь угодно большим.

Базис называется полным, если с его помощью можно реализовать любую булеву

функцию в виде схемы.

Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система

функций, реализуемых элементами базиса, была полной.

Пример полного базиса.

- Конъюнктор

- Дизъюнктор

- Инвертор

Чтобы построить минимальную функциональную схему для функции на

конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию,

нужно

1. Найти минимальную ДНФ.

2. Для любой из минимальных ДНФ (их может быть много) попробовать упростить

формула с помощью вынесения за скобки общего множителя.

Сумматор n-разрядных двоичных чисел

Составить элементы с 2n входами и n+1 выходом, реализующих сложение n-

разрядных двоичных чисел вида

X = XnXn-1…X1

Y = YnYn-1…Y1

Z = x+y = Zn+1Zn…Z1

X+Y – сумма чисел.

Для решения такой задачи вводим qi – единица переноса из одного разряда в

другой.

Формулы сумматора

Zi = Xi + Yi + Qi – сумма по модулю 2

Qi+1 = XiYi V XiQi V QiYi

Лекция 11

Графы

Графом (G) будем называть тройку объектов (V, X, ?))

V – множество n вершин.

X – конечное множество ребер.

? - функция инцидентности, которая каждому элементу множества X ставит в

соответствие пару элементов из множества V.

? задана на множестве X.

Если в значении функции инцидентности допускается перестановка вершин, то

граф называется неориентированным. В противном случае граф называется

ориентированным (Орграф).

Vj – начало ребра

Vk – его конец

?(xi) = (Vj, Vk) – ребро инцидентно в вершине Vj и в вершине Vk.

Если одной и той же паре вершин инцидентно несколько ребер, то ребра

называются кратными.

Если на ребре xi0

?((x0) = (Vj0, Vj0),

то ребро называется петлей.

Способы задания графов

1. Аналитический

Если вершине не инцидентно никакое ребро, то эта вершина называется

изолированной.

Выписываются все ребра и пишутся напротив две пары вершин, которым они

инцидентны.

В конце выписываются все изолированные вершины.

2. Геометрический

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин –

кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то

их надо отличать от вершин.

3. С помощью матрицы инцидентности

A(m*n)

m = [V] – число вершин

n = [X}- число ребер

а) Неориентированные графы

Aij = {0, если Vi не инцидентно xj, 1, если Vi инцидентно xj)

б) Орграфы

Aij = {0, если Vi не инцидентно xj, -1, если Vi - начало xj, 1, если Vi -

конец xj)

Для петель нужны дополнительные предположения.

4. Матрица смежности (задается одинаково для всех графов)

B(m*m) m = [V]

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична.

Граф, в котором нет кратных ребер и петель, называется простым.

Простой граф называется полным, если любой паре его вершин инцидентно одно

ребро.

Дальше все о неориентированных графах.

K1 – полный граф с одной вершиной

K2 – с двумя

K3 – с тремя

K4 – полный граф с четырьмя вершинами

K5 – полный пятивершинник

Граф называется двудольным, если множество вершин разбивается на 2

непересекающихся подмножества, такие, что ребра соединяют вершины из разных

подмножеств.

Двудольный граф называется полным, если каждая вершина одного подмножества

соединена ребром с каждой вершиной другого подмножества.

Полный двудольный граф.

Маршруты, циклы, связности.

Маршрутом в графе называется чередующаяся последовательность вершин и

ребер, начинающаяся и заканчивающаяся вершинами, такую, что каждое ребро в

нем соединяет только те вершины, между которыми оно стоит.

Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если

существует маршрут, то последняя вершина называется достижимой из первой

вершины.

Маршрут, в котором нет повторяющихся ребер, называется цепью.

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней),

называется простой цепью.

Если в простой цепи первая и последняя вершины совпадают, то она называется

циклом.

Граф называется связным, если любая вершина достижима из любой другой

вершины. В противном случае граф называется несвязным. Несвязный граф

распадается на несколько частей, каждая из которых является связным графом.

Эти части называются компонентами связности.

Ребро называется циклическим, если оно входит хотя бы в один цикл графа. В

противном случае ребро называется ациклическим.

Утверждение.

Если из связного графа удалить циклическое ребро, то вновь полученный граф

останется связным, а если удалить ациклическое ребро, то граф распадется на

два компонента связности.

Связный граф, у которого все ребра ациклические, называется деревом.

Несвязный граф, компонентами связности которого являются деревья, лесом.

Свойства деревьев.

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы

число вершин было больше числа ребер на один.

2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины

его соединялись единственным маршрутом.

3. Граф будет деревом тогда и только тогда, когда добавление любого нового

ребра приводит к появлению ровно одного цикла.

Лекция 12

Эйлеровы графы

Дан граф. Требуется найти в нем маршрут, проходящий по каждому ребру ровно

один раз. Начало и конец – в одной вершине.

Такой маршрут называется Эйлеровым циклом, а граф, в котором он существует,

называется Эйлеровым графом.

Степень вершины в графе – это число ребер, инцидентных этой вершине.

Критерий эйлеровости графа.

Для того, чтобы связный граф без петель был Эйлеровым, необходимо и

достаточно, чтобы степень его вершины была четным числом.

Планарные графы.

Определение.

Укладкой графа называется такое его геометрическое изображение, при котором

ребра пересекаются только в вершинах. Если существует укладка графа на

плоскости, то граф называется планарным.

Сама же укладка графа без пересечения ребер называется плоским графом.

Любой граф можно изобразить в трехмерном пространстве без пересечения

ребер.

Для любого графа xi, соединяющего 2 вершины проводим новую плоскость,

содержащую эту прямую, а ребро рисуем на плоскости.

Граф будет планарным, если существует его укладка на сфере.

Доказательство следует из взаимно однозначного соответствия точек на сфере

с точками плоскости из стереографических проекций.

Следствие. Граф любого выпуклого многогранника планарен.

Ребра плоского графа разбивают плоскость на несколько частей, одна из

которых бесконечна. Эти части и являются гранями плоского графа.

Теорема Эйлера о плоских графах.

Формула Эйлера.

Для плоского графа справедливо соотношение.

M – N + P = 2.

Докажем индукцией по числу граней

P = 1

Если P = 1, то граф – дерево. В нем нет ни одного цикла. У дерева число

вершин больше числа ребер на 1.

M = N + 1

N + 1 – N + 1 = 2 – справедливо.

Пусть p = k, и утверждение верно.

Тогда оно верно и при P= k+1

Берем ребро графа, отделяющее бесконечную грань от внутренних и удаляем это

ребро из графа. Т.к. оно циклическое, то в новом графе g1 (он также будет

связным) число вершин M останется прежним.

N1 = N – 1

P1 = P – 1

M = M

k + 1-1 = k

Для g1 справедливо предположение индукции.

M1 + N1 + P1 = 2

M – N – 1 + K = 2

M – N + K – 1 = 2

M – N + P = 2

Что и требовалось доказать.

Следствие 1.

Для плоского связного простого графа справедливо соотношение

n 2

И если бы он был плоским, то для него было бы справедливо следствие 1.

N L(Vi, Vj) *

Если это неравенство выполняется, то меняем метку ?j на новую.

?j = ?i + L(Vi, Vj) и так до тех пор, пока выполняется *.

Если * нигде не выполняется, то та метка, которая будет стоять у вершины В

и будет равна длине минимального пути из А в В, а сам путь строится

движением назад из В в А.

Г-1(В) Существует такое ребро Vi1, для которого выполнено равенство.

?b - ?i1 = L(Vi1,B)

Затем Г-1(V1) Существует V2, где ?(V1) - ?(V2) = L(V1, V2) и т.д. пока не

вернемся в вершину А.

Путь минимальной длины найден.

Остов графа минимальной длины.

Остов – дерево, содержащее все вершины графа и какие-то из его ребер.

Если каждому ребру графа поставлена в соответствие его длина, то требуется

найти такой остов, сумма длин ребер которого минимальна.

Алгоритм

1. Перенумеруем все ребра графа в порядке возрастания их длин.

2. Просматриваем ребра, начиная с первого. Если x1 не является петлей, мы

его включаем в остов и переходим к следующему ребру. Если оно не является

петлей и не образует с уже имеющимися ребрами цикла, мы его включаем в

остов. И так до тех пор, пока не рассмотрим все ребра.

Остов минимальной длины найден.

Лекция 14

Парное сочетание (паросочетание) двудольных графов

Двудольным графом называется граф, у которого множество вершин можно

разбить на два непересекающихся подмножества так, что ребра соединяют

вершины из разных подмножеств.

Паросочетанием в двудольном графе называется любое множество попарно

несмежных ребер (у них нет общих вершин).

Паросочетание называется максимальным для данного графа, если оно содержит

наибольшее число ребер для всех возможных паросочетаний.

Паросочетание называется совершенным (из множества v в множество w), если

число ребер в нем совпадает с числом вершин в подмножестве c.

Для любого подмножества S через ф(S) обозначим те вершины из множества w,

которые соединяются ребрами с вершинами подмножества S.

Теорема Холла (без доказательства)

Для того, чтобы в двудольном графе существовало совершенное паросочетание,

необходимо и достаточно, чтобы для любого подмножества S из множества V

выполнялось условие [S] ф(S).

Ищем это подмножество.

Для каждой вершины Vi из S метку Ai уменьшают на 1, а для wj из ф(s) метку

Vj увеличивают на 1.

5. Переходим на начало шага 2 с новыми значениями меток.

Лекция 15

Потоки в транспортных сетях

Введем обозначения

V – вершина орграфа

M-(V) – множество ребер, для которых вершина V является концом.

M+(V) – множество ребер, для которых вершина V является началом.

Транспортной сетью называется связный орграф без петель, для которого

выполнены следующие условия

1. Существует только одна вершина A, для которой M-(А) – пустое множество.

А – исток.

2. Имеется только одна вершина B, для которой M+(B) – пустое множество. В –

сток.

3. Каждому ребру графа поставлено в соответствие целое неотрицательное

число, называемое пропускной способностью данного ребра.

2(1) 3(1)

1(1)

6(0)

5(5)

1(1) 4(1)

2(1)

Потоком в транспортной сети (ТС) называется целочисленная функция,

определенная на любых ребрах ТС и удовлетворяющая следующим свойствам

1. ф(X) 0 в новом графе g* заменяются двумя

ребрами x* и x**. Ребро x* направлено в ту же сторону, что и x, и

пропускная способность c(x*) = c(x) – ф(x).

Ребро x** направлено в противоположную сторону ребру x, и пропускная

способность c(x**) = ф(x).

Ребра с нулевой пропускной способностью можно не рисовать.

3. В графе g* ищем путь из А в В по ребрам с ненулевой пропускной

способностью. Если его нет, то имеющийся поток является максимальным и

алгоритм закончен. Иначе переходим к пункту 4.

(Этот путь называется увеличенной цепью. ? ’ min(c(x)) – минимальное

значение пропускной способности этой цепи).

4. Меняем значение функции потока в графе g для тех ребер, которые

соответствуют найденному пути в графе перестроек по следующему правилу:

Если направление ребра x в графе g совпадает с направлением пути, то новое

ф(x) = ф(x) + ?

Если же направление противоположно направлению пути, то ф(x) = ф(x) - ?

5. Переходим на шаг 2 с новым потоком.

-----------------------

0 1

00

01

10

11

000

100

110

001

010

011

111

101

Логическое умножение

Логическое сложение

F

&

V

__

Полюса

Not Z

Пересечение множеств

Объединение множеств

Дополнение множества