Teorija grafova – matematika oko nas

Matematika je zaista, svuda oko nas. Lep primer za to je teorija grafova. Teorija grafova je oblast u matematici koja se bavi modelovanjem struktura koje sačinjavaju entiteti u paru i međusobne veze između njih, jednostavnije rečno – grafovi.

U toku školovanja često sam se susretala sa frazom da je „matematika svuda oko nas“. Koliko god to u početku zvučalo apstraktno, posle nekog vremena provedenog u rešavanju raznih teorijskih i praktičnih, inženjerskih problema shvatila sam da ta fraza i nije toliko pretenciozna.

Dakle, grafovi su matematičke strukture koje se sastoje iz čvorova (eng. nodes, vertices)  i veza između njih (eng. edges). Na slici 1 je prikazan primer jednog jednostavnog grafa.

U primeru grafa na slici 1 čvorovi istih boja imaju neke zajedničke karakteristike, dok linije koje ih povezuju predstavljaju realne veze koje postoje između tih čvorova. Lako se može primetiti da nisu svi čvorovi međusobno povezani, kao što ni realni entiteti ne moraju biti međusobno povezani. Veze između čvorova mogu biti usmerene ili neusmerene, što znači da ako posmatramo dva čvora a i b, veza između njih može biti ab ili ba ukoliko je graf usmeren ili može biti nevažno u kom pravcu je postavljena veza ukoliko je graf neusmeren. Takođe, važno je napomenuti da vizuelna reprezentacija grafa može biti različita za isti graf ukoliko čvorovi grafa nisu fiksno pozicionirani. Fiksno pozicionirane čvorove imaju grafovi koji su nastali kao reprezentacija prostornih mreža, jer u prostoru svaki čvor predstavlja tačno određenu tačku i njena pozicija je jedinstvena. Jedan od prvih problema koji je rešen primenom teorije grafova je čuveni „Sedam mostova u Königsberg – u“ (eng. The Seven Bridges of Königsberg).

Problem sedam mostova

Problem je analizirao švajcarski matematičar Leonhard Euler u 18. veku, i zaključci do kojih je došao predstavljaju osnovu i začetak teorije grafova. Kroz grad Königsberg protiče reka Pregel koja deli grad na četiri celine međusobno povezane sa sedam mostova. Problem se sastoji u tome kako pronaći putanju kroz grad tako da se prođe preko svakog mosta jednom i samo jednom. Slikovito opisano, to bilo kao kada biste srušili most za sobom nakon što ga pređete. Na slici 2 je prikazana mapa grada sa lokacijama mostova i Eulerova interpretacija tog problema. Euler je posmatrao ovaj problem na drugačiji način. Pošto je njegov zadatak bio da pronađe putanje, svaki deo grada je posmatrao kao celinu, odnosno kao čvor, dok je mostove posmatrao kao veze između čvorova. Na taj način je predstavio problem u vidu graf strukture. Zatim je analizirao sve moguće putanje između čvorova tako da se poseti svaki čvor a da se pri tome pređe preko svakog mosta samo jednom. Odgovor je da tako nešto nije moguće, evo i objašnjenja.

Hajde da se upoznamo sa još jednim pojmom vezanim za grafove, a to je stepen čvora. Stepen čvora predstavlja broj veza koje taj čvor formira sa svim susednim. Analizom svih mogućih putanja Euler je zaključio da čvor koji nije polazana ili završna tačka putanje mora imati stepen koji je paran broj. Sledeći to pravilo u zavisnosti od odabira početne i krajnje tačke možemo zaključiti koja je veza „suvišna“ da bi problem bio rešiv.

Tako je sve počelo, pre nešto manje od 300 godina. Hvala Euleru! Danas se teorija grafova primenjuje u mnogim naukama i disciplinama za analizu različitih problema. Jedna od vrlo popularnih primena je u analizi društvenih mreža. Kada posmatramo društvenu mrežu, čvorovi su pojedinci a veze između njih su „prijateljstva“. U biologiji, problem analize genoma može da se posmatra kroz prizmu teorije grafova gde bi hromozomi bili čvorovi a veze između njih veze u grafu. Ljudske interakcije posmatrane kroz telekomunikacioni saobraćaj mogu da se modeluju kao grafovi, itd. Primera ima mnogo, i u budućnosti će ih biti još i više.

Kad se sve uzme u obzir, koga ne zanima teorija grafova bolje da ne ruši mostove za sobom!

Više o teoriji grafova u narednim postovima…

 

[av_heading heading=’Reference’ tag=’h3′ style=” size=” subheading_active=” subheading_size=’12’ padding=’10’ color=” custom_font=”][/av_heading]

[1] Graph Theory general, https://en.wikipedia.org/wiki/Graph_theory

[2] The Seven Bridges Problem, https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

[3] Lessons on Graph Theory by Sarada Herke, https://www.youtube.com/watch?v=eIb1cz06UwI