Решение задач по дискретной математике

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

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

Логические операции в порядке убывания приоритета

1.Инверсия (логическое отрицание) — логическая операция, которая данное высказывание преобразует в противоположное высказывание. Обозначается словами или символами: НЕ, NOT ,  , ¬, верхнее подчеркивание ().

Например: НЕ A , NOT A , ,   ¬ A .

2.Конъюнкция (логическое умножение) обозначается словами или символами: И, AND , &, ·, *, ˄, ∏, ∩.

Например : A И B, A AND B, A & B, A · B, A * B, A ˄ B, A ∏ B, A ∩ B.

∩ — математический знак, обозначающий пересечение.

3.Дизъюнкция (логическое сложение) обозначается словами или символами: ИЛИ, OR , +, ˅, U , ∑.

Например : A ИЛИ B, A OR B, A + B, A ˅ B, A U B.

U — математический знак, обозначающий объединение.

4.Импликация (если A, то B) обозначается символами: = > , →.

5.Эквиваленция ( A тогда и только тогда, когда B ) обозначается словами или символами: , ↔,

Приоритет логических операций

Порядок выполнения логических операций определяют круглые скобки и порядок логических операций. Сначала выполняется операция отрицания (“не”), за ней — конъюнкция (“и”), затем — дизъюнкция (“или”), затем — импликация (→) и в последнюю очередь — эквивалентность ≡.

Радиус, диаметр и центры графа

Эксцентриситет вершины графа — расстояние до максимально удаленной от нее вершины. Радиус графа — минимальный эксцентриситет вершин, а диаметр графа — максимальный эксцентриситет вершин. Центр графа образуют вершины, у которых эксцентриситет равен радиусу. Центр графа может состоять из одной, нескольких или всех вершин графа [Кирсанов М. Н. Графы в Maple. Задачи, алгоритмы, программы. — М.: Издательство ФИЗМАТЛИТ, 2007. — 168 с.].

Задача. Дан граф с заданным весом ребер

Найти радиус, диаметр и центры графа.

Заданы веса ребер, поэтому граф называется взвешенный. Программа на C ++ в Visual Studio 2013:

# include "stdafx.h" // Visual Studio 2013

# include "algorithm" // для min, max в Visual Studio 2013

# include "iostream" // Visual Studio 2013

using namespace std ;

const int N = 9 ; // Количество вершин в графе

const int INF = 100000 ; // Число большее длины любого пути в графе

>; // Дистанции (вес) в графе

int e [ N ]; // Эксцентриситет вершин

int c [ N ]; // Центры графа

int rad = INF ; // Радиус графа

int diam = 0 ; // Диаметр графа

for ( int k = 0 ; k N ; ++ k )

for ( int i = 0 ; i N ; ++ i )

for ( int j = 0 ; j N ; ++ j )

d [ i ][ j ] = min ( d [ i ][ j ], d [ i ][ k ] + d [ k ][ j ]);

for ( int i = 0 ; i N ; i ++) <

for ( int j = 0 ; j N ; j ++) <

e [ i ] = max ( e [ i ], d [ i ][ j ]);

// Нахождение диаметра и радиуса

for ( int i = 0 ; i N ; i ++) <

rad = min ( rad , e [ i ]);

diam = max ( diam , e [ i ]);

cout "Diameter: " diam endl ;

cout "Radius: " rad endl ;

for ( int i = 0 ; i N ; i ++) <

system ( "pause" ); // Visual Studio 2013

Остовные деревья

Остовное дерево неориентированного связного графа ( spanning tree ) G — его подграф, содержащий все вершины графа G и ребра графа G , не образующие циклы. Остов графа является деревом.

Задача. Построить все остовные деревья неориентированного графа из предыдущей задачи.

