Садржај

1. Увод

..........................................................................................................................................................1

1.1. Основни појмови у теорији графова................................................................................................1
1.2. Дефиниције графова .........................................................................................................................2
1.3. Врсте графова ...................................................................................................................................3
1.4. Појмови о графовима ....................................................................................................................... 3

2. Од Коенигсбершких мостова до кинеског поштара

............................................................................. 4

2.1. Шта бележе историчари....................................................................................................................4

3. Проблем кинеског поштара

.................................................................................................................. 6

3.1. Проблем кинеског поштара на неорјентисаним мрежама ............................................................6
3.1. Алгоритам за решавање проблема кинеског поштара у мрежи ...................................................8

4. Проблем Кинеског поштара задатак

.....................................................................................................9

5. Проблем трговачког путника

...............................................................................................................13

5.1. ’’Најближи сусед’’ алгоритам ......................................................................................................13

6. Алгоритми за конструкцију руте трговачког путника

....................................................................19

6.1. Алгоритам ’’убацивања’’ за конструкцију руте трговачког путника .......................................19
6.2. Алгоритам ’’најближег убацивања’’ за конструкцију руте трговачког путника .....................19
6.3. Алоритам ''најјефтинијег убацивања'' за конструкцију руте трговачког путника ...................19
6.4. Алгоритам ''произвољног убацивања'' за конструкцију руте трговачког путника ..................20
6.5. Christofides-ов хеуристички алгоритам за конструисање руте трговачког путника ................20
6.6. Clarke-Wright-ов алгоритам ''уштеда'' за конструкцију руте трговачког путника ...................20
6.7. Алгоритам ''највећег угла'' за конструкцију руте тргочког путника .........................................21
6.8. Алгоритам ''убацивања у конвексан многоугао'' за конструкцију руте трговачког путника .22
6.9. Or-ов алгоритам за конструкцију руте трговачког путника ......................................................22
6.10. 2-OPT, 3-OPT и k-OPT хеуристички алгоритам за решавање проблема трговачког путника 23

7. Проблем m трговачких путника

..........................................................................................................24

8. Алгориам најбржег убацивања за конструкцију руте трговачког путника

....................................25

9. Кристофидесов алгоритам за конструкцију руте трговачког путника

...........................................34

10. Проблеми рутинга саобраћајних средстава

......................................................................................38

11. Метод додељивања, асигнације

........................................................................................................39

11.1. Метод трговачког путника (метод Кенинсбершких мостова) .................................................42

11.1.1. Еастман – ов Алгоритам ....................................................................................................... 42

12. Колесаров алгоритам

.......................................................................................................................... 51

13. Закључак

.............................................................................................................................................. 55

14. Литература

.......................................................................................................................................... 56

1. Увод

1.1. Основни појмови у теорији графова

Комбинаторика (са Теоријом графова) је једна од најстаријих области математике, али и данас

је веома актуелна. Неки њени проблеми су заокуп али математичаре вековима (попут проблема
четири боје), док су неке области постале веома актуелне са вртоглавим развојем рачунара и
њиховом све већом применом при решавању математичких проблема.
Графови су математички објекти које веома често срећемо у свакодневном животу. Ако
посматрамо неку географску мапу са мноштвом градова који су повезани неким путевима
добијамо један граф. У скупу људи на неком предавању неки се међусобно познају, а неки не - ако
све људе представимо тачкицама, а само оне који се познају спојимо линијама добићемо један
граф, који нам даје добру слику познанства међу људима на том предавању. Структурна формула
неког молекула или једињења такође представља један граф. Шема неког електричног кола у
теорији кола или електроници исто представља један граф.
Графови налазе примену и у решавању такозваних проблема за разбибригу.

За приказивање појединих географских локација и веза међу локацијама често се

