Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


«адача визначенн€ максимальних поток≥в м≥ж вузлами мереж≥ перевезень пошти




” практиц≥ поштового звТ€зку ≥нод≥ виникаЇ ситуац≥€, коли к≥льк≥сть посилок, що надход€ть у вузли на обробленн€, перевищуЇ њхн≥ пропускн≥ спроможност≥.

якщо таке перевищенн€ короткострокове, зазначена ситуац≥€ призводить лише до упов≥льненн€ терм≥н≥в обробленн€ посилок та де€ких незручностей, €кщо ж воно б≥льш-менш тривале Ц в≥дбуваЇтьс€ нагромадженн€ посилок, вони заповнюють складськ≥, виробнич≥ площ≥ ≥ допом≥жн≥ прим≥щенн€, закривають проходи, викликають так зван≥ завали вузл≥в. ¬узли практично перестають функц≥онувати.

–озбиранн€ завал≥в, особливо крупних вузл≥в, Ц складний ≥ тривалий процес. ƒл€ розбиранн€ завал≥в приймаютьс€ в≥дпов≥дн≥ заходи: припиненн€ прийому посилок у в≥дд≥ленн€х звТ€зку та в≥д п≥дприЇмств ≥ орган≥зац≥й; припиненн€ обм≥нювань з поштовим транспортом; перевезенн€ посилок у тимчасов≥ складськ≥ прим≥щенн€; залученн€ до роботи в≥йськовослужбовц≥в, студент≥в, пенс≥онер≥в та ≥нш≥.

≈фективним заходом розбиранн€ завал≥в Ї перевезенн€ необроблених посилок у т≥ вузли, де ≥снують можливост≥ њх обробленн€. ѕри цьому виникаЇ задача визначенн€ максимальних поштових поток≥в, €к≥ можливо спр€мувати м≥ж вузлами мереж≥ перевезень пошти.

–озгл€немо граф G (X, Y), вершини €кого в≥дпов≥дають вузлам мереж≥ перевезень пошти, ребра Ц поштовим маршрутам, що зТЇднують вузли мереж≥, а ваги ребер Ц њх пропускним спроможност€м.

ѕропускна спроможн≥сть ребра дор≥внюЇ сум≥ пропускних спроможностей (вантажоп≥дйомностей) транспортних одиниць вс≥х поштових маршрут≥в, що пр€мують по зазначеному ребру.

Ќа рис. 2.13 наведений граф G (X, Y), в €кому n = 5, m = 6. Ѕ≥л€ ребер графа зазначен≥ њх пропускн≥ спроможност≥.

 

1 1 2

       
   


4

5 3

1 6

4 1 5

 

–исунок 2.13. √раф мереж≥

” мереж≥ поштового звТ€зку, €ку в≥дбиваЇ граф, дл€ перевезень пошти використовуютьс€ маршрути:

ћ1: 1 Ц 2 Ц 3 Ц 4 Ц 5, ћ2: 5 Ц 4 Ц 3 Ц 2 Ц 1

пропускною спроможн≥стю R (M1) = R (M2) = R (M1/M2) = 1;

M3: 1 Ц 4, M4: 4 Ц 1

пропускною спроможн≥стю R (M3) = R (M4) = R (M3/M4) = 5;

ћ5: 2 Ц 3 Ц 5, ћ6: 5 Ц 3 Ц 2

пропускною спроможн≥стю R (M5) = R (M6) = R (M5/M6) = 3;

ћ7: 3 Ц 5, ћ8: 5 Ц 3

пропускною спроможн≥стю R (M7) = R (M8) = R (M7/M8) = 3.

ѕропускн≥ спроможност≥ ребер визначаютьс€ €к:

(1,2) = R (M1/M2) = 1,

(1,4) = R (M3/M4) = 5,

(2,3) = R (M1/M2) + R (M5/M6) = 4,

(3,4) = R (M1/M2) = 1,

(3,5) = R (M5/M6) + R (M7/M8) = 6,

(4,5) = R (M1/M2) = 1.

ѕропускн≥ спроможност≥ ребер зручно подавати у вид≥ матриц≥, наведеноњ у табл. 2.25.

