Транспортные сети
Транспортной сетью T называется пара объектов Т = (G, c), где
G = (V, Γ) – орграф без петель, удовлетворяющий условиям:
а)	!v0	V :	1	(v0 ) – вход транспортной сети / источник;
б)	!u0	V : (u0 ) – выход / сток;

	c: Γ → (0; ∞)			– функция пропускных способностей дуг, т.е. каждой дуге γ поставлено в соответствие
				число c(γ) – пропускная способность дуги.
	Пусть A V . Введём следующие обозначения:
	U		(w, v) ;		U		(v, w) ;
		v				v

	U
		A

(v, w) : v A & w A ;

	U
		A

(v, w) : v A & w A .

Пусть A V :

v

0

V & u

0

A . Множество U T называется разрезом транспортной сети Т.

A

Очевидно, удаление из транспортной сети T всех дуг разреза U разрывает все (v0 – u0)-пути.

A

Если A = {u0}, то разрез U

v, u

0

: v

1 u

0

является множеством выходных дуг сети.

A

Если A = V \ {v0}, то U

v

0

, v : v v

0

– множество входных дуг сети.

A

Пропускная способность разреза

– число

U A

c U A c .

U

A

.

Разрез U A называется минимальным, если имеет наименьшую пропускную способность c U A

Поток φ в транспортной сети T – функция φ: Γ → (0; ∞) удовлетворяющая условиям:

а) ограниченности:

: c

, т.е. пропускная способность – максимальный поток по дуге;

б) сохранения:

v V \ v

0

, u

0

:

.

U

U

v

v

Число φ(γ) называется потоком по дуге γ, если φ(γ) = c(γ), то дуга γ называется насыщенной.

Поток по (v0 – u0)-пути μ называется полным, если хотя бы одна дуга этого пути насыщена.

Условие сохранения потока в сети:

.

U

U

v

0

u

0

Величина потока транспортной сети φ – число

u		.
	0
		U
		u
		0

Поток φ называется максимальным, если имеет наибольшую величину.

Задача о максимальном потоке оказывается тесно связанной с задачей о минимальном разрезе.
Лемма. Для любого потока φ и любого разреза U A :	u0	c U A		.
		U A	U A

Теорема 39. (Форд и Фалкерсон). В любой транспортной сети T величина максимального потока равна пропускной способности любого минимального разреза.

Алгоритм Форда-Фалкерсона максимизации потока в транспортной сети:

1.Перенумеровать все вершины сети произвольным образом, кроме v0 и u0.

2.Задать некоторый начальный поток φ в сети, например, нулевой поток: Г : 0 .

3.Вершинам присвоить целочисленные метки, а дугам знаки «+» или «–» по следующим правилам. а) Вершине v0 присвоить метку 0.

б) Пусть vi – помеченная вершина, а w – не помеченная вершина.

Если w vi и φ(vi, w) < c(vi, w), вершине w присвоить метку «i», а дуге γ = (vi, w) – знак «+». Если w 1 vi и φ(w, vi) > 0, вершине w присвоить метку «i», а дуге γ = (w, vi) – знак «–».

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

в) Если в результате процесса расстановки меток (п. 3,б) вершина u0 метку получила, перейти к п. 4.

5

Противное означает, что поток φ – максимальный. Дуги, начала которых имеют метку, а концы – нет, составляют минимальный разрез.

4. Рассмотреть последовательность вершин	u0	, vi	, , v0 , метка каждой из которых равна номеру
		1

следующей

обязательно

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

	,		если & γ c " " ;
			если & γ c " " ;
	,
		если .
	,

где	min				,		,
			min c ,							min .
			c " "							c " "

Перейти к п. 3.

Замечание. Дуги, получающие знак «+» называют прямыми, а дуги, получающие знак «–», –

обратными.		Первая часть п. 3.б, когда w vi	, называется прямым помечиванием, а вторая часть,
когда w	1	vi – обратным помечиванием.

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

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

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

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

Элементы комбинаторики

Комбинаторика – это раздел дискретной математики, в котором изучают операции отбора элементов из множества и их упорядочения с удовлетворением определенных условий.

Выборка – результат выполнения операций отбора элементов некоторого множества. Пусть V – множество, содержащее n элементов, и производится отбор элементов из V. Объем выборки – число отобранных элементов. Выборка объема r называется r-выборкой. Возможны две схемы отборов его элементов:

