Лекции. Теория графов и комбинаторика (стр. 9 )

– множество дуг, направленных от к (множество обратных дуг).

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

Пропускная способность разреза – сумма пропускных способностей прямых дуг.

Пример.

1.

2.

3.

4.

Лемма 1.

Если – сечение, то .

4Рассмотрим .

С другой стороны

3

Теорема 1.

43

Следствие.

Теорема 2.

4

Следовательно, если 3

Теорема 3 (о максимальном потоке и минимальном разрезе).

4Пусть f – максимальный поток.

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

1.  Если (дуга насыщена) дуга проходится против своей ориентации.

2.  Если дуга проходится в направлении своей ориентации.

Покажем, что – сечение, т. е. .

Допустим, что , тогда неориентированная цепь , ведущая из S в t, удовлетворяющая условиям 1 и 2. Разобьём её на две части:

Вычислим величины

В силу условий 1 и 2 . Возьмём .

Построим новый поток

. Это противоречит тому, что .

Т. о. – разрез.

В силу условий 1 и 2

3

Алгоритм построения максимального потока и минимального разреза:

1.  Начать с нулевого потока ;

2.  Построить полный поток, т. е. поток, в котором каждый путь из S в t содержит насыщенную дугу (дугу, в которой );

2.1.  Найти путь из S в t;

2.2.  Вычислить ;

2.3.  Увеличить на поток на всех дугах этого пути ;

3.  Ставить метки вершин;

3.1.  Пометить S символом +0;

3.2.  Если помечена, а не помечена, то пометить символом

3.3.  Если при этом t пометить нельзя, то , а помеченные вершины образуют множество А для минимального разреза .

Иначе, если t помечен, то неориентированная цепь из S в t (по меткам вершин),

Увеличить поток на следующим образом:

Вернуться к пункту 3.1.

Лекция № 12.

КОМБИНАТОРНЫЙ АНАЛИЗ.

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

Комбинаторный анализ – раздел математики, имеющий дело с конечными множествами.

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

Особые подмножества конечных множеств называются комбинаторными конфигурациями. Количество комбинаторных конфигураций определённого вида называется комбинаторным числом.

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

Перечислительные задачи – раздел комбинаторики, занимающийся нахождением комбинаторных чисел.

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

Введём универсальное множество из n элементов (n-множество) U и рассмотрим его подмножества из k элементов (k-подмножества). Они могут быть упорядочены или неупорядочены (линейно).

Неупорядоченное подмножество называется k-сочетанием n-множества U (из n по k).

Упорядоченное подмножество называется k-размещением n-множества U (из n по k).

Обозначение.

– число сочетаний из n элементов по k.

– число размещений из n элементов по k.

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

Пусть – названия типов элементов, тогда сочетанием (размещением) с повторениями называется сочетание (размещение), в котором элементы одного типа могут повторяться.

Обозначение.

– число сочетаний из n элементов по k с повторениями.

– число размещений из n элементов по k с повторениями.

Теорема 1 (правило произведения).

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

Теорема 2 (правило суммы).

Если объект может быть выбран способами, объект может быть выбран способами и выбор и невозможен, то или может быть выбран способами.