Teorija grafova

Označeni graf sa 6 čvorova i 7 grana

Teorija grafova je oblast matematike, veoma zastupljena i u informatici, čija je oblast istraživanje osobina grafova. Neformalno govoreći, grafovi su sastavljeni od tačaka, odnosno čvorova (vrhova), i linija među njima, odnosno grana.

Veoma je česta upotreba grafova za opis modela ili struktura podataka. Struktura jedne veb prezentacije se može predstaviti slikovito upotrebom grafa. Čvorovi tog grafa su pojedine stranice a grane grafa su veze kojima se može sa jedne stranice prelaziti na drugu.

Proučavanje algoritama koji rešavaju probleme upotrebom grafova predstavlja veoma značajan deo informatičke nauke. Mreže imaju mnogo primena u proučavanju praktičnih aspekata teorije grafova i to se zove analiza mreža. Analiza mreža je posebno značajna za probleme modeliranja i analiziranje mrežnog saobraćaja, recimo interneta.

Osobine

Ako se može smatrati da je grana koja spaja čvorove A i B isto što i grana koja spaja čvorove B i A, onda je graf neusmeren. Ako se pak smatra da su to dve različite grane onda je graf usmeren.

Pojam grafa može biti proširen dodavanjem osobine težine svakoj grani. Ovakvi grafovi se zovu težinski grafovi i oni su zgodni za predstavljanje nekih problema, na primer mreže puteva gde se težina odnosi na dužinu puta između dva čvora. Težinski graf koji je usmeren zove se mreža.

Dve (ili više) grane grafa su paralelne ako spajaju dva ista temena. Grana može da spaja vrh sa samim sobom, i tada se naziva petljom. Graf koji nema petlje niti paralelne grane se naziva prostim grafom. Graf je prazan ako nema nijednu granu, a nulti graf nema nijedan vrh.

Stepen čvora v_i=d(v_i) je jednak broju grana koje ulaze/izlaze iz njega, s tim da se petlja računa kao dve grane. Totalni stepen grafa je zbir svih stepeni grafa, i jednak je dvostrukom broju grana. Nije moguće nacrtati graf sa neparnim stepenom.