Алгоритм порождения всех каркасов неориентированного графа [Окулов С. М. Программирование в алгоритмах [Электронный ресурс] / С. М. Окулов.—5-е изд. (эл.).—М. : БИНОМ. Лаборатория знаний, 2014.—383 с.] реализован на C ++ в Visual Studio 2013:

using namespace std ;

const bool Zero = 0 ; // Ноль

const int N = 9 ; // число узлов графа

bool Nnew [ N ]; // признак, просмотрена вершина графа или нет

int Turn [ N ]; // очередь

int Tree [ 2 ][ N ]; // список ребер, образующих каркас

int Down ; // нижний указатель

int Up ; // верхний указатель

int numb ; // число ребер в строящемся каркасе

int AllTrees ; // Всего остовных деревьев

void Solve ( int v , int q ) // Номера вершин: v — из которой выходит ребро,

// q — начиная с которой следует искать очередное ребро каркаса

if ( Down >= Up ) return ;

while ( j N && numb N — 1 )

// Просмотр ребер, выходящих из вершины v

if ( A [ v ][ j ] != 0 && ! Nnew [ j ])

// Ребро включаем в каркас, так как вершина с номером j еще не в каркасе

Tree [ 0 ][ numb ] = v ;

Tree [ 1 ][ numb ] = j ;

Turn [ Up ] = j ; Up ++; // Включаем вершину j в очередь

Solve ( v , j + 1 ); // Продолжаем построение каркаса

// Исключаем ребро из каркаса:

Up —; Nnew [ j ] = false ; numb —;

if ( numb == N — 1 ) // вывод каркаса

AllTrees = AllTrees + 1 ;

cout "Tree N= " AllTrees endl ;

for ( i = 1 ; i numb ; i ++)

cout Tree [ 0 ][ i ] + 1 " " Tree [ 1 ][ i ] + 1 endl ;

/*Все ребра, выходящие из вершины с номером v, просмотрены.

Переходим к следующей вершине из очереди и так до тех пор,

пока не будет построен каркас.*/

Solve ( Turn [ Down ], 1 );

Nnew [ 1 ] = false ;

Turn [ 0 ] = 0 ; Down = 0 ; Up = 1 ; // в очередь первую вершину

for ( i = 0 ; i N ; i ++)

for ( k = 0 ; k N ; k ++)

cout " " A [ i ][ k ]; // Матрица смежности графа

Solve ( Down , Up );

cout "All trees: " AllTrees endl ;

cout "Press any key " endl ;

Конец выполнения программы:

Остов минимального веса. Алгоритм Крускала

Остовом минимального веса является остов, содержащий ребра с минимальным весом.

Алгоритм Крускала используется для построения графа минимального веса. Для этого к пустому графу на множестве вершин заданного графа G присоединяются ребра, выбирая всякий раз ребра минимального веса, не образующие циклов с ранее присоединенными ребрами.

Кодирование сообщения кодом, контролирующим ошибки ( d ≥ 3). Например, кодом Хэминга.

Передача по информационному каналу или хранение сообщения (могут появиться ошибки).

Читайте также:  Где хранятся закладки в мозиле windows 7

Оценка кодового слова и исправление ошибок при их наличии средствами контроля и исправления ошибок кода.

Выходное сообщение = исходному сообщению.

Пусть r – контрольные биты (разряды, символы, позиции), тогда

n = 2 r – 1 – длина кодовых слов,

k = 2 r – 1 – r = n – r – число информационных битов,

получаем ( n , k ) – код Хэмминга.

d – минимальное кодовое расстояние (число позиций, в которых отличаются любые два кодовых слова между собой), для кода Хэмминга d = 3.

( n , k ) – код с минимальным кодовым расстянием d можно назвать ( n , k , d ) – кодом.

Примеры кодов Хэмминга:

Граница Синглтона, названная в честь Сиглтона Р. К., устанавливает минимальное число контрольных символов в коде, контролирующем ошибки.