“аблиц€ 2.25. «агальний вид матриц≥ пропускних спроможностей ребер графа

¬ершина          
  (1,1) (1,2) (1,3) (1,4) (1,5)
  (2,1) (2,2) (2,3) (2,4) (2,5)
  (3,1) (3,2) (3,3) (3,4) (3,5)
  (4,1) (4,2) (4,3) (4,4) (4,5)
  (5,1) (5,2) (5,3) (5,4) (5,5)

 

¬ершини, подан≥ в л≥в≥й колонц≥, вважаютьс€ витоками, а вершини, подан≥ в верхньому р€дку, Ц стоками, наприклад, (2,4) Ц це пропускна спроможн≥сть дуги (2,4), а (4,2) Ц пропускна спроможн≥сть дуги (4,2). ѕропускн≥ спроможност≥ ребер (2,4) ≥ (4,2) сп≥впадають. ¬≥дсутн≥м дугам або ребрам приписуютьс€ пропускн≥ спроможност≥, що дор≥внюють нулю.

” табл. 2.26 подана матриц€ пропускних спроможностей графа рис. 2.13 (пропускн≥ спроможност≥ елемент≥в головноњ д≥агонал≥ матриц≥ вважаютьс€ невизначеними).

 

“аблиц€ 2.26. ћатриц€ пропускних спроможностей графа

¬ершина          
  -        
    -      
      -    
        -  
          -

 

ќск≥льки значенн€ пропускних спроможностей ребер симетричн≥ в≥дносно головноњ д≥агонал≥ матриц≥, вони можуть бути подан≥ у вигл€д≥ трикутноњ матриц≥, елементи €коњ розташован≥ вище або нижче зазначеноњ д≥агонал≥.

ƒл€ визначенн€ значень максимальних поток≥в м≥ж вузлами мереж≥ перевезень пошти використовуютьс€ значенн€ так званих перетин≥в графа.

ѕеретином звТ€зного графа G (X, Y) називаЇтьс€ ненадм≥рна множина його дуг (ребер), вилученн€ €ких розд≥л€Ї зазначений граф на два незвТ€заних м≥ж собою графа G 1 (X 1, Y 1) ≥ G 2 (X 2, Y 2).

ѕропускна спроможн≥сть перетину дор≥внюЇ сум≥ пропускних спроможностей дуг (ребер), що його створюють.

¬≥дпов≥дно до одн≥Їњ з основних теорем теор≥њ граф≥в величина максимального потоку м≥ж вершинами та j графа дор≥внюЇ м≥н≥мальн≥й величин≥ пропускноњ спроможност≥ перетину, що розд≥л€Ї зазначен≥ вершини.

« розгл€ду матриць табл. 2.25, 2.26 видно, що у перетин, €кий розд≥л€Ї, наприклад, вершини 1, 3, 5 ≥ вершини 2, 4 вход€ть дуги (ребра), €к≥ подан≥ елементами, розташованими на перехрест€х 1, 3, 5 р€дк≥в з 2, 4 стовпчиками зазначених матриць, тобто елементи (1,2), (1,4), (3,2), (3,4), (5,2), (5,4), сума пропускних спроможностей €ких дор≥внюЇ 1 + 5 + 4 + 1 + 0 + 1 = 12.

÷е означаЇ, що значенн€ поток≥в м≥ж вершинами 1 ≥ 2, 1 ≥ 4, 3 ≥ 2, 3 ≥ 4, 5 ≥ 2, 5 ≥ 4 не перевищують 12.

–озгл€даючи посл≥довно вс≥ перетини, що розд≥л€ють вершини та j, можна визначити з них те, €ке маЇ м≥н≥мальну пропускну спроможн≥сть, ≥, тим самим, визначити величину максимального потоку м≥ж зазначеними вершинами.

Ѕудемо вважати, що кожний перетин заданий n -розр€дним дв≥йковим кодом, в €кому вершинам-витокам в≥дпов≥дають одиниц≥, а вершинам-стокам Ц нул≥. Ќаприклад, згаданий перетин, що розд≥л€Ї вершини 1, 3, 5 ≥ 2, 4 маЇ код 10101.

