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

Замечание 1. Если граф не ориентирован, то миноры и совпадают.

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

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

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

Для предыдущего примера нахождение всех сечений между (1) и (4):

1. Сеть. Потоки в сети. Теорема Форда — Фалкерсона

Сеть — связный граф, в котором заданы «пропускные способности» рёбер, то есть числа . Эти числа неотрицательные, причём тогда и только тогда, когда нет ребра, соединяющего вершины и .

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

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

Поток в сети между (источником) и (стоком) — набор чисел (то есть количество условного «груза», перевозимого из вершины с номером в вершину с номером ), удовлетворяющих четырём условиям:

• Числа (провозимый по ребру груз не должен превосходить пропускной способности этого ребра). Если , то ребро — насыщенно.

• Числа , причем если , то (нет встречных перевозок). Это условие превращает поток в орграф: мы считаем, что в паре вершин, определяющей ребро, первой является та, из которой груз отправляется, а второй — та, куда он отправлен.

• Если вершина — промежуточная (не совпадает с источником и стоком), то

То есть количество груза, вывозимого из вершины , равно количеству груза, ввозимого в эту вершину.

• Количество груза, вывозимого из источника , должно быть равно количеству груза, ввозимого в сток :

Число — величина данного потока (или просто поток между и ).

Пусть имеется некоторое сечение между вершинами и . Тогда величиной сечения называется сумма пропускных способностей рёбер, входящих в это сечение.

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

Теорема Форда — Фалкерсона (1955). Максимальный поток между вершинами и равен величине минимального сечения между этими вершинами.

Доказательство этой теоремы является конструктивным (то есть показывает, как найти нужный максимальный поток).

1. Докажем сначала, что любой поток между вершинами и меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин «грузов», перевозимых по всем возможным путям из вершины в . Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести «груза» больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна сумме всех пропускных способностей рёбер данного сечения. Утверждение доказано.

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

2. Докажем теперь обратное неравенство. Пусть имеется некоторый поток (какой-то поток всегда существует, например, нулевой, когда все ). Будем помечать вершины графа, причём считаем, что все помеченные вершины образуют множество . Пометки вершин производятся от источника. Далее можно помечать только те непомеченные вершины, для которых найдётся ненасыщенное ребро из помеченной вершины или даже насыщенное ребро, если оно направлено из непомеченной в помеченную (то есть обратно направлено). Каждая пометка вершины (если эта вершина может быть помечена) состоит из двух чисел: первое число — это «» или «» номер вершины (из ), с которой смежна новая помечаемая вершина, и второе — (обязательно должно быть положительным) — это фактически та добавка к потоку, которая может быть «довезена» в эту вершину из источника по сравнению с исходным потоком , допускаемая пропускной способностью ребра.

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

• Источник принадлежит и его пометка всегда имеет вид ; второе число, условно говоря, равно бесконечности — что для дискретной математики означает, что это больше любого реального числа, которое нам встретится.

• 

Если вершина принадлежит и (дуга — прямая и ненасыщенная), то вершина также принадлежит и пометка вершины равна , где *. Заметим, что здесь число — это число уже помеченной вершины , а знак «» перед номером означает, что дуга, связывающая вершины является прямой и ненасыщенной (идёт от к ).

Если вершина принадлежит и (дуга — обратная), то вершина с номером также должна принадлежать и её пометка , где «» означает, что уже помеченная вершина смежна с непомеченной обратной дугой, ** (груз, направляемый в вершину , считаем отрицательным).

* — вместо можно написать , так как минимум от всех будет рассматриваться далее.

** — вместо можно написать , так как минимум от всех будет рассматриваться далее.

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

После того, как построение множества закончено (к нему нельзя добавить новых вершин), возможны 2 случая.

1. Сток (то есть вершина с номером ) не входит в множество вершин . Тогда обозначим множество вершин, не входящих в , через . Наш граф по условию является связным, поэтому из в идут некоторые ребра. По правилам построения все эти ребра являются прямыми насыщенными дугами.

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