Teorija grafova u računarstvu

Teorija grafova ima veliku primenu u različitim oblastima, mnogi inženjerski, biološki, fizički i sociološki problemi mogu da se modeluju pomoću grafova. Da bi sve to imalo smisla, matematičke apstrakcije  koje predstavljaju grafove su morale naći svoj put do računara kako bi celokopun doprinos koji je teorija dala mogao imati i praktičnu vrednost, jednostavnije rečeno – da bi nešto moglo da se izračuna.

Mnoge matematičke apstrakcije imaju svoje mesto u računarskim naukama. Može se reći da je računarstvo “produžena ruka” matematike, jer zahvaljujući razvoju računarskih nauka danas je moguće jednostavno rešavati kompleksne probleme, i što je možda još značajnije – moguće ih je rešavati brzo. Hajde da krenemo iz početka. Na bilo kom uvodom kursu iz programiranja, ubrzo nakon lekcije o brojevnim sistemima i nakon što naučite da “peške” konvertujete brojeve iz dekadnog u binarni sistem, upoznaćete se sa pojmom – struktura podataka (eng. data structure).

 

“Struktura podataka je specijalan format za organizaciju podatka i za njegovo smeštanje u računarsku memoriju.”

 

Najbitnije strukture podataka su nizovi, liste, stekovi, redovi, stabla i grafovi. Dakle, stigli smo do te magične veze između teorije grafova i računarstva. Grafovi su u prvom redu među strukturama podataka. Oni predstavljaju generalizaciju strukture stabla. Graf je kao i stablo sačinjen od entiteta i relacija između njih, ali za razliku od stabla ne postoji koren i ne postoji nivo. U grafu, svaki element može biti u vezi sa svakim drugim i ne postoji “glavni” ni “početni” čvor. Na slici 1 su prikazani primeri jednostavnog stabla i grafa.

U računarstvu ne postoji posebna struktura za smeštanje grafa u memoriju. Graf mora biti predstavljen uz korišćenje drugih struktura. Informacije koje se čuvaju vezano za graf su čvorovi i veze koje postoje između njih, kao i usmerenost ili težina ukoliko postoje. Dva osnovna načina za skladištenje graf strukture u računarsku memoriju je pomoću matrice susednosti (eng. adjacency matrix) ili liste susednosti. Matrica susednosti predstavlja dobar način da se predstavi konektivnost. U matrici postoji polje za sve moguće veze između čvorova u grafu i ukoliko veza postoji stavlja se jedinica, a ukoliko veza ne postoji stavlja se nula.

Ukoliko je graf neusmeren onda je matrica susednosti simetrična u odnosu na glavnu dijagonalu. Takođe, matrica susednosti je dobar način da se predstavi težinski graf jer bi umesto jedinica na mestu gde postoji veza stajala vrednost težine te veze. Matricu susedosti je najbolje primenjivati kada graf ne sadrži više od par hiljada čvorova i kada je gustina grafa velika, odn. kada je velik broj međusobno povezanih čvorova u grafu. Kod grafova koji ne sadrže velik broj veza bolji način reprezentacije je uz pomoć liste susednosti. Za svaki čvor u grafu definiše se lista njegovih suseda. Takav način je pogodan kada se vrši pretraga veza koje su incidentne nekom čvoru. Na slici 2 je prikazan graf i njegova reprezentacija pomoću matrice i liste.

U zavisnosti od toga koji se način izabere za reprezentaciju grafa zavisi koliko će efikasno biti iskorišten memorijski prostor i koliko će biti brza pretraga grafa.

Optimalan načina reprezentacije grafa zavisi od veličine grafa i prirode problema koji se analizira, ne postoji univerzalno rešenje. Grafovi kao složene strukture nisu jednostavni za manipulaciju i zahtevaju poseban pristup. Za analizu grafova koriste se posebni algoritmi.

Algoritmi za analizu grafova

Algoritmi za analizu grafova su razvijani da bi se bolje razumele veze i priroda entiteta u grafu, kao i skriveni ponovljivi šabloni (eng. patterns) koji postoje u grafu. Pronalaženje najkraćih putanja, snažno povezanih komponenti, stepeni grupisanja, itd. samo su neki od veoma važnih zadataka za analizu grafa. Putanja u grafu je način da se stigne od noda a do noda b koristeći samo veze koje postoje između nodova a i b. Putanja u grafu u velikoj meri podseća na putanju u saobraćaju, jer kao ni u grafu, ni u saobraćaju ne možemo da se krećemo proizvoljnim putanjama već samo tamo gde postoji put, asfalt, kaldrma ili bilo kakva podloga pogodna za transport. Najkraća putanja, ili geodetska putanja je distanca između dva noda koja povezuje najmanji broj veza. Postoje putanje koje su posebno karakteristične i imaju specifično značenje za graf, to su Ojlerova putanja i Hamiltonova putanja. Ojlerova putanja (eng. Eulerean path) je ona putanja koja povezuje dva noda a da pri tome prođe kroz svaku vezu samo jednom. Hamiltonova putanja (eng. Hamiltonian path) je ona putanja koja prolazi kroz svaki nod samo jednom. Najkraća putanja je važna karakteristika grafa, pa tako imamo pojam diametra (eng. diameter) koji predstavlja maksimalnu najkraću putanju u grafu. Drugim rečima, to je najveća moguća udaljenost između bilo koja dva noda u grafu. “Breadth-First Search (BFS)” algoritam je jedan od najčešće korišćenih algoritama za identifikaciju najkraćih putanja u grafu.

Konektivnost (eng. connectivity) je veoma važna osobina grafa koja opisuje da li je nod u dometu od nekog drugog noda u grafu ili nije. Graf može biti u potpunosti konektovan (eng. fully connected) što znači da se od bilo kog noda u grafu može stići do bilo kog drugog noda u grafu. Grafovi koji su u potpunosti konektovani mogu biti veoma teški za analizu, zbog složenosti koja postoji u njihovoj strukturi. U grafu se mogu pojaviti strukture koje su međusobno izrazito povezane pa tako dobijamo grupu algoritama za detekciju tih povezanih struktura (eng. connected components). Podela grafa prema njegovim izrazito povezanim strukturama je globalni način da se opiše njegova struktura. “Breadth-First Search (BFS)” algoritam se takođe može koristiti za pronalaženje povezanih komponenti u grafu.

Poznavanjem strukture grafa, broj izrazito povezanih komponenti i njihov položaj u grafu možemo bolje razumeti kako se informacije šire kroz graf što može biti od velikog praktičnog značaja uz poznavanje prirode mreže koju graf predstavlja. Ako graf predstavlja telekom mrežu, poznavanjem izrazito povezanih komponenti znamo kako se informacije prenose između pojedinaca. Ako graf predstavlja neki biološki fenomen, poznavanjem izrazito povezanih komponenti znaćemo koji deo grafa je izolovan a koji je dobro povezan, a to znanje nam može pomoći da predvidimo kako će se kretati epidemija virusa ili mutacija u ćelijama.

Posebna grupa algoritama za analizu grafa su klastering algoritmi. Poznavanje klastera u grafu je od neprocenjivog značaja za razumevanje njegove strukture. Algoritmi za klastering su veoma kompleksni, i tematika njihovog izučavanja je veoma široka. Više o tome u nekom od narednih postova!