користе тачке и повезнице међу њима. Две тачке и линија која повезује те тачке могу на
пример представљати директну ваздушну линију између два града. Употребна вредност
структуре где тачка представља неку географску локацију, а линија на пример пут од једне до
друге географске локације добра је мотивација за увођење математичке структуре коју називамо
граф.

Први рад у којем се користи „граф“ за приказ односа географских локација и

њихових повезница објавио је 1741. швајцарски  математичар  Leonhard Euler  (1707.–1783.)  у
часопису  Commentarii academiae scientiarum Petropolitanae, у коме  је формулирао и решио
проблем Седам Кöнигсбершких мостова. Проблем  који  је решавао  Леонхард  Еулер  је
интересантан  због  приступа  у  коме  је  за решење проблема битна само енумерација објеката
проблема  и њихова међусобна повезаност, а не стварне тополошке димензије постављеног
проблема. Проблем Седам Кöнигсбершких мостова је настао када су становници Калининграда
(тадашњег Кöнигсберга) покушавали пронаћи начин да пређу свих  седам  мостова  тако да  сваки
мост  пређу  тачно  једанпут  и  да  се  врате  у  полазну  тачку, али безуспешно. Сами  мостови
су  изграђени  с  обе  стране  реке  Прегел  и  на  два  речна  острва  (слика1.1 Проблем Седам
Кöнигсбершких мостова ). Седам мостова повезује обе стране реке и острва. Еулер је доказао да на
жељени начин није могуће обићи свих седам мостова.

Слика 1.1. Проблем Седам Кoнигсбершких мостова

У сваком случају, граф је задат ако су задата два скупа, скуп чворова и скуп грана.

1.3. Врсте графова

Граф који има коначан број чворова се зове

коначан граф

. Аналогно, граф са бесконачним бројем

чворова се зове

бесконачан граф

Ако је свеједно да ли је грана графа

исто што и

и то важи за све гране графа, онда

је

симетрична релација, а граф је

симетричан

или

неоријентисан

. Код таквих графова се

изостављају стрелице на цртежу.

Ако све гране на графу имају стрелице, односно оријентисане су, тада је цео
граф

оријентисан

или

антисиметричан

Повезан граф

је такав неоријентисани граф код кога се било која два чвора могу повезати путем.

Ако постоје два чвора која се не могу повезати, граф је

неповезан

1.4. Појмови о графовима

Грана графа која полази из једног чвора и завршава у истом чвору се зове

петља

Неповезан граф се састоји од бар два неповезана дела. Такви делови се зову

компоненте

повезаности графа

Ако се удаљавањем једног чвора из графа он распада, односно број компонената повезаности се
повећава, тада је тај чвор

артикулациони чвор

Ако се удаљавањем једне гране граф распада, грана се зове

мост графа

Степен чвора

графа је број грана графа који имају крај у чвору. Ако грана спаја чвор са самим

собом, онда се она рачуна два пута.

Грана која спаја чвор са степеном један је

висећа грана.

2. Од Коенигсбершких мостова до кинеског поштара

2.1. Шта бележе историчари

Теорија графова има доста прецизне историјске одреднице. Први рад из теорије графова је

Еулерово решење питања шетње Коенигсбершким мостовима, објављен 1736. године. Прву књигу
из теорије графова написао је 200 година после Д. Коениг, што се сматра почетком развоја теорије
графова као засебне математичке дисциплине. Коениг је дотадашње резултате објединио и
систематизовао, наводећи списак од свега 110 објављених радова у којима се експлицитно
појављује појам графа. Међу њиховом ауторима су славна имена попут Г. Кирххофф, А. Кејли и
Ц. Куратовски. Од тада граф постаје уопштено прихваћен појам. Следећих тридесетак година
језиком графова су постављани и решавани бројни интересантни проблеми о чему сведочи пример
списак од 1617 референција из теорије графова објављен 1964. године.

У 60-тим годинама двадесетог века почиње снажан развој истраживања у теорији графова и

