УНИВЕРЗИТЕТ У БЕОГРАДУ
Тема:
Оптимизација руте поштара
(семинарски рад)
Предметни наставник:
Београд, јул 2017.
4
представљање неких проблема, на пример мреже путева где се тежина односи на дужину
пута између два чвора. Тежински граф који је усмерен зове се мрежа. Две (или више)
гране графа су паралелне ако спајају два иста темена. Грана може да спаја врх са самим
собом, и тада се назива петљом. Граф који нема петље нити паралелне гране се назива
простим графом. Граф је празан ако нема ниједну грану, а нулти граф нема ниједан врх.
Степен чвора vi=d(di) је једнак броју грана које улазе/излазе из њега, с тим да се
петља рачуна као две гране. Тотални степен графа је збир свих степени графа, и једнак је
двоструком броју грана. Није могуће нацртати граф са непарним степеном.
Граф G'=(V',Е') је подграф графа G=(V, Е) ако је скуп његових чворова (V') подскуп скупа
чворова графа G (V), а скуп његових грана (Е') је подскуп скупа грана вектора G (Е). Ако
је овим графовима скуп чворова једнак, онда се граф G' назива разапињујућим графом,
или скелетом (
слика 1.1
).
Ако је степен сваког чвора исти, онда је граф регуларан. Комплетан граф је
прост граф, код кога су свака два чвора спојена граном.
Два графа, G1, и G2 су изоморфна ако и само ако постоји „1-1“ и „на“
пресликавање врхова и грана, тако да се очувава суседност свих врхова, тј. да су везе
између врхова начињене на аналоган начин. Изоморфни графови су од великог значаја у
електроници, при конструисању штампаних кола, где гране графа (струјни водови) не
смеју да се секу осим у чворовима. Зато је битно да се пронађе изоморфан граф жељеном
графу, али такав да му се гране не секу.
Слика 1.1
Теорија графова има доста прецизне историјске одреднице. Први рад из теорије
графова је Еулерово решење питања шетње коенигсбершким мостовима, објављен 1736.
године. Прву књигу из теорије графова написао је
Dénes Kőnig
200 година касније, што се
сматра почетком развоја теорије графова, као засебне математичке дисциплине.
Kőnig
је
дотадашње резултате објединио и систематизовао, наводећи попис од свега 110
објављених радова у којима се експлицитно појављује појам графа. Међу њиховим
ауторима су славна имена попут
G. Kirhhoff
,
A. Cayley
и
C. Kuratowsky
. Од тада, граф
постаје уопштено прихваћен појам. Следећих тридесетак година, језиком графова су
постављани и решавани бројни занимљиви проблеми, о чему сведочи попис од 1617
референција из теорије графова, објављен 1964. године.
5
Током 60-их година двадесетог века, почиње снажан развој истраживања у
теорији графова и њеним применама, који траје до данас. У периоду од 1960. до 1970.
број годишње објављених радова се више него удесетростручио. Данас имамо на
десетине угледних часописа који готово искључиво објављују чланке из теорије графова
и њених примена. Необично интензиван развој и велику популарност теорија графова је
доживела захваљујући наглом развоју модерних информационих технологија. Графови
постају универзални математички језик којим је могуће описати најразличитије, и сасвим
апстрактне математичке структуре.
Пажњу ћемо усмерити на две славне теме: шетњу коенигсбершким мостовима и
проблем кинеског поштара.
Проблем Седам Кeнигсбершких мостова
Успешно решавање сложених проблема који се јављају на транспортним и
комуникационим мрежама подразумева примену метода операционих истраживања,
вештачке интелигенције, теорије графова као и коришћење савремене рачунарске
технике. Током последњих пет деценија у свету је публиковано на стотине радова у
областима рутирања саобраћајних средстава и рутирања саобраћајних токова на
транспортним и телекомуникационим мрежама. Велики број алгоритама развијених за
решавање ових проблема је заснован на Теорији графова. Први рад у коме је разматран
један проблем рутирања је објавио
Leonhard Euler.
Велики математичар
Leonhard Euler
се сматра оцем теорије графова.
Проучавајући проблем “седам мостова у Кенигсбергу”
Leonhard Euler
(1707-1783) је у
свом раду
“Solutio problematis ad geometriam situs pertinentis”, Commetarii Academiae
Scientiarum Imperialis Petropolitanae
, објављеном 1736. године од стране Академија
наука у Санкт Петерсбургу утврдио у којим случајевима мрежа поседује тзв. Еулер-ову
туру и Еулер-ов пут. Еулер-а је интересовало да ли је могуће прећи преко сваког од седам
мостова на реци Прегел у граду Кенигсбергу (тада главни град пруског краљевства, а
после Калињинград у Русији) тачно једанпут. (
Слика 1.2: Проблем Седам Кенигсбершких
мостова
)
7
у нови граф (Слика 1.4) који је Еулер-ов и који има Еулер-ову туру. У новом графу могуће
су тражене поштареве стазе, на пример. стаза W(1.1).
W = de
4
ae
1
be
2
ae
3
be
6
ce
7
be
5
de
8
be
9
d (1.1)
Slika 1.4
У стази W (1.1) користе се обе вештачки додате гране е1 и е9 који омогућавају
парност свих чворова и претварају граф, (Слика 1.3) у Еулеров граф односно у граф,
(Слика 1.4).
У даљем раду ћемо видети на које начине је све могуће имплементирати
вештачке гране.
Транспортне и телекомуникационе мреже су по својој природи системи великих
димензија. На модерним транспортним и комуникационим мрежама се у сваком
тренутку обавља веома велики број путовања. У било ком тренутку велики број
корисника Интернета покушава да приђе одређеним веб страницама, десетине хиљада
људи покушава да телефонира, а хиљаде путника мења авион у хабовима.
Комплексност мрежа потиче од великог броја узрочника. Интеракција људи,
возила, процеса транспорта и складиштење робе, информационо-комуникационих
технологија и инфраструктуре је веома комплексна. Многи аспекти проблема које треба
решити на мрежама су случајни, динамички и нелинеарни.
Управљање саобраћајем и транспортом на мрежама се може спроводити кроз
низ дистрибуираних и хијерархијски распоређених нивоа. Имплементација одређених