1)с возвратом, когда перед каждым отбором элемента ранее выбранный элемент возвращается в множество, а значит, может быть выбран повторно – выборка с повторениями;

2)без возврата, т.е. ранее выбранный элемент не может быть выбран повторно – выборка без повторений.

	При подсчете числа выборок для числа способов построения сложного объекта используется два
основных правила комбинаторики – правила суммы и произведения.
	Правило суммы:
	если объект A можно выбрать n способами, а объект B другими m способами, то объект				A B можно
	выбрать n + m способами;
число элементов объединения непересекающихся конечных множеств A и B равно сумме числа
	элементов этих множеств, т.е.	A B		A B A B ;

A B

A B

A

B

A B

.

Это правило легко распространяется на случай любого конечного числа объектов: Если V – конечное множество и Vi V , i 1, k : V Vi ; i j : Vi V j (разбиение V), то

V Vi i

.

В общем случае, когда i, j 1, k :Vi V j , справедливо неравенство V Vi .

Правило произведения:

если объект A можно выбрать n способами и для каждого такого выбора объект B можно выбрать m способами, то объект A & B в указанном порядке можно выбрать n∙m способами;

6

Cn r1 , , rk k n .

число элементов декартова произведения двух конечных множеств A и B равно произведению числа

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

A B

A

B .

Для любого числа объектов: если Vi,

i 1, k

, – ni-множества, то

V1 V2

Vk

n1

n2 nk .

В упорядоченной выборке (перестановке)

vi , , vi

существен

порядок следования элементов.

Неупорядоченные выборки (сочетания) vi

1

r

, , vi

полностью определяются составом элементов.

1

r

V vi ,i

.

Допустим,

что

производится выбор элементов из некоторого n-множества

1, n

Получим формулы для расчета количества выборок четырех основных типов:

P(n, r), или

r

, или Pn,r, – число r-перестановок без повторений из n-множества;

Pn

P n, r , или

r

P

, или P

, – число r-перестановок с повторениями из n-множества;

n

n,r

C(n, r), или

r

, или Cn,r, – число r-сочетаний без пвторений из n-множества;

Cn

r

, или Cn,r

, – число r-сочетаний с повторениями из n-множества.

C n, r , или Cn

1.

Выбор r-перестановки можно представить как последовательный выбор r элементов без возврата в

множество перед следующим выбором,

т.е.

k-й элемент r-выборки может быть выбран (n + k – 1)

способами,

k 1, r . По правилу произведения:

Pr n n 1 n r 1

n!

.

n

n

r !

2.

r

n

r

.

Если допускаются повторения, то каждый элемент выборки можно выбрать n способами: Pn

3.

Заметим, что упорядочение элементов r-сочетания дает r-перестановку. По правилу произведения:

P

r

n!

r

P

r

P

r

r

C

. Отсюда

C

n

r! n r !

.

n

n

r

r

n

P

r

4.

Для сочетания с повторениями

r

n 1

n r 1 !

.

Cn Cn r 1

r! n

1 !

x y

n

n

k

k

n k

Биномиальная формула (бином Ньютона) имеет вид:

Cn

x

y

.

k 0

Числа C k , k 0, n , называются биномиальными коэффициентами.

n

Используя формулу (13.6), можно получить некоторые свойства биномиальных коэффициентов:

n

n

1°.

положив x = 1, y = 1, получим

C

k

2

n

;

k 0

n

n

k

2°.

если принять x = –1, y = 1,

1

C

0

;

k 0

3°.

свойство симметрии:

C k

C n k .

n

n

Например, с помощью введенных понятий можно найти число подмножеств n-множества

Заметим, что любое k-подмножество

является k-сочетанием, т.е. число

k-подмножеств равно

C

n

Пользуясь правилом суммы и свойством 1°, находим решение: 2V

Cnk

2n 2 V .

k 0

V.

k . n

Полиномиальная формула имеет вид: x1 xk n

Cn r1 , , rk x1r1 xkrk .

i:ri 0 целое r1 r2 rk n

Числа Cn(r1, r2, …, rk) называются полиномиальными коэффициентами.

Положив x1 = x2 = … = xk = 1, получим следующее свойство:

i:ri 0 целое r1 r2 rk n

7