Материал: Ответы на экзаменационные вопросы по дискретной математике

Рисунок 11

2. Сток (то есть вершина с номером ) входит в множество вершин , и пусть второе число её пометки . Тогда, очевидно, что между вершинами и существует путь (состоящий из направленных рёбер — прямых и обратных дуг), соединяющий эти вершины. Обозначим вершины этого пути через и найдём минимум из символов, являющихся вторыми числами меток вершин вдоль этого пути:

Ясно, что вдоль рассматриваемого пути поток можно увеличить на (с учетом знака первого числа метки, то есть прибавляя его к уже имеющемуся потоку на ребре в случае знака «» и вычитая в случае знака «»; при этом для некоторых рёбер может получиться отрицательное число, но оно обязательно будет по абсолютной величине меньше , так как по построению для всех и , а это означает, что обратная дуга должна поменять направление, то есть она становится прямой дугой и её нагрузка будет равна модулю числа ).

Схематичный пример маршрута представлен на следующем рисунке.

Рисунок 12

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

Прибавляя к для прямых дуг этой цепи (по построению видно, что полученное число будет меньше или равно ) и вычитая это из для обратных дуг, получим новый поток из вершины в вершину (легко проверить простым рассуждением, что для новых чисел выполняются все 4 условия определения потока). Кроме того, величина нового потока по сравнению со старым увеличилась на . Для нового потока снова проведём ту же процедуру и так далее.

Так как каждый раз величина потока увеличивается, по крайней мере, на 1 (пропускные способности рёбер являются целыми (рациональными) числами), а величина максимального потока ограничена (величиной минимального сечения), то эта процедура не может продолжаться бесконечно и, значит, на каком-то шаге получим поток, для которого вершина не входит в , то есть поток является максимальным и величина его равна величине минимального сечения. Теорема доказана.

Рассуждение теоремы Форда — Фалкерсона фактически является алгоритмом нахождения максимального потока между двумя вершинами (или доказательством того, что этот поток является максимальным).

Примечание. Если в данной сети имеется несколько источников и несколько стоков, то описанный выше алгоритм можно применить следующим образом. Вводим новый источник и новый сток, причём новый источник соединяем рёбрами со всеми источниками, а новый сток — со всеми стоками, при этом пропускные способности новых рёбер считаем сколь угодно большими числами, так что эти дуги в любом возможном потоке были бы ненасыщенными (напомним, что ребра, идущие из источника и ребра, идущие в сток, всегда являются прямыми дугами). После этого для нового графа решаем задачу о максимальном потоке (из одного нового источника в один новый сток). Решив её, стираем все введённые ребра и вершины.

Пример.

Таблица 1

2. Функция. Бинарное отношение. Тотальность, сюръективность, инъективность, биективность. Примеры Множество

Множество — совокупность объектов любой природы. Эти объекты называются элементами множества.

Символ — отношение принадлежности. Запись означает, что элемент принадлежит множеству . Если элемент не принадлежит множеству , то пишут (или ).

Принцип объёмности. означает, что множества и состоят из одних и тех же элементов. Пример: . Но .

Символ — отношение включения. Запись означает, что каждый элемент множества есть элемент множества . То есть — подмножество множества .

Символ — отношение строгого включения (то есть ). Запись означает, что каждый элемент множества есть элемент множества и больше по количеству элементов. То есть — собственное подмножество множества .

Заметим, что:

• .

• Если , то .

• Если , то .

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

Пустое множество — множество, не содержащее элементов. Пустое множество есть подмножество любого множества.

У каждого множества есть два подмножества, которые называют несобственными — само множество и пустое множество. Все остальные подмножества — собственные.

Множество всех подмножеств называется множеством-степенью (или булеаном) и обозначается .

Пример. . Собственные подмножества : , несобственные: .

Если множество состоит из элементов, то множество состоит из элементов.

Объединение множеств () — множество, все элементы которого являются элементами множества или : . .

Пример. .

Пересечение множеств () — множество, все элементы которого являются элементами множеств и : . .

Очевидно, что и .

Пример. .

Множества и — непересекающиеся, если .

Разность () — множество, все элементы которого являются элементами множества и не принадлежат множеству : .

Пример. .

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

Пример. .

Универсальное множество — множество всех рассматриваемых в ходе данного рассуждения множеств.

Дополнение () — множество всех элементов , которые не принадлежат множеству . То есть . Причём: .