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

Автор работы: Пользователь скрыл имя, 30 Апреля 2012 в 01:48, лабораторная работа

Краткое описание

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

Вложенные файлы: 1 файл

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

— 207.50 Кб (Скачать файл)

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

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

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

      Таблица 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 ─ Граф сети

  1. В качестве исходной цепи выбрал 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.

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

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

  1. Далее проделал действия описанные в пункте 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. 
 
 
 

     
  1. Снова проделал действия описанные в пункте 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. 
 
 
 

     
  1. Снова проделал действия описанные в пункте 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. 
 
 

     
  1. Снова проделал действия описанные в пункте 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. 
 
 

     
  1. Полученная  таблица 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  

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

                                      Таблица 7

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

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

Информация о работе Пропускная способность сети