ќск≥льки загальне число n -розр€дних дв≥йкових код≥в складаЇ 2 n, а коди 00 Е 0 ≥ 11 Е 1 не Ї кодами перетин≥в, ≥снуЇ 2 n - 2 перетин≥в ор≥Їнтованого ≥

2 n -1 - 1 перетин≥в неор≥Їнтованого графа. “аким чином, посл≥довн≥сть код≥в перетин≥в в≥дпов≥даЇ посл≥довност≥ звичайних дв≥йкових код≥в.

¬изначенн€ величин максимальних поток≥в м≥ж вершинами графа пол€гаЇ в наступному.

ѕочатков≥ величини максимальних поток≥в м≥ж ус≥ма парами вершин графа подаютьс€ у вид≥ матриц≥ табл. 2.25 ≥ приймаютьс€ необмеженими.

—творюЇтьс€ код чергового перетину ≥ обчислюЇтьс€ величина його пропускноњ спроможност≥, €ка пор≥внюЇтьс€ з ран≥ше отриманими величинами вс≥х поток≥в, що розд≥л€ютьс€ зазначеним перетином.

якщо обчислена величина пропускноњ спроможност≥ перетину менше, н≥ж величина в≥дпов≥дного потоку, останн€ зам≥нюЇтьс€ першою.

ѕ≥сл€ розгл€данн€ вс≥х перетин≥в графа автоматично створюЇтьс€ матриц€ величин максимальних поток≥в м≥ж ус≥ма парами вершин графа, тобто, м≥ж ус≥ма парами вузл≥в мереж≥ перевезень пошти.

јлгоритм визначенн€ величин максимальних поток≥в м≥ж вершинами графа G (X, Y) поданий на рис. 2.14.

јлгоритм м≥стить 10 блок≥в.

” блоц≥ 1 провадитьс€ уведенн€ матриц≥ пропускних спроможностей ребер графа.

” блоц≥ 2 ус≥м елементам матриц≥ максимальних поток≥в, кр≥м розташованих на головн≥й д≥агонал≥, надаютьс€ необмежен≥ значенн€, €к≥ подаютьс€ у вид≥ надм≥рних чисел 999.

” блоц≥ 3 коду перетину надаЇтьс€ початкове значенн€ K = 00 Е0.

” блоц≥ 4 код перетину зб≥льшуЇтьс€ на одиницю.

” блоц≥ 5 виконуЇтьс€ розрахунок пропускноњ спроможност≥ перетину R (K).

” блоц≥ 6 провадитьс€ визначенн€ значенн€ чергового потоку P (i, j) м≥ж вершинами i, j, що розд≥л€ютьс€ зазначеним перетином.

” блоц≥ 7 величина потоку P (i, j) пор≥внюЇтьс€ з величиною пропускноњ спроможност≥ перетину R (K). ѕри P (i, j) > R (K) Ц перех≥д до блоку 8, при P (i, j) £ R (K) Ц до блоку 9.

” блоц≥ 8 величина P (i, j) зам≥нюЇтьс€ величиною R (K).

” блоц≥ 9 перев≥р€Їтьс€, чи вс≥ потоки P (i, j) м≥ж вершинами i, j, що розд≥л€ютьс€ перетином, перев≥рен≥. якщо так Ц перех≥д до блоку 10, €кщо н≥ Ц поверненн€ до блоку 6.

” блоц≥ 10 перев≥р€Їтьс€ значенн€ коду перетину. якщо в≥н менше

11 Е1 дл€ ор≥Їнтованого графа або 10 Е0 дл€ неор≥Їнтованого Ц поверненн€ до блоку 4, в протилежному випадку робота алгоритму зак≥нчуЇтьс€.

 

 

ѕочаток


1. ”веденн€ матриц≥ пропускних

спроможностей дуг (ребер)

графа


2. Ќаданн€ елементам матриц≥ величин

максимальних поток≥в надм≥рних значень

P (i, j) = 999 (i, j = 1 n, i ¹ j)


3. Ќаданн€ коду перетину значенн€

  = 00 Е 0

       
   

 


4.   =   + 1

 

 


5. –озрахунок величини пропускноњ

спроможност≥ перетину R (K)

       
   


