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

  ПРОПУСКНАЯ СПОСОБНОСТЬ СЕТИ  

     Цели  работы: изучение теоретических и практических приёмов определения пропускной способности сети.

      Постановка  задачи: найти пропускную способность сети. Построить граф.

      Таблица 1

	S	1	2	3	4	T
S		2	5	3	4
1	5		1	2	5
2	4	3		3		7
3	1	5			5	5
4	3	2	6	5		3
T			1	5	4

     Ход работы:

1. Построил граф по матрице пропускной способности (рисунок 1).

Рисунок 1 ─ Граф сети

2. В качестве исходной цепи выбрал s→1→2→t.

Таким образом, ячейки (s, 1), (1,2) и (2, t) помечаются знаком (-), а ячейки (1, s), (2, 1) и (t, 2) - знаком (+). Для данной цепи максимальный поток определяется как q=min{2,1,7}=1.

Матрица в таблица 1 корректируется путем  вычитания q=1 из всех элементов, помеченных знаком (-), и сложения со всеми элементами, имеющими знак (+). Результаты приведены в таблице 2.

        ─ помечаются знаком (-);

        ─ помечаются знаком (+).

3. Далее проделал действия описанные в пункте 2. Получил таблицу 3.

      Таблица 2

      

	S	1	2	3	4	T
S		1	5	3	4
1	6		0	2	5
2	4	4		3		6
3	1	5			5	5
4	3	2	6	5		3
T			2	5	4

     

      S→2→T

      (S2) (2T) пометил знаком (-)

      (2S) (T2) пометил знаком (+)

      q=min{5,6}=5. 
 
 
 

     

4. Снова проделал действия описанные в пункте 2. Получил таблицу 4.

      Таблица 3

      

	S	1	2	3	4	T
S		1	0	3	4
1	6		0	2	5
2	9	4		3		1
3	1	5			5	5
4	3	2	6	5		3
T			7	5	4

     

      S→4→3→T

      (S4) (43) (3Т) пометил знаком (-)

      (4S) (34) (Т3)пометил знаком (+)

      q=min{4,5,5}=4. 
 
 
 

     

5. Снова проделал действия описанные в пункте 2. Получил  таблицу 5.

      Таблица 4

      

	S	1	2	3	4	T
S		1	0	3	0
1	6		0	2	5
2	9	4		3		1
3	1	5			9	1
4	7	2	6	1		3
T			7	9	4

     

      S→3→4→T

      (S3) (34) (4Т) пометил знаком (-)

      (3S) (43) (Т4)пометил знаком (+)

      q=min{3,9,3}=3. 
 
 

     

6. Снова проделал действия описанные в пункте 2.

      Таблица 5

      

	S	1	2	3	4	T
S		1	0	0	0
1	6		0	2	5
2	9	4		3		1
3	4	5			6	1
4	7	2	6	4		0
T			7	9	7

     

      S→1→3→T

      (S1) (13) (3Т) пометил знаком (-)

      (1S) (31) (Т3)пометил знаком (+)

      q=min{1,2,1}=1. 
 
 

     

7. Полученная  таблица 6 является конечной. Из табл. 6 следует, что между s и t нельзя построить цепей с положительным потоком, поскольку все элементы в строки s равны нулю.

                                       Таблица 6

	S	1	2	3	4	T
S		0	0	0	0
1	7		0	1	5
2	9	4		3		1
3	5	5			6	0
4	7	2	6	4		0
T			7	10	7

      
 
 
 
 
 
 
     

8. Нашёл матрицу  оптимального потока путём вычитания  конечной матрицы из исходной (таблица 7).

                                      Таблица 7

	S	1	2	3	4	T
S		2	5	3	4
1			1	1
2						6
3						5
4				1		3
T

      
 
 
 
 
 
 
     

9. Из таблицы 7 видно, что z=2+5+3+4=6+5+3=14. Сумма всех q(=1+5+4+3+1) также дает максимальный поток.