{"id":1841,"date":"2018-10-01T14:35:27","date_gmt":"2018-10-01T12:35:27","guid":{"rendered":"http:\/\/www.datascience.rs\/?p=1841"},"modified":"2018-10-01T14:35:27","modified_gmt":"2018-10-01T12:35:27","slug":"teorija-grafova-u-racunarstvu","status":"publish","type":"post","link":"https:\/\/imuno-srbija.com\/data-science\/2018\/10\/01\/teorija-grafova-u-racunarstvu\/","title":{"rendered":"Teorija grafova u ra\u010dunarstvu"},"content":{"rendered":"<p>Teorija grafova ima veliku primenu u razli\u010ditim oblastima, mnogi in\u017eenjerski, biolo\u0161ki, fizi\u010dki i sociolo\u0161ki problemi mogu da se modeluju pomo\u0107u grafova. Da bi sve to imalo smisla, matemati\u010dke apstrakcije\u00a0 koje predstavljaju grafove su morale na\u0107i svoj put do ra\u010dunara kako bi celokopun doprinos koji je teorija dala mogao imati i prakti\u010dnu vrednost, jednostavnije re\u010deno \u2013 da bi ne\u0161to moglo da se izra\u010duna.<!--more--><\/p>\n<p>Mnoge matemati\u010dke apstrakcije imaju svoje mesto u ra\u010dunarskim naukama. Mo\u017ee se re\u0107i da je ra\u010dunarstvo \u201cprodu\u017eena ruka\u201d matematike, jer zahvaljuju\u0107i razvoju ra\u010dunarskih nauka danas je mogu\u0107e jednostavno re\u0161avati kompleksne probleme, i \u0161to je mo\u017eda jo\u0161 zna\u010dajnije \u2013 mogu\u0107e ih je re\u0161avati brzo. Hajde da krenemo iz po\u010detka. Na bilo kom uvodom kursu iz programiranja, ubrzo nakon lekcije o brojevnim sistemima i nakon \u0161to nau\u010dite da \u201cpe\u0161ke\u201d konvertujete brojeve iz dekadnog u binarni sistem, upozna\u0107ete se sa pojmom \u2013 struktura podataka (<em>eng. data structure<\/em>).<\/p>\n<p>&nbsp;<\/p>\n<p>\u201c<em>Struktura podataka je specijalan format za organizaciju podatka i za njegovo sme\u0161tanje u ra\u010dunarsku memoriju.<\/em>\u201d<\/p>\n<p>&nbsp;<\/p>\n<p>Najbitnije strukture podataka su nizovi, liste, stekovi, redovi, stabla i grafovi. Dakle, stigli smo do te magi\u010dne veze izme\u0111u teorije grafova i ra\u010dunarstva. Grafovi su u prvom redu me\u0111u strukturama podataka. Oni predstavljaju generalizaciju strukture stabla. Graf je kao i stablo sa\u010dinjen od entiteta i relacija izme\u0111u njih, ali za razliku od stabla ne postoji koren i ne postoji nivo. U grafu, svaki element mo\u017ee biti u vezi sa svakim drugim i ne postoji &#8220;glavni&#8221; ni &#8220;po\u010detni&#8221; \u010dvor. Na <em>slici 1<\/em> su prikazani primeri jednostavnog stabla i grafa.<\/p>\n<figure id=\"attachment_1721\" aria-describedby=\"caption-attachment-1721\" style=\"width: 300px\" class=\"wp-caption alignleft\"><img loading=\"lazy\" class=\"alignleft size-medium wp-image-1843\" src=\"http:\/\/www.datascience.rs\/wp-content\/uploads\/graphVStree-300x193.png\" alt=\"graphVStree\" width=\"300\" height=\"193\" \/><figcaption id=\"caption-attachment-1721\" class=\"wp-caption-text\">Slika 1 &#8211; Graf vs. stablo<\/figcaption><\/figure>\n<p class=\"Standard\">U ra\u010dunarstvu ne postoji posebna struktura za sme\u0161tanje grafa u memoriju. Graf mora biti predstavljen uz kori\u0161\u0107enje drugih struktura. Informacije koje se \u010duvaju vezano za graf su \u010dvorovi i veze koje postoje izme\u0111u njih, kao i usmerenost ili te\u017eina ukoliko postoje. Dva osnovna na\u010dina za skladi\u0161tenje graf strukture u ra\u010dunarsku memoriju je pomo\u0107u matrice susednosti (<em>eng. adjacency matrix<\/em>) ili liste susednosti. Matrica susednosti predstavlja dobar na\u010din da se predstavi konektivnost. U matrici postoji polje za sve mogu\u0107e veze izme\u0111u \u010dvorova u grafu i ukoliko veza postoji stavlja se jedinica, a ukoliko veza ne postoji stavlja se nula.<\/p>\n<p class=\"Standard\">Ukoliko je graf neusmeren onda je matrica susednosti simetri\u010dna u odnosu na glavnu dijagonalu. Tako\u0111e, matrica susednosti je dobar na\u010din da se predstavi te\u017einski graf jer bi umesto jedinica na mestu gde postoji veza stajala vrednost te\u017eine te veze. Matricu susedosti je najbolje primenjivati kada graf ne sadr\u017ei vi\u0161e od par hiljada \u010dvorova i kada je gustina grafa velika, odn. kada je velik broj me\u0111usobno povezanih \u010dvorova u grafu. Kod grafova koji ne sadr\u017ee velik broj veza bolji na\u010din reprezentacije je uz pomo\u0107 liste susednosti. Za svaki \u010dvor u grafu defini\u0161e se lista njegovih suseda. Takav na\u010din je pogodan kada se vr\u0161i pretraga veza koje su incidentne nekom \u010dvoru. Na <em>slici 2<\/em> je prikazan graf i njegova reprezentacija pomo\u0107u matrice i liste.<\/p>\n<figure id=\"attachment_1721\" aria-describedby=\"caption-attachment-1721\" style=\"width: 300px\" class=\"wp-caption alignleft\"><img loading=\"lazy\" class=\"alignleft size-medium wp-image-1842\" src=\"http:\/\/www.datascience.rs\/wp-content\/uploads\/graphRepresentation-300x225.jpg\" alt=\"graphRepresentation\" width=\"300\" height=\"225\" \/><figcaption id=\"caption-attachment-1721\" class=\"wp-caption-text\">Slika 2 &#8211; Graf i njegova reprezentacija<\/figcaption><\/figure>\n<p class=\"Standard\">U\u00a0zavisnosti od toga koji se na\u010din izabere za reprezentaciju grafa zavisi koliko \u0107e efikasno biti iskori\u0161ten memorijski prostor i koliko \u0107e biti brza pretraga grafa.<\/p>\n<p>Optimalan na\u010dina reprezentacije grafa zavisi od veli\u010dine grafa i prirode problema koji se analizira, ne postoji univerzalno re\u0161enje. Grafovi kao slo\u017eene strukture nisu jednostavni za manipulaciju i zahtevaju poseban pristup. Za analizu grafova koriste se posebni algoritmi.<\/p>\n<h3>Algoritmi za analizu grafova<\/h3>\n<p>Algoritmi za analizu grafova su razvijani da bi se bolje razumele veze i priroda entiteta u grafu, kao i skriveni ponovljivi \u0161abloni (<em>eng. patterns<\/em>) koji postoje u grafu. Pronala\u017eenje najkra\u0107ih putanja, sna\u017eno povezanih komponenti, stepeni grupisanja, itd. samo su neki od veoma va\u017enih zadataka za analizu grafa. Putanja u grafu je na\u010din da se stigne od noda <em>a<\/em> do noda <em>b<\/em> koriste\u0107i samo veze koje postoje izme\u0111u nodova <em>a<\/em> i <em>b<\/em>. Putanja u grafu u velikoj meri podse\u0107a na putanju u saobra\u0107aju, jer kao ni u grafu, ni u saobra\u0107aju ne mo\u017eemo da se kre\u0107emo proizvoljnim putanjama ve\u0107 samo tamo gde postoji put, asfalt, kaldrma ili bilo kakva podloga pogodna za transport. Najkra\u0107a putanja, ili geodetska putanja je distanca izme\u0111u dva noda koja povezuje najmanji broj veza. Postoje putanje koje su posebno karakteristi\u010dne i imaju specifi\u010dno zna\u010denje za graf, to su Ojlerova putanja i Hamiltonova putanja. Ojlerova putanja (<em>eng. Eulerean path<\/em>) je ona putanja koja povezuje dva noda a da pri tome pro\u0111e kroz svaku vezu samo jednom. Hamiltonova putanja (<em>eng. Hamiltonian path<\/em>) je ona putanja koja prolazi kroz svaki nod samo jednom. Najkra\u0107a putanja je va\u017ena karakteristika grafa, pa tako imamo pojam diametra (<em>eng. diameter<\/em>) koji predstavlja maksimalnu najkra\u0107u putanju u grafu. Drugim re\u010dima, to je najve\u0107a mogu\u0107a udaljenost izme\u0111u bilo koja dva noda u grafu. &#8220;<em>Breadth-First Search (BFS)<\/em>&#8221; algoritam je jedan od naj\u010de\u0161\u0107e kori\u0161\u0107enih algoritama za identifikaciju najkra\u0107ih putanja u grafu.<\/p>\n<p>Konektivnost (<em>eng. connectivity<\/em>) je veoma va\u017ena osobina grafa koja opisuje da li je nod u dometu od nekog drugog noda u grafu ili nije. Graf mo\u017ee biti u potpunosti konektovan (<em>eng. fully connected<\/em>) \u0161to zna\u010di da se od bilo kog noda u grafu mo\u017ee sti\u0107i do bilo kog drugog noda u grafu. Grafovi koji su u potpunosti konektovani mogu biti veoma te\u0161ki za analizu, zbog slo\u017eenosti koja postoji u njihovoj strukturi. U grafu se mogu pojaviti strukture koje su me\u0111usobno izrazito povezane pa tako dobijamo grupu algoritama za detekciju tih povezanih struktura (<em>eng. connected components<\/em>). Podela grafa prema njegovim izrazito povezanim strukturama je globalni na\u010din da se opi\u0161e njegova struktura. &#8220;<em>Breadth-First Search (BFS)<\/em>&#8221; algoritam se tako\u0111e mo\u017ee koristiti za pronala\u017eenje povezanih komponenti u grafu.<\/p>\n<p>Poznavanjem strukture grafa, broj izrazito povezanih komponenti i njihov polo\u017eaj u grafu mo\u017eemo bolje razumeti kako se informacije \u0161ire kroz graf \u0161to mo\u017ee biti od velikog prakti\u010dnog zna\u010daja uz poznavanje prirode mre\u017ee koju graf predstavlja. Ako graf predstavlja telekom mre\u017eu, poznavanjem izrazito povezanih komponenti znamo kako se informacije prenose izme\u0111u pojedinaca. Ako graf predstavlja neki biolo\u0161ki fenomen, poznavanjem izrazito povezanih komponenti zna\u0107emo koji deo grafa je izolovan a koji je dobro povezan, a to znanje nam mo\u017ee pomo\u0107i da predvidimo kako \u0107e se kretati epidemija virusa ili mutacija u \u0107elijama.<\/p>\n<p>Posebna grupa algoritama za analizu grafa su klastering algoritmi. Poznavanje klastera u grafu je od neprocenjivog zna\u010daja za razumevanje njegove strukture. Algoritmi za klastering su veoma kompleksni, i tematika njihovog izu\u010davanja je veoma \u0161iroka. Vi\u0161e o tome u nekom od narednih postova!<\/p>\n<!--themify_builder_content-->\n<div id=\"themify_builder_content-1841\" data-postid=\"1841\" class=\"themify_builder_content themify_builder_content-1841 themify_builder tf_clear\">\n    <\/div>\n<!--\/themify_builder_content-->\n","protected":false},"excerpt":{"rendered":"<p>Teorija grafova ima veliku primenu u razli\u010ditim oblastima, mnogi in\u017eenjerski, biolo\u0161ki, fizi\u010dki i sociolo\u0161ki problemi mogu da se modeluju pomo\u0107u grafova. Da bi sve to imalo smisla, matemati\u010dke apstrakcije\u00a0 koje predstavljaju grafove su morale na\u0107i svoj put do ra\u010dunara kako bi celokopun doprinos koji je teorija dala mogao imati i prakti\u010dnu vrednost, jednostavnije re\u010deno \u2013 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[39,25],"tags":[42,105,118,125,143,145],"_links":{"self":[{"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/posts\/1841"}],"collection":[{"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/comments?post=1841"}],"version-history":[{"count":0,"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/posts\/1841\/revisions"}],"wp:attachment":[{"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/media?parent=1841"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/categories?post=1841"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/imuno-srbija.com\/data-science\/wp-json\/wp\/v2\/tags?post=1841"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}