6. ¬изначенн€ значенн€ чергового потоку

P (i, j) м≥ж вершинами, що розд≥л€ютьс€

перетином


Ќ≥

7. P (i, j) > R (K)

 

 

“ак

8. P (i, j) = R (K)

 


9. ¬с≥ потоки

Ќ≥ P (i, j) м≥ж вершинами i, j, що

розд≥л€ютьс€ перетином,

перев≥рен≥

 

“ак

н≥ 10.  оди вс≥х

перетин≥в перев≥рен≥

 

“ак

 ≥нець

 

–исунок 2.14. јлгоритм визначенн€ величин максимальних поток≥в м≥ж вершинами графа

” табл. 2.27 Е 2.34 наведена посл≥довн≥сть крок≥в формуванн€ матриц≥ максимальних поток≥в дл€ графа рис. 2.13.  роки, що не зм≥нюють значень поток≥в, випущен≥.

       
 
“аблиц€ 2.27. ‘ормуванн€ матриц≥ максимальних поток≥в
 
“аблиц€ 2.28. ‘ормуванн€ матриц≥ максимальних поток≥в

 

 


 рок 0: початковий    рок 1: R (00001) = R (11110) = 7
¬ершина           ¬ершина          
  -           -        
    -           -      
      -           -    
        -           -  
          -           -

“аблиц€ 2.30. ‘ормуванн€ матриц≥ максимальних поток≥в
“аблиц€ 2.29. ‘ормуванн€ матриц≥ максимальних поток≥в

 

 

 рок 2: R (00010) = R (11101) = 7    рок 4: R (00100) = R (11011) = 11
¬ершина           ¬ершина          
  -           -        
    -           -      
      -           -    
        -           -  
          -           -

“аблиц€ 2.32. ‘ормуванн€ матриц≥ максимальних поток≥в
“аблиц€ 2.31. ‘ормуванн€ матриц≥ максимальних поток≥в

 

 

 рок 5: R (00101) = R (11010) = 6    рок 8: R (01000) = R (10111) = 5
¬ершина           ¬ершина          
  -           -        
    -           -      
      -           -    
        -           -  
          -           -

 

       
 
“аблиц€ 2.33. ‘ормуванн€ матриц≥ максимальних поток≥в
 
“аблиц€ 2.34. ‘ормуванн€ матриц≥ максимальних поток≥в

 

 


 рок 13: R (01101) = R (10010) = 3    рок 15: R (01111) = R (10000) = 6
¬ершина           ¬ершина          
  -           -        
    -           -      
      -           -    
        -           -  
          -           -

 

ѕри визначенн≥ шл€х≥в передач≥ максимальних поток≥в м≥ж вузлами мереж≥ перевезень пошти сл≥д враховувати, що на€вн≥сть пр€мого маршруту м≥ж вузлами i, j не означаЇ його обовТ€зкового використанн€.

“ак, зг≥дно з табл. 2.34, максимальний пот≥к м≥ж вузлами 1 ≥ 5 становить 3. ” перетин з м≥н≥мальною пропускною спроможн≥стю, що розд≥л€Ї вузли 1 ≥ 5, вход€ть ребра (1,2), (3,4), (4,5).

якщо дл€ передач≥ максимального потоку використати пр€мий маршрут ћ1: 1 Ц 2 Ц 3 Ц 4 Ц 5 пропускною спроможн≥стю 1, в≥н займе вс≥ зазначен≥ ребра ≥, тим самим, перекриЇ ≥нш≥ шл€хи його передач≥.

ѕередача максимального потоку буде забезпечена, €кщо дл€ цього використати комб≥нован≥ маршрути ћ1, ћ5: 1 Ц 2 Ц 3 Ц 5 пропускною спроможн≥стю 1; ћ3, ћ2, ћ5: 1 Ц 4 Ц 3 Ц 5 пропускною спроможн≥стю 1; ћ3, ћ1:

1 Ц 4 Ц 5 пропускною спроможн≥стю 1.






ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 510 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

∆изнь - это то, что с тобой происходит, пока ты строишь планы. © ƒжон Ћеннон
==> читать все изречени€...

2064 - | 1873 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.065 с.