3. Для каждого из подмножеств уточняем оценки, вычитая из строчек и столбцов минимальные элементы и прибавляя вычтенные числа к предыдущей оценке:

А1=		1	2	4	5	6	7	8	10+4=14
	1		3	0	2	2	0	5
	3	0		1	0	1	3	5
	4	2	5		0	1	5	1
	5	2	4	1		2	1	2	1
	6	1	7	5	3		0	4
	7	0	6	4	2	0		0
	8	6	8	2	8	2	0	

А2=		1	2	3	4	5	6	7	8	10+5=15
	1		3	1	0	2	2	0	5
	3	5			5	6	6	8	5	5
	3	0	0		1	0	1	3	5
	4	2	8	1		0	1	5	1
	5	2	4	0	1		2	1	2
	6	1	7	8	5	3		0	4
	7	0	6	6	4	2	0		0
	8	6	8	7	2	8	2	0	

4. Среди полученных подмножеств выбираем различные с наименьшей оценкой. По аналогичной схеме разбиваем его на 2 подмножества.

Указанная процедура повторяется до тех пор, пока не будет пути, проходящей через все вершины ровно по одному разу.

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

(23) (23)(87) (23)(8(;/ 7)

А1=		1	2	4	5	6	7	8		14
	1		0	0	2	2	0	5
	3	0		1	0	1	3	5
	4	2	2		0	1	5	1		С87=2
	5	2	0	0		1	0	1
	6	1	4	5	3		0	0
	7	0	3	4	2	0		0
	8	6	5	2	8	2	0	
А11=		1	2	4	5	6	8	14+2=16
	1		0	0	2	2	5
	3	0		1	0	1	5
	4	2	2		0	1	1
	5	1	0	0		1	1
	6	1	4	5	3		4	1
	7	0	3	4	2	0	
							1
А12=		1	2	4	5	6	7		8		14+3=18
	1		0	0	2	2	0		5
	3	0		1	0	1	3		5
	4	2	2		0	1	5		1
	5	1	0	0		1	0		1
	6	1	4	5	3		0		4
	7	0	3	4	2	0			0
	8	6	5	2	8	2					2

приведенная Двигаясь дальше, мы не сможем получить

оценку, меньшую чем 16

Вернемся к А₂

(2(;/ 3)(32) (2(;/ 3)(3(;/ 2)

А2=		1	2	3	4	5	6	7	8
	1		3	1	0	2	2	0	5
	2	0			0	1	1	3	0
	3	0	0		1	0	1	3	5
	4	2	5	1		0	1	5	1	С32=3
	5	2	4	0	1		2	1	2
	6	1	7	8	5	3		0	4
	7	0	6	6	4	2	0		0
	8	6	8	7	2	8	2	0	

приведенная

А21=		1	3	4	5	6	7	8	15
	1		1	0	2	2	0	5
	2	0		0	1	1	3	0
	4	2	1		0	1	5	1
	5	2	0	1		2	1	2
	6	1	8	5	3		0	4
	7	0	6	4	2	0		0
	8	6	7	2	8	2	0	

А22=		1	2	3	4	5	6	7	8	15+3=18
	1		3	1	0	2	2	0	5
	2	0			0	1	1	3	0
	3	0			1	0	1	3	5
	4	2	5	1		0	1	5	1
	5	2	4	0	1		2	1	2
	6	1	7	8	5	3		0	4
	7	0	6	6	4	2	0		0
	8	6	8	7	2	8	2	0	
			3

Разрабатываем А₂₁

(32) (32)(87) (32)(8(;/ 7)

А21=		1	3	4	5	6	7	8		15
	1		1	0	2	2	0	5
	2	0		0	1	1	3	0
	4	2	1		0	1	5	1		С87=2
	5	2	0	1		2	1	2
	6	1	8	5	3		0	4
	7	0	6	4	2	0		0
	8	6	7	2	8	2	0	
А211=		1	3	4	5	6	8	15+1=16
	1		1	0	2	2	5
	2	0		0	1	1	0
	4	2	1		0	1	1
	5	2	0	1		2	2
	6	1	8	5	3		4	1
	7	0	6	4	2	0	
А212=		1	3	4	5	6	7		8		15+2=17
	1		1	0	2	2	0		5
	2	0		0	1	1	3		0
	4	2	1		0	1	5		1
	5	2	0	1		2	1		2
	6	1	8	5	3		0		4
	7	0	6	4	2	0			0
	8	6	7	2	8	2					2

приведенная

Возвращаемся к А₁₁, т.к. там тоже 16

(23)(87) (23)(87)(61) (23)(87)(6(;/ 1)

А11=		1	2	4	5	6	8	16
	1		0	0	2	2	5
	3	0		1	0	1	5
	4	2	2		0	1	1	С61=2
	5	1	0	0		1	1
	6	1	4	5	3		4
	7	0	3	4	2	0	

приведенная

А111=		2	4	5	6	8	16
	1	0	0	2		4
	2		1	0	1	4
	4	2		0	1	0
	5	0	0		1	0
	7	3	4	2	0	

А112=		1	2	4	5	6	8	16+2=18
	1		0	0	2	2	5
	3	0		1	0	1	5
	4	2	2		0	1	1
	5	1	0	0		1	1
	6		4	5	3		4
	7	0	3	4	2	0	

Выбираем А₁₁₁

(23)(87)(61) (23)(8761) (23)(87)(7(;/ 6)(61)

А111=		2	4	5	6	8	16
	1	0	0	2		4
	3		1	0	1	4
	4	2		0	1	0	С76=3
	5	0	0		1	0
	7	3	4	2	0	

А1111=		2	4	5	8	16
	1	0	0	2	
	3		1	0	4
	4	2		0	0
	5	0	0		0

из 1 в 8 исключаем

А1112=		2	4	5	6	8	16+3=19
	1	0	0	2		4
	3		1	0	1	4
	4	2		0	1	0
	5	0	0		1	0
	7	3	4	2			2

Выбираем А₁₁₁₁

(23)(8761) (235)(8761) (23)(3(;/ 5) (8761)

А1111=		2	4	5	8	16
	1	0	0	2	
	3		1	0	4
	4	2		0	0	С76=1
	5	0	0		0

А1111=		2	4	8	16
	1	0	0	
	4	2		0
	5		0	0

из 5 в 2 искюсаем

А1112=		2	4	5	8	16+1=17
	1	0	0	2	
	3		1		4	1
	4	2		0	0
	5	0	0		0

Выбираем

(235)(8761) (235)(48761)

А11111=				2		4		8		16
		1		0		0		
		4		2				0		С48=2
		5				0		0
	А11111=		2		4		16
		1	0		
		5			0

из 4 в 1 исключаем

(23548761)

1+2+2+2+0+1+3+5=16

1. Полагаем xX (x)=0 (т.е. начинаем с нулевого потока). Крме того, полагаем D'=0.

2. Удаляем из орграфа D' все дуги, являющиеся насыщенными при потоке  в транспортной сети D. Полученный граф снова обозначаем через D'.

3. Ищем в D' простую цепь  из  в _n. Если такой цепи нет, то  - искомый полный поток в транспортной сети D. В противном случае переходим к шагу 4.

4. Увеличиваем поток (x) по каждой дуге х из  на одинаковую величину a>0 такую, что, по крайней мере, одна дуга из  оказывается насыщенной, а потоки по остальным дугам из  не превышают их пропускных способностей. При этом величина потока транспортной сети D остается допустимым (поскольку в каждую промежуточную вершину, содержащуюся в , дополнительно вышло а. едениц потока АА из нее вышло также а единиц потока). После этого переходим к шагу 2.

Пусть D - транспортная сеть. Для любого множества V₁V такого, что ₁V₁, _nV₁, разрезом сети D относительно множества вершин V₁ называется множество дуг X(V₁)={(,)XV₁,V₁}, то есть множество, включающее в себя все дуги, исходящие из вершин, не принадлежащих V₁, и заходящие в вершниы, принадлежащие V₁. Число называется пропускной способностью разреза. Расрез с минимальной пропускной способностью называется минимальным.

Для любого допустимого потока  в транспортной сети D и любого множества V₁V, где V₁,_nV₁, величина любого допустимого потока в сети D (в том числе максимального) не превышает пропускной способности любого разреза сети D (в том числе минимального).