Код, содержащий алфавит из q элементов, называется q -ичным кодом. Если q = 2, то это двоичный код. Возможное число слов длиной n (мощность кода), составленных из q -ичного алфавита равно q n .

Пример двоичного кода, состоящего из 2 битов (разрядов, символов, позиций):

Если во всех словах кода убрать d – 1 символов, то оставщиеся n – ( d — 1) символы представляют слова, отличающиеся как минимум в 1 позиции. Мощность (максимальное количество слов) такого кода q n – ( d – 1) .

Информационные символы в коде занимают k позиций. Возможное число слов (мощность) длиной k равна q k . Для линейных кодов граница Синглтона:

q k ≤ q n – ( d – 1) .

q > 1 , следовательно

n — k — это количество добавочных контрольных символов кода, контролирующего ошибки.

Окулов С. М. Программирование в алгоритмах [Электронный ресурс] / С. М. Окулов.—5-е изд. (эл.).—М. : БИНОМ. Лаборатория знаний, 2014.—383 с.

Дискретная математика для школьников с алгоритмами на Паскале.

Калужнин Л.А. Что такое математическая логика? — М.: Наука, 1964. — 152 с.

Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. — М.: Вузовская книга, 2000. — 280 с.

Гиндикин С.Г. Алгебра логики в задачах. — М.: Наука, 1972. — 288 с.

Никольская И.Л. Математическая логика: Учебник. — М.: Высшая школа, 1981. — 127 с.

Зуев Ю.А. По океану дискретной математики: от перечислительной комбинаторики до современной криптографии. 2 тома. – М.: «Либроком», 2012.

Захарова Л.Е. Алгоритмы дискретной математики: Учебное пособие. – Моск. гос. ин-т электроники и математики. М., 2002, 120 с.

На Паскаль реализованы многие алгоритмы, графы. Имеется не большой список литературы, который полезно просмотреть.

Верещагин Н.К., Шень А. Лекции по математической логике и теория алгоритмов. Часть 1. Начала теории множеств. М.: МЦНМО, 1999. 128 с.

Хорошо представлена теория множеств, но некоторые значки не привычные.

Верещагин Н.К., Шень А. Лекции по математической логике и теория алгоритмов. Часть 3. Вычислимые функции. М.: МЦНМО, 1999. 176 с.

Кирсанов М. Н. Графы в Maple. Задачи, алгоритмы, программы. — М.: Издательство ФИЗМАТЛИТ, 2007. — 168 с.

Лаконично описана теория графов

Тюкарева М.Н. Метрические свойства графов. Дипломная работа. –Казань, 2014 — 32 с.

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

Альпин Ю.А., Ильин С.Н. Дискретная математика: графы и автоматы. Учебное пособие. — Казань: Казанский государственный университет им. В.И. Ульянова-Ленина, 2006. — 78 с

Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978, — 432 с.

Авиационные, ракетные и автомобильные двигатели. Гиперзвуковые, прямоточные, ракетные, импульсные детонационные, пульсирующие, газотурбинные, поршневые двигатели внутреннего сгорания — теория, конструкция, расчет, прочность, проектирование, технология изготовления. Термодинамика, теплотехника, газовая динамика, гидравлика.

Авиация, аэромеханика, аэродинамика, динамика полета, теория, конструкция, аэрогидромеханика. Сверхлегкие летательные аппараты, экранопланы, самолеты, вертолеты, ракеты, крылатые ракеты, аппараты на воздушной подушке, дирижабли, винты — теория, конструкция, расчет, прочность, проектирование, технология изготовления.

Генерация, внедрение идей. Основы научных исследований, методы генерации, внедрения научных, изобретательских, бизнес идей. Обучение приемам решения научных проблем, изобретательских задач. Научное, изобретательское, писательское, инженерное творчество. Постановка, выбор, решение наиболее ценных научных, изобретательских задач, идей.

