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.

Vidi još

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

Spoljašnje veze

Teorija grafova na Wikimedijinoj ostavi