Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


«адача побудови маршруту листонош≥




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

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

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

–озвТ€занн€ задач≥ суттЇво залежить в≥д так званоњ парност≥ вершин графа.

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

√раф G (X, Y) називаЇтьс€ парним, €кщо вс≥ його вершини парн≥. √раф G (X, Y) називаЇтьс€ непарним, €кщо в ньому Ї непарн≥ вершини.

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

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

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

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

Ќа рис. 2.10 наведений парний граф G (X, Y), в €кому n = 6, m = 8. Ѕ≥л€ ребер графа зазначен≥ њхн≥ ваги. ѕочаткова вершина 1 в≥дпов≥даЇ в≥дд≥ленню звТ€зку.

 
 

 

 


 

ЅудуЇмо цикли:

(1,2), (2,6), (6,4), (4,1);

(1,3), (3,6), (6,5), (5,1).

ќбТЇднуЇмо знайден≥ цикли в будь-€к≥й сп≥льн≥й вершин≥, скаж≥мо 6, ≥ будуЇмо загальний цикл:

(1,2), (2,6), (6,5), (5,1), (1,3), (3,6), (6,4), (4,1).

” знайденому загальному цикл≥ ребра (1,2), (2,6) ≥ (6,4), (4,1) належать першому циклу, а ребра (6,5), (5,1), (1,3), (3,6) Ц другому.

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

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

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

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

Ќа рис. 2.11 наведений непарний граф G (X, Y), в €кому n = 6, m = 10.

 
 

 

 


 

” наведеному граф≥ вершини 2,5 Ц парн≥, вершини 1,3,4,6 Ц непарн≥.

«наченн€ найкоротших шл€х≥в м≥ж ус≥ма непарними вершинами графа наведен≥ у табл. 2.23.

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

—полученн€ непарних вершин Ќайкоротший шл€х ¬ага найкоротшого шл€ху
(1,3) 1 Ц 3  
(1,4) 1 Ц 4  
(1,6) 1 Ц 4 Ц 6  
(3,4) 3 Ц 6 Ц 4  
(3,6) 3 Ц 6  
(4,6) 4 Ц 6  

 

” табл. 2.24 наведен≥ можлив≥ вар≥анти сполучень чотирьох непарних вершин графа рис. 2.11 за допомогою додаткових ребер.

“аблиц€ 2.24. ћожлив≥ вар≥анти сполучень чотирьох непарних вершин графа

¬ар≥ант —получен≥ вершини —умарна вага додаткових ребер
  (1,3), (4,6)  
  (1,4), (3,6)  
  (1,6), (3,4)  

 

як видно з табл. 2.24, м≥н≥мальна сумарна вага додаткових ребер графа дос€гаЇтьс€ у вар≥ант≥ 2.

ќтже, додатковими повинн≥ бути ребра (1,4), (3,6), сумарна вага €ких м≥н≥мальна ≥ складаЇ 2.

Ќа рис. 2.12 наведений парний граф G (X, Y), в €кому n = 6, m = 12, отриманий з початкового непарного графа рис. 2.11 шл€хом введенн€ в нього додаткових ребер (1,4), (3,6).

 
 

 

 


 

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

(1,4), (4,1);

(3,6), (6,3);

(1,2), (2,6), (6,5), (5,1);

(1,3), (3,4), (4,6), (6,1).

ќбТЇднуЇмо знайден≥ цикли у сп≥льних вершинах 1 ≥ 3 та будуЇмо загальний цикл:

(1,4), (4,1), (1,2), (2,6), (6,5), (5,1), (1,3), (3,6), (6,3), (3,4), (4,6), (6,1).

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

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

 





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


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


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

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

—ложнее всего начать действовать, все остальное зависит только от упорства. © јмели€ Ёрхарт
==> читать все изречени€...

1975 - | 1878 -


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

√ен: 0.008 с.