Публикации результатов творчества. Как написать и опубликовать научную статью, подать заявку на изобретение, написать, издать книгу. Теория написания, защиты диссертаций. Зарабатывание денег на идеях, изобретениях. Консультирование при создании изобретений, написании заявок на изобретения, научных статей, заявок на изобретения, книг, монографий, диссертаций. Соавторство в изобретениях, научных статьях, монографиях.

Теоретическая механика (теормех), сопротивление материалов (сопромат), детали машин, теория механизмов и машин (ТММ), технология машиностроения, технические дисциплины.

Теоретические основы электротехники (ТОЭ), электроника, основы цифровой, аналоговой электроники.

Подготовка студентов по физике, математике, информатике, школьников желающих получить много баллов (часть C) и слабых учеников к ОГЭ (ГИА) и ЕГЭ. Одновременное улучшение текущей успеваемости путем развития памяти, мышления, понятного объяснения сложного, наглядного преподнесения предметов. Особый подход к каждому ученику. Подготовка к олимпиадам, обеспечивающим льготы при поступлении. 15-летний опыт улучшения успеваемости учеников.

Высшая математика, алгебра, геометрия, теория вероятностей, математическая статистика, линейное программирование.

Аналитическая геометрия, начертательная геометрия, инженерная графика, черчение. Компьютерная графика, программирование графики, чертежи в Автокад, Нанокад, фотомонтаж.

Логика, графы, деревья, дискретная математика.

OpenOffice и LibreOffice Basic, Visual Basic, VBA, NET, ASP.NET, макросы, VBScript, Бэйсик, С, С++, Делфи, Паскаль, Delphi, Pascal, C#, JavaScript, Fortran, html, Маткад. Создание программ, игр для ПК, ноутбуков, мобильных устройств. Использование бесплатных готовых программ, движков с открытыми исходными кодами.

Создание, размещение, раскрутка, программирование сайтов, интернет-магазинов, заработки на сайтах, Web-дизайн.

Информатика, пользователь ПК: тексты, таблицы, презентации, обучение методу скоропечатания за 2 часа, базы данных, 1С, Windows, Word, Excel, Access, Gimp, OpenOffice, Автокад, nanoCad, Интернет, сети, электронная почта.

Устройство, ремонт компьютеров стационарных и ноутбуков.

Видеоблогер, создание, редактирование, размещение видео, видеомонтаж, зарабатывание денег на видеоблогах.

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

Выбор, достижение целей, планирование.

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

Вы можете поддержать развитие сайта, оплатить консультационные услуги Ольшевского Андрея Георгиевича

Читайте также:  1С область ячеек табличного документа

В задачах 1–10, а) требуется, используя правила де Моргана, привести к ДНФ выражение, содержащее конъюнкции, дизъюнкции и отрицания, и затем сократить ДНФ, если это возможно. Для этих задач есть точный алгоритм решения: “понижение” отрицания по правилам де Моргана до тех пор пока они не окажутся над одной переменной. После этого раскрываем скобки (используя естественные свойства конъюнкций, дизъюнкций и отрицаний, а также поглощение) и затем сокращаем ДНФ по правилу Блейка.

Заметим, что часто в примерах приходится раскрывать скобки вида (х Ъу Ъ z ) ( x Ъ u ) . Здесь необходимо учитывать, что дизъюнктные слагаемые, содержащие х, поглощаются слагаемым х, поэтому после раскрытия скобок получится выражение x Ъyu Ъ zu.

Пример 1. Привести выражение к ДНФ, а затем сократить ее (если это возможно).

Решение. “Понижаем” отрицания по правилу де Моргана. Получаем По правилу Блейка (имеются дизъюнктные слагаемые, содержащие у и ) к последнему выражению можно добавить слагаемое x z , которое поглотит второе слагаемое в L.

Ответ: L = xy Ъxz

В задачах 1–10, б) надо просто применять правило Блейка, а затем уже правило поглощения