Graf G'=(V',E') je podgraf grafa G=(V, E) ako je skup njegovih čvorova (V') podskup skupa čvorova grafa G (V), a skup njegovih grana (E') je podskup skupa grana vektora G (E). Ako je ovim grafovima skup čvorova jednak, onda se graf G' naziva razapinjujućim grafom, ili skeletom.

Kompletan graf, prost graf, i njegov komplement

Ako je stepen svakog čvora isti, onda je graf regularan. Kompletan graf je prost graf, kod koga su svaka dva čvora spojena granom.

Izomorfni i neizomorfni grafovi

Dva grafa, G₁, i G₂ su izomorfna ako i samo ako postoji „1-1“ i „na“ preslikavanje vrhova i grana, tako da se očuvava susednost svih vrhova, tj. da su veze između vrhova načinjene na analogan način. Izomorfni grafovi su od velikog značaja u elektronici, pri konstruisanju štampanih kola, gde grane grafa (strujni vodovi) ne smeju da se seku osim u čvorovima. Zato je bitno da se pronađe izomorfan graf željenom grafu, ali takav da mu se grane ne seku.

Istorija

Prvi problem i njegovo rešenje izneseni na način koji je drugačiji u odnosu na prethodne i može se smatrati pretečom teorije grafova jeste rad Leonarda Ojlera pod nazivom Sedam mostova Kenigsberga, objavljen 1736. Ovo je prvi rezultat iz oblasti topologije u geometriji; što će reći ne zavisi od neke mere odnosno veličine. Ovo prikazuje duboke veze između teorije grafova i topologije.

Gustav Kirhof je 1845. godine objavio nešto što je kasnije nazvano Kirhofov zakon, a odnosilo se na problem računa napona i struje u električnom kolu.

Frensis Gutri je 1852. godine je izložio problem četiri boje koji postavlja pitanje da li je moguće obojiti zemlje na geografskoj karti sa samo četiri boje, a da se ne pojave dve susedne zemlje obojene istom bojom. Ovaj problem su rešili tek 1976. godine Kenet Apel i Volfgang Heken, ali se postavljanje ovog problema smatra rođenjem teorije grafova. Tokom pokušaja rešavanja ovog problema otkrivene su mnoge teoreme i postavljeni mnogi teoretski pojmovi i koncepti.

Aplikacije

Mrežni graf koji su formirali urednici Vikipedije (ivice) koji su doprineli različitim jezičkim verzijama Vikipedije (vrhovima) tokom jednog meseca leta 2013.

Grafovi se mogu koristiti za modelovanje mnogih tipova odnosa i procesa u fizičkim, biološkim, društvenim i informacionim sistemima. Mnogi praktični problemi mogu biti predstavljeni grafikonima. Naglašavajući njihovu primenu na sisteme u stvarnom svetu, termin mreža se ponekad definiše da označava graf u kome su atributi (npr. imena) povezani sa vrhovima i ivicama, a subjekt koji izražava i razume sisteme u stvarnom svetu kao mrežu se naziva nauka o mreži.

Informatika

U okviru računarske nauke, uzročne i nekauzalne povezane strukture su grafovi koji se koriste za predstavljanje mreža komunikacije, organizacije podataka, računarskih uređaja, toka računanja, itd. Na primer, graf u kome vrhovi predstavljaju veb stranice, a usmerene ivice predstavljaju veze sa jedne stranice na drugu. Sličan pristup se može primeniti na probleme u društvenim medijima, putovanju, biologiji, dizajnu kompjuterskih čipova, mapiranju progresije neuro-degenerativnih bolesti, i mnogim drugim poljima. Stoga je razvoj algoritama za rukovanje grafovima od velikog interesa u računarskoj nauci. Transformacija grafova je često formalizovana i predstavljena sistemima za prepisivanje grafova. Komplementarni sistemima transformacije grafova koji se fokusiraju na manipulaciju grafovima u memoriji zasnovanoj na pravilima su baze podataka grafova usmerene na bezbedne transakcije, perzistentno skladištenje i ispitivanje grafno strukturiranih podataka.

Fizika i hemija

Teorija grafova se takođe koristi za proučavanje molekula u hemiji i fizici. U fizici kondenzovane materije, trodimenzionalna struktura komplikovanih simuliranih atomskih struktura može se kvantitativno proučavati prikupljanjem statističkih podataka o grafno teoretskim svojstvima u vezi sa topologijom atoma. Takođe, „Fejnmanovi grafovi i pravila izračunavanja sumiraju kvantnu teoriju polja u obliku u bliskom kontaktu sa eksperimentalnim brojevima koje neko želi da razume.“ U hemiji graf čini prirodni model za molekul, gde vrhovi predstavljaju atome i ivice veze. Ovaj pristup se posebno koristi u kompjuterskoj obradi molekularnih struktura, u rasponu od hemijskih editora do pretraživanja baze podataka. U statističkoj fizici, grafovi mogu predstavljati lokalne veze između delova sistema u interakciji, kao i dinamiku fizičkog procesa na takvim sistemima. Slično, u računarskoj neuronauci grafovi se mogu koristiti za predstavljanje funkcionalnih veza između oblasti mozga koje su u interakciji da bi dovele do različitih kognitivnih procesa, gde vrhovi predstavljaju različite oblasti mozga, a ivice predstavljaju veze između tih oblasti. Teorija grafova igra važnu ulogu u električnom modelovanju električnih mreža, ovde se težine povezuju sa otporom segmenata žice da bi se dobila električna svojstva mrežnih struktura. Grafovi se takođe koriste za predstavljanje mikro-kanala poroznih medija, u kojima vrhovi predstavljaju pore, a ivice predstavljaju manje kanale koji povezuju pore. Hemijska teorija grafova koristi molekularni graf kao sredstvo za modelovanje molekula. Grafovi i mreže su odlični modeli za proučavanje i razumevanje faznih prelaza i kritičnih fenomena. Uklanjanje čvorova ili ivica dovodi do kritične tranzicije gde se mreža raspada u male klastere što se proučava kao fazni prelaz. Ovaj slom se proučava kroz teoriju perkolacije.

Biologija

Isto tako, teorija grafova je korisna u biologiji i konzervacionim naporima gde vrh može predstavljati regione u kojima određene vrste postoje (ili ih naseljavaju), a ivice predstavljaju puteve migracije ili kretanja između regiona. Ove informacije su važne kada se posmatraju modeli razmnožavanja ili praćenje širenja bolesti, parazita ili kako promene kretanja mogu uticati na druge vrste.

Grafovi se takođe obično koriste u molekularnoj biologiji i genomici za modelovanje i analizu skupova podataka sa složenim odnosima. Na primer, metode zasnovane na grafovima se često koriste za 'grupisanje' ćelija zajedno u tipove ćelija u analizi transkriptoma jedne ćelije. Druga upotreba je modelovanje gena ili proteina u biološkom putu i proučavanje odnosa između njih, kao što su metabolički putevi i mreže regulacije gena. Evoluciona stabla, ekološke mreže i hijerarhijsko grupisanje obrazaca ekspresije gena su takođe predstavljeni kao strukture grafova.

Teorija grafova se takođe koristi u konektomici; nervni sistemi se mogu posmatrati kao graf, gde su čvorovi neuroni, a ivice veze između njih.

Vidi još

• Graf (struktura podataka)
• Sudoku - igra slagalica koja se zasniva na ovoj teoriji
• Problem trgovačkog putnika
• Bojenje grana grafa

Литература

• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. ISBN. 
• Claude, Claude (1958). Théorie des graphes et ses applications. Paris: Dunod. ISBN.  English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
• Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736–1936. Oxford University Press. ISBN. 
• Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Springer. ISBN 978-1-84628-969-9. 
• Bollobás, Béla; Riordan, O. M. (2003). Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)) (1st изд.). Weinheim: Wiley VCH. ISBN. 
• Chartrand, Gary (1985). Introductory Graph Theory. Dover. ISBN 978-0-486-24775-5. 
• Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge University Press. ISBN. 
• Reuven Cohen, Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press. ISBN 9781139489270. 
• Golumbic, Martin (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN. 
• Harary, Frank (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. ISBN. 
• Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. New York, New York: Academic Press. ISBN. 
• Mahadev, N. V. R.; Peled, Uri N. (1995). Threshold Graphs and Related Topics. North-Holland. ISBN. 
• Newman, Mark (2010). Networks: An Introduction. Oxford University Press. ISBN. 

Додатна литература

• Hartmann, Alexander K.; Weigt, Martin (2006). „Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs”. arXiv:cond-mat/0602129 . 

Спољашње везе

• Hazewinkel Michiel, ур. (2001). „Graph theory”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Graph theory tutorial Arhivirano na sajtu Wayback Machine (16. januar 2012)
• A searchable database of small connected graphs
• Image gallery: graphs na sajtu Wayback Machine (arhivirano februar 6, 2006)
• Concise, annotated list of graph theory resources for researchers
• rocs — a graph theory IDE
• The Social Life of Routers — non-technical paper discussing graphs of people and computers
• Graph Theory Software Arhivirano na sajtu Wayback Machine (13. mart 2013) — tools to teach and learn graph theory
• Online books, and library resources in your library and in other libraries about graph theory
• A list of graph algorithms Arhivirano na sajtu Wayback Machine (13. jul 2019) with references and links to graph library implementations

Onlajn udžbenici

• Digraphs: Theory Algorithms and Applications 2007 by Jorgen Bang-Jensen and Gregory Gutin
• Graph Theory, by Reinhard Diestel