њеним применама који траје до данас. У периоду од 1960. до 1970. број годишње објављених
радова се више него удесетеростручио. Данас имамо на десетине угледних часописа који готово
искључиво објављују чланке из теорије графова и њених примена. Необично интензиван развој и
велику популарност теорија графова је доживела захваљујући, директно или индиректно, наглом
развоју модерних информационих технологија. С друге стране, графови постају универзални
математички језик којим је могуће описати најразличитије, и сасвим апстрактне математичке
структуре.

Овде ћемо усмерити пажњу на две славне теме: шетње коенигсбершким мостовима и проблем

кинеског поштара.

Слика 2.1. Коенигсбершки мостови

Грађани КОЕНИГСБЕРГ (тада главни град пруског краљевства, а после Калињинград у Русији)
забављали су се старим питањем могу ли прошетати својим градом тако да сваки од 7 мостова на
реци Прегел пређу тачно једанпут и заврше шетњу у полазној тачки, Слика 2.1. Леонхард Еулер
решио је тај проблем као успутни задатак на почетку каријере водећег математичар Руске царске
академије у Петрограду, где је 1733. године добио посао. Одговор је био недвосмислен: таква
шетња није могућа ако сваки део копна није с осталима повезан парним бројем мостова.
Шематски приказ на Слици 2.2 , на којем су делови копна (обале B и C и отоци А и D)
представљени тачкама а мостови њиховим спојницама, прототип је модела који ће одредити
дефиницију појма графа.

3. Проблем кинеског поштара

1.Дефинисање проблема кинеског поштара
2. Проблеми кинеског поштара на неоријентисаним мрежама

Дефинисање:
1.         Један  поштара  је  одговоран  за    разношење  поште  у  делу  града  .  Он    започиње  са  ра
разношењем поште из одређеног извора у  коме  је  лоцирана пошта и  током радног времена  мора
да   обиђе све   улице у посматраном делу града   најмање   једанпут   да би   се на завршетку радног
времена  вратио у пошту . Поставља се питање која је о рута којом  треба да се креће  поштар тако
да     растојање     које  пређе  буде     минимално  при     чему     сваку  улицу  треба  да  обиђе  најмање
једанпут.

Који је најкраћи пут којим треба да се крећемо кроз мрежу тако да кроз све гране мреже

прођемо најмање једанпут и да се на крају вратимо у чвор из ког смо кренули. Овај проблем је

први пут изучован од стране аутора Меј Коа и тај рад је обављен у часопису кинеска

математика, тако да се назвао проблем кинеског поштара.

Преведено на терминологију транспортних мрежа ово питње гласи: који је најкраћи пут којим

треба да се крећемо кроз транспортну мрежу, тако да кроз све гране мреже прођемо најмање
једанпут и да се на крају вратимо у чвор из ког смо кренули.

Ојлерова тура

је циклус којим се кроз сваку грану у мрежи пролази тачно једанпут.

Ојлеров пут

је пут којим се кроз сваку грану мреже пролази тачно једанпут ,при чему се пут не

завршава у чвору из кога је почео

Проблем кинеског поштара може се јавити на неорјентисаним, орјентисаним и мешовитим

мрежама.

У зависности од саобраћајно-транспортног проблема који се разматра под поштаром могу

да се подразумевају возила за прање улица, возила за чишћење улица од снега, возила за
сакупљање смећа у густо насељеним улицама, возила која се користе за поправку и инспекцију
комуналне инфраструктуре.

3.1. Проблем кинеског поштара на неорјентисаним мрежама

Нека је дата неорјентисана мрежа

и нека су познате функције свих грана

Величине

могу да представљају и трошкове , време

путовања или нешто друго.

Проблем кинеског поштара на неорјентисаним мрежама можемо дефинисати на следећи

начин.

Пронађимо циклус којим је могуће проћи кроз све гране мреже најмање једанпут и за

који важи

где је

број пролазака кроз грану