Теорию, применяемую к задачам 11–20, подробно обсуждали в разд. 3, 6, поэтому ограничимся решением примеров.

Пример . Дана ДНФ . Требуется для этой функции найти полином Жегалкина и перейти от ДНФ к КНФ, а затем и к СКНФ. Сначала найдем полином Жегалкина (вторым способом). Для этого ставим двойное отрицание и по правилам де Моргана “убираем” дизъюнкцию, потом “убираем” отрицания по правилу. После этого раскрываем скобки, учитывая при этом, что четное число слагаемых (по модулю 2) равно 0, а нечетное – одному такому слагаемому. Тогда

((x+1)(y+1)+1)(xy(z+1)+1)+1=(xy+x+y+1+1)(xyz+xy+1)+1=

Последнее выражение и является полиномом Жегалкина.

Для того чтобы перейти к КНФ для выражения L (в соответствии с разд. 3) ставим над L два отрицания и, оставляя временно верхнее отрицание без изменения, приводим оставшееся выражение к ДНФ. Затем по правилу де Моргана получаем КНФ. Таким образом, можем получить

.

Далее по правилу Блейка можем из последнего выражения исключить yz, тогда получим: . Это и есть КНФ.

Чтобы из последнего выражения получить СКНФ, нужно в первой и второй дизъюнкции добавить , а в третьей – Затем воспользуемся распределительным законом:

Последнее выражение и есть СКНФ.

Пример 2,б. Пусть имеется выражение . Требуется записать L в виде ДНФ, а затем перейти к СДНФ.

Ясно, что ДНФ можно получить простым раскрытием скобок. В обеих скобках есть , которое поглощает слагаемые, содержащие , поэтому . Это и есть ДНФ. Для того чтобы получить СДНФ, умножаем на , а умножаем на (y Ъ)и раскрываем скобки. Тогда

.

С самого начала надо позаботиться о правильном порядке переменных, что требуется для СДНФ, но последнее выражение еще не является СДНФ, так как содержит два одинаковых слагаемых. После уничтожения одного из них получим окончательный ответ:

Разберем пример решения задач типа 21–30.

Пример 3. Пусть требуется для функции

а) составить таблицу истинности;

б) написать для неё СДНФ или СКНФ (если это возможно);

в) сократить СДНФ по карте Карно;

г) найти по таблице истинности полином Жегалкина.

а) в таблицу истинности данной функции полезно включить таблицы истинности промежуточных функций:

б) составить СДНФ и СКНФ по полученной таблице. В соответствии с теорией разд. 4 СДНФ составляется по единицам таблицы истинности, причем если f(x, y, z) = 1, то если х = 0, в соответствующей конъюнкции СДНФ берется , а если х = 1 в СДНФ берется х. Аналогично поступают и с другими переменными, поэтому СДНФ для данной функции имеет вид:

.

СКНФ составляется по нулям таблицы истинности, т. е. если
f(x, y, z) = 0 и х = 0, то в соответствующей дизъюнкции берётся х, а если х = 1, то . Таким образом, СКНФ для данной функции имеет вид:

.

Заметим, что по определению СДНФ и СКНФ, переменные (в каждой конъюнкции и дизъюнкции соответственно) должны следовать в одинаковом порядке;

в) составим полином Жегалкина по таблице истинности. Напишем его сначала с неопределёнными коэффициентами:

Подставим в него по очереди все 8 наборов переменных и найдём коэффициенты полинома Жегалкина.

  • x = 0, y = 0, z = 0: a = 0;
  • x = 0, y = 0, z = 1: a 3= 1;
  • x = 0, y = 1, z = 0: a 2= 0;
  • x = 0, y = 1, z = 1: a 2+ a 3+ a 6= 1, a 6= 0;
  • x = 1, y = 0, z = 0: a 1= 1;
  • x = 1, y = 0, z = 1: a 1+ a 3+ a 5= 0, a 5= 0;
  • x = 1, y = 1, z = 0: a 1+ a 2 + a 4 = 1, a 4 = 0;
  • x = 1, y = 1, z = 1: a + a 1 + a 2 + a 3 + a 4 + a 5 +a 6 + a 7 =0.

Так как a =a 2 =a 4 =a 5 =a 6 = 0, тогда a 1 +a 3 +a 7 = 0, откуда a 7 = 0, и полином Жегалкина для данной функции имеет вид: f(x, y, z) = x+ z (для данной функции у является фиктивной переменной);

г) составим теперь для данной функции карту Карно и сократим её. Сначала составим таблицу:

Откуда f(x, y, z) =. Опять оказалось, что у – фиктивная переменная.

В задачах 31–40 требуется по карте Карно для функции 4 переменных составить сокращённую ДНФ. Надо иметь в виду, что карты Карно соединяются по кругу. Число единиц, которые можно объединять, равно 2, 4, 8, … (прямая, плоскость и т. д.)

Пример 4.

Получаем всего 4 объединения, т. е. 4 конъюнкции в ДНФ: f = (x1,x2, x3,x4) =

Заметим, что при правильно составленном объединении единиц правило Блейка может привести только к ДНФ с тем же числом символов переменных (в нашем примере их 11).

В задачах 41–50 требуется в данных наборах из 4 или 5 функций найти базисы и полные наборы функций (полные наборы – это наборы функций, содержащих базис).

(y z), 4) f4(x, y) = x + 5) f5 (x, y, z) = = x y Ъ z

Составляем таблицу истинности для каждой из этих 5 функций (для f2 и f4 таблицу можно составить отдельно).

(y z) = = x + yz + 1 – нелинейна;

f5 = x y Ъ z = = (x y + 1) z + 1 = x y z + z + 1 – нелинейна.

Читайте также:  Ag002a системы ess scr

Для f1 требуется проверка нелинейности. Составим полином Жегалкина для f1:

Для f2 и f4 составляем свои таблицы истинности.

В задачах 51–60 требуется по данному ориентированному графу составить структурную матрицу, а по ней (методами булевой алгебры) найти все пути из вершины i в вершину j, а затем (отрицанием этих путей) найти все сечения между двумя указанными вершинами. Пусть дан ориентированный граф (рис. 12) , причем ребра a,b,h являются ориентированными (их направление указано стрелками), а остальные ребра не ориентированы. Требуется методами булевой алгебры найти пути и сечения между вершинами 2 и 4.

Составляем структурную матрицу S, затем вычеркиваем из нее 4-ю строчку и 2-й столбец (тем самым получаем минор М(4,2)):

.

Раскрытие определителей производится по известному правилу: определитель равен сумме (в данном случае дизъюнкции) произведений элементов, умноженных на свои алгебраические дополнения (в данном случае просто миноры). При этом для определителей 3-го порядка можно пользоваться и правилом треугольника.

Искомые пути, расположенные в порядке прохождения ребер:

Сечения же получатся отрицанием этих путей. Применяя правила де Моргана (заменяя конъюнкцию на дизъюнкцию и наоборот), затем раскрывая скобки, получаем: (знаки отрицания опущены во всех равенствах, кроме 1-го):

= d (hЪ f)(cЪ e)(hЪ gЪ bЪ e)

или, применяя в скобках правило поглощения, получаемЪ

В индивидуальных заданиях 61–70 требуется найти в данной сети (т. е. в графе с заданными пропускными способностями ребер) максимальный поток из вершины с номером 1 в вершину с наибольшим номером (в заданиях либо в вершину 5, либо 6). В заданиях заданы 2 графа (граф, который находится слева, – это сеть с заданными пропускными способностями ребер, и граф справа с заданным потоком, который необходимо либо улучшить, либо доказать, что он не улучшаем и, значит, является максимальным). Конечно, можно дать задание просто найти максимальный поток между двумя вершинами. Однако при работе вручную нельзя дать большое число вершин (в наших заданиях это число равно 5 или 6), а в этих случаях максимальный поток можно найти без всякой теоремы Форда-Фалкерсона (просто из общих соображений). Поэтому задание в примерах 61–70 состоит в том, чтобы правильно расставить пометки для заданного потока, указанного в графе справа и после этого делать выводы о том, является ли этот поток максимальным или нет.

Задание в примерах 61–70 состоит в следующем: требуется, расставляя пометки в графе

с заданным потоком с помощью алгоритма, описанного в теореме Форда – Фалкерсона, найти максимальный поток между вершиной с номером 1 и вершиной с максимальным номером. При этом если улучшенный поток окажется максимальным, то нужно указать то минимальное сечение, которому равен наш поток (если же улучшенный поток не окажется максимальным, то нужно снова его улучшать до тех пор, пока он не окажется максимальным). На рис. 13а изображен граф с данными пропускными способностями ребер, при этом вершина номер 1 является “источником”, а вершина 6 – стоком. На рис. 13б изображен тот же граф, но на ребрах его задан поток, удовлетворяющий свойствам 1–4, который надо либо увеличить, либо доказать, что он является максимальным.

После этого подробно объясняем, как расставляются пометки в этом графе, и результат этого показываем на рис. 14. Для нового потока (рис. 14) снова расставляем пометки и убеждаемся, что этот поток является максимальным (рис. 15). Здесь же находим минимальное сечение, которому равен поток.

Начинаем расставлять пометки во втором графе (там дан поток).
1-я вершина (источник) всегда имеет пометку (Ґ ) (это означает, что второе число как угодно большое). Далее вторую вершину пометить пока нельзя, зато можно пометить вершину 4 и ее пометка будет (+1,25). Это означает, что дуга (1,4) прямая, ненасыщенная и по ней можно “перевезти” дополнительно 25 единиц “груза”. Далее вершину 5 пометить пока нельзя, но теперь можно пометить вершину 2 и ее пометка будет
(–4,20).

Это означает, что дуга (4,2) обратная, и, учитывая возможный “разворот” ее, по ней можно дополнительно “перевезти” 20 единиц “груза”. Так как 20 меньше 25, получаем данную пометку. Теперь можно пометить вершину 3 пометкой (+2,15) и, вершину 5, пометка которой будет (–3,15). (Заметим, что по дуге (5,3) с учетом разворота можно дополнительно “перевезти” 25 единиц груза, но так как для вершины 3 второе число было равно 15, то любое следующее число не может быть его больше). Только после этого можем пометить вершину 6 (сток), пометка которой будет (+5,15). Таким образом, наш поток можно увеличить на 15 единиц, прибавляя эти 15 единиц к прямым дугам и вычитая из обратных с учетом возможного “разворота” обратных дуг. Результат всех этих действий изображен на рис. 14.

Таким образом, получили новый поток, изображенный на рис. 15.

После этого для нового потока (рис. 15), снова расставляем пометки, которые также изображены на рис. 15. Мы видим, что для этого потока (кроме источника) можно пометить только 2 вершины: вершину 4 (ее пометка будет (+1,10)) и (после этого) вершину 2, пометка которой будет (+4,5). Больше ничего пометить нельзя, так как из множества помеченных вершин (Y) в множество непомеченных вершин (Z) идут только прямые, насыщенные дуги (дуги (2–3) и (4–5)). Эти две дуги образуют минимальное сечение, величина которого равна 30 условных единиц, и эта же величина равна величине потока. Заметим, что величина потока также равна “количеству груза”, вывозимого из источника, и равна количеству груза, ввозимого в сток. Таким образом, поток на рис. 15 является максимальным, а дуги (2–3) и (4–5) образуют минимальное сечение, которому